"""A BARD DAY'S NIGHTa.k.a. BARD ROCK CAFEa.k.a. THE SCHOOL OF BARD KNOCKSa.k.a. A BARD RAIN'S A-GONNA FALL"""

# Imports

from typing import Optional, TextIO, Dict, Set, List,Tuple # Specific annotations

from math import ceil # For stats

# Constants

# Minimum number of songs for a villager to be promoted to abardBARD_THRESHOLD = 10

# Number of songs for the billboard_top statisticBILLBOARD_N = 10

# Maps from {name: songs that this person knows}villagers_type = Dict[str, Set[str]]

bards_type = Set[str]

# Maps from {song name: names of people that know thissong}songs_type = Dict[str, Set[str]]

# A list of parties; each party is a set of the attendeenamesparties_type = List[Set[str]]

def read_input( f: TextIO,) -> Tuple[villagers_type, bards_type, songs_type,parties_type]: """ Read the given file and return the villagers,bards, songs, and parties.

f is an open file containing VILLAGERS andbards, SONGS, and PARTIES, in that order. One villager or bard perline; one song per line; one party per line,consisting of attendees separated by commas. The parties are given inthe order they're held.

""" # TODO villagers = dict() bards = set() songs = dict() parties = list() while True: line =f.readline().strip() if line =='VILLAGERS': while True: name = f.readline().strip() if name == '': break if name[-1] == '*': bards.add(name[:-1]) else: villagers[name] = set() elif line =='SONGS': while True: song = f.readline().strip() if song == '': break songs[song] = bards.copy() else: while True: line = f.readline().strip() if line == '': break names = set() for name in line.split(','): names.add(name) parties.append(names) break return villagers, bards, songs, parties

def sing_at_party( villagers:villagers_type, bards: bards_type, songs: songs_type, party:Set[str]) -> None: """ A bard sings if present, otherwise the villagerssing. """ # TODO pass

def update_bards_after_party( villagers:villagers_type, bards: bards_type, songs: songs_type, party:Set[str]) -> None: """ Promote attendees who have learned enough songsto bards, iff there is another bard present at theparty. """ # TODO pass

def unheard_songs( villagers:villagers_type, bards: bards_type, songs: songs_type, parties:parties_type,) -> Set[str]: """ Return a set of songs that have never been heardby non-bards. (This means that only the bards know it.) """ # TODO pass

def billboard_top( villagers:villagers_type, bards: bards_type, songs: songs_type, parties:parties_type,) -> List[str]: """ Return a list of the BILLBOARD_N most popularsongs by number of people who know them, in descending order. Break tiesalphabetically. """ # TODO pass

def all_bards( villagers:villagers_type, bards: bards_type, songs: songs_type, parties:parties_type,) -> Set[str]: """Return the set of the village'sbards.""" # TODO pass

def average_attendees( villagers:villagers_type, bards: bards_type, songs: songs_type, parties:parties_type,) -> int: """ Return the average number of attendees atparties in the village. Round up to the nearest integer. """ # TODO pass

# Main process

def run(filename: str) -> Dict[str, object]: """ Run the program: Create a village, read theinput, host the parties, and return a dictionary of resulting statisticskeyed by name: unheard_songs, billboard_top, all_bards,average_attendees

filename is the name of an input file. """ # TODO f = open(filename) villagers, bards, songs, parties =read_input(f) for party in parties: sing_at_party(villagers,bards, songs, party) update_bards_after_party(villagers, bards, songs, party) return dict()

# Run program

if __name__ == "__main__":

# Sample input from the handout -- you cantweak this if you like stats_handout = run("handout_example.txt") print("Results of handout sample input") for key, value in stats_handout.items(): print(f"{key}:{value}")

print()

# Sample bigger input -- you can tweak thisif you like stats_bigger = run("bigger_example.txt") print("Results of bigger sample input") for key, value in stats_bigger.items(): print(f"{key}:{value}")

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 learned from these porte ous events. Your task Simulate the above village with its nightly parties. You'll be given a list of villagers 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.) 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 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 of the 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. If the 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 Markus. 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 if there 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 if there are no new songs for a bard to sing? The party is boring. No one sings. Nothing changes. What happens if 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. a party where a villager learns enough songs to If there's become a bard but there isn't a bard at the party, do they miss their chance? No, they become a bard at the next party they attend where there's a bard (if they ever attend such a party). Sets One of the concepts you'll be practicing throughout this assignment is sets. A set is very much like a list, There are values are always unique. Sets have no order. There are no indices and you can't access individual elements. no Sets have their may find find sets a party has no bard, but during the party a duplicate values with Checking whether a value is in a set is instantaneous, no matter the size. organized. a few differences: own set set union and a valuable tool throughout this assignment. Important Reminders Compared to prior assignments, note this time that we are asking you to write functions that do what we have specified. In particular, none of your functions should use input or print. don't change what you have been given in the starter code. then our correctness tests on your will not work Please If you do, code in a set. No matter what you do, Test, test, test! correctly. o For the code we have given you, do not add or remove any parameters, change any parameters or return types, or change type annotations. Please don't any You can and of operations as described in set theory. You set difference useful and, in general, you will Please submit must work You The final thing and make sure code. add additional import statements. should add helper functions to keep your code The test cases that we give you are not to be considered full testing. all of your files to Markus. alone on this assignment. you should do is to open your code that the code displays correctly as only Python files in Notepad