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.

The villagers were most interested in the strangers wide-ranging knowledge of popular songs from the future. 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 werent 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 themselves.

Your task

Simulate the above village with its nightly parties.

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

Youll 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 theres at least one bard present, they sing a song that none of the regular villagers at the party know yet. Specifically, the bard sings the first new song alphabetically, according to Pythons sort order of strings.

If there are no bards present, everyone at the party sings all the songs they know at that point.

Either way, whenever a song is sung, everyone at the party learns and remembers it.

If a villager learns enough songs, and theyre at a party with a bard, they too become a bard and learn every song.

Finally, youll calculate some statistics about the simulation.

Sets

One of the concepts youll be practicing throughout this assignment is sets.

A set is very much like a list, with a few differences:

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 cant access individual elements.

Checking whether a value is in a set is instantaneous, no matter the size.

Sets have their own set of operations as described in set theory. You may find set union and set difference useful and, in general, you will find sets a valuable tool throughout this assignment.

Input File

Each test case is one input file. Heres 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

People with an asterisk * after their name are bards. However, the asterisk isnt part of their name notice there are no asterisks in the list of parties.

Of course, there may be any number of villagers, bards, songs, and parties (including zero). An important task is to write the read_input function, which parses the input into the villagers, bards, songs, and parties structures in Python. (HINT: how can you tell when one part of the file ends? You need to keep track of which part of the file you are working on now!)

Walkthrough of the above example

Lets say for this example that the threshold to become a bard is 2 songs. The first party has a bard, Dan. Hes a bard so he knows every song. He sings Call Me Maybe (the first alphabetical song that no one at the party knows). At the next party, theres 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. Under our assumption that the threshold to become a bard is 2 songs, 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 villages parties:

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

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 Pythons sort order of strings. (HINT: the list sort method is going to be very helpful here. What criterion does it sort on by default? How many times will you need to sort? What can the key parameter be used for?)

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

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 MarkUs.

In bard.py, youll 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 youve been given and the functions you must write.

Testing

We have a thorough set of tests on which well run your code. Everything well 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 if there are multiple bards at a party? Only one of them sings. It doesnt 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 if there are no new songs for a bard to sing? The party is boring. No one sings. Nothing changes.

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 cant happen. A party either has a bard at the beginning or doesnt, and a partys status never changes once its begun.

If theres a party where a villager learns enough songs to become a bard but there isnt a bard at the party, do they miss their chance? No, they become a bard at the next party they attend where theres a bard (if they ever attend such a party).

Important Reminders

Compared to prior assignments, note this time that we are asking you to write functions that do what we have specified. None of your functions should use input or print.

Please dont change what you have been given in the starter code. If you do, then our correctness tests on your code will not work correctly.

For the code we have given you, do not add or remove any parameters, change any parameters or return types, or change any type annotations.

Please dont add additional import statements.

You can and should add helper functions to keep your code organized.

Test, test, test! The test cases that we give you are not to be considered full testing.

The final thing you should do is to open your code files in Notepad and make sure that the code displays correctly as only Python code.