Q1: Finding the Key

Background

It has been rumored that professor Dan has a          reading level of a 5 year old. Being embarrassed of this, he keeps his books encrypted so that others    cannot find out what he is reading. You somehow   stumble into his book library and discover the         encrypted books. Since you took a class with Dan,  you want to discover if the rumour is true.

We define the encrypted text as the text that is          encrypted and therefore not currently readable. We define the plaintext as the text that was encrypted.

Remember the Caesar Cipher that we worked on in  Week 3? After some investigation, you realize that    Dan has used a Caesar Cipher to encrypt each book.

As a reminder, Caesar Cipher is an encryption    technique in which each letter of the plaintext is

shifted by a certain number of characters. The       encrypted text can be decrypted by shifting in the opposite direction.

In Week 3, we used a shift value of 3. Here, Dan has chosen his own shift value for each book.

You need to decrypt Dan’s books to figure out what he is reading and confirm/deny the rumour.

Your Task

You will write a function that can be used to decrypt Dan’s encrypted text. You will be given an open         file that contains an encrypted passage from one of  the books, and the name of afile containing a            wordlist of English words. You need to discover the  shift value to use (0-25) in order to decrypt the text. A correct shift value is one that leads to the                 maximum number of words being found in the          English list ofwords.

To find the words in the encrypted text, you must       call split(). For a given shift value, convert all           letters to lowercase, then try to find each word in the English wordlist. Do not remove any punctuation or  symbols from the word: for example, if the word         is hello!, then that is the exact string, including         exclamation mark, that you should try to find in the   English wordlist.

Your function should return a string where all letters are in lowercase, and all other characters (newlines,   spaces, punctuation, etc.) are retained.

Input

In each test case, we will call your decrypt function with an openfile that contains encrypted text, and   the name of afile containing an English wordlist.

An encrypted file contains the encrypted text; for example, it might look like this:

Q  svme  pm  nmtb  smmvtg  bpm  ijamvkm  wn  pqa

abases

Return Value

Using the full English wordlist provided in the

starter code, your function would return the

following string for the above encrypted text:

i  knew  he  felt  keenly  the  absence  of  his

own  family.

Please find your starter code and test examples in

 In decrypt.py, you’ll find a function

Testing

We have a thorough set of tests on which we’ll run  your code. Everything we’ll test has been discussed here and in the starter code, so please read both      carefully!

The starter code includes the test case from this handout that you can try out by

running test_decrypt.py. We have also provided several txt files that you can use to test as well.

Q2:A Bard Day’s Night

Background

Once upon a time, in a certain medieval village, a        group of mysterious strangers appeared in jeans and  T-shirts. The strangers managed to learn enough Old English to explain that they had been enjoying their   favourite pastime – belting out tunes at a karaoke

party – when they saw a blinding flash and heard a thunderous roar, lost consciousness, and found       themselves transported back in time without any    explanation.

Of all their bizarre story, the villagers were most         interested in the strangers’ wide-ranging knowledge  of popular songs from their own time. They                  understood that the strangers belonged to some sort  of bard class. The villagers were also party animals,   and had a feast every night. The bards agreed to          come to some of the parties and sing one Billboard     Top 40 song whenever they did. When they weren’t   there, the villagers would sing these songs to each      other, reverently, knowing that they held clues to the future of their world. The more they learned, the         more they were able to share, and some were even      initiated into the mysterious strangers’ inner circle    and allowed to become bards and learn all the             secrets of the 21st-century pop music scene. The         village chronicler wrote down the most important      things they learned from these portentous events.

Your task

Simulate the above village with its nightly parties.

You’ll be given a list ofvillagers and bards. You’ll     also get a list of songs. The bards start out knowing every song, but no one else knows any songs.

You’ll be given a list of parties with their attendees, in the order that the parties are held. Every party    features singing. There are two ways a party can      unfold:

•   If there’s at least one bard present, they sing a   song that none of the regular villagers at the       party know yet. (Specifically, the first new song alphabetically, according to Python’s sort order of strings.)

•   Ifthere are no bards present, everyone at the

If a villager learns enough songs, and they’re at a      party with a bard, they too become a bard and learn

every song.

Finally, you’ll calculate some statistics about the simulation.

Technical details

Input

Each test case is one input file. Here’s a sample input file:

VILLAGERS

Luke  Sawczak

Dan  Zingaro*

Freddie  Prinze  Jr.

Arnold  Rosenbloom

SONGS

People,  I've  Been  Sad

Call  Me  Maybe

What  a  Man  Gotta  Do

Delete  Forever

PARTIES

Dan  Zingaro,Freddie  Prinze  Jr.,Arnold

Rosenbloom

Arnold  Rosenbloom,Luke  Sawczak,Freddie  Prinze

Jr.

Dan  Zingaro,Luke  Sawczak

Freddie  Prinze  Jr.,Luke  Sawczak,Arnold

Rosenbloom

Villagers with an asterisk * after their name are         bards. However, the asterisk isn’t part of their name – notice there are no asterisks in the party list.

Of course, there may be any number of villagers, bards, songs, and parties.

Walkthrough ofthe above example

The first party has a bard, Dan. He sings Call Me Maybe (the first alphabetical song that no one     knows). At the next party, there’s no bard, but

Arnold and Freddie teach Call Me Maybe to Luke. At the third party, Dan the bard is back. Since Luke        already knows Call Me Maybe, Dan debuts Delete      Forever next. At the fourth party, Luke teaches           Freddie and Arnold Delete Forever. Ifthe threshold   to become a bard was 2, Luke would have qualified    to be a bard after the third party, and Freddie and      Arnold after the fourth party.

Statistics

After the simulation, you will prepare and return these stats on your village’s parties:

1.  unheard_songs: The set of songs that have never been heard by non-bards.

2.  billboard_top: A list of the n best-known songs in descending order from songs known by the     most people to songs known by the fewest.           Break ties alphabetically, according to Python’s   sort order of strings.

3.  all_bards: The set of villagers who are bards,  whether they started out as one or became one by learning enough songs.

4.  average_attendees: The average number of   people at a party. Round up to the nearest       integer (so both 1.7 and 1.1 should become 2).

Starter code

Please find your starter code and test examples in

In bard.py, you’ll find functions marked

with TODO whose implementations you must

complete.

You also have a couple of import statements to make the type annotations work and constants for the          number of songs a villager must know to become a     bard and the number of Billboard Top songs.

Take some time to read over the starter code to          understand the structure, as well as the functions     you’ve been given and the functions you must write.

Testing

We have a thorough set of tests on which we’ll run  your code. Everything we’ll test has been discussed here and in the starter code, so please read both      carefully!

The starter code has some tests, including one          holistic test (the statistics you should output for the sample given above), which you can try out by           running test_bard.py.

F.A.Q.

Can there be duplicate villager names or song names?

No.

What happens ifthere are multiple bards at a party?

Only one of them sings. It doesn’t matter which one, since they would all choose the same next song.

What happens if there are only bards at a party?

Whether anyone sings or not makes no difference since all the bards already know all the songs.

What happens ifthere are no new songs for a bard to sing?

What happens if a party has no bard, but during the party a villager learns enough songs to become one?

A villager can only become a bard at a party that      already has a bard, so this can’t happen. A party      either has a bard at the beginning or doesn’t, and a party’s status never changes once it’s begun.

Ifthere’s a party where a villager learns      enough songs to become a bard but there   isn’t a bard at the party, do they miss their

chance?

Sets

One of the concepts you’ll be practicing throughout

•   There are no duplicate values in a set. No matter what you do, values are always unique.

•   Sets have no order. There are no indices and you can’t access individual elements.

•   Checking whether a value is in a set is

Important Reminders

•   Compared to prior assignments, note this time    that we are asking you to write functions that do