Description

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 of villagers, some of whom are 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, calculate some statistics about the simulation.

Technical details

Input

Each test case is one input file. An input file has this format:

VILLAGERS
Luke Sawczak
Dan Zingaro*
Sadia Rain Sharmin
Arnold Rosenbloom

SONGS
Call Me Maybe
People, I've Been Sad
What a Man Gotta Do
Dan Zingaro,Sadia Rain Sharmin,Arnold Rosenbloom
Delete Forever

PARTIES
Dan Zingaro,Luke Sawczak
Arnold Rosenbloom,Luke Sawczak,Sadia Rain Sharmin
Sadia Rain Sharmin,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, 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 Sadia 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 Sadia 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 Sadia and Arnold after the fourth party.

Object-Oriented Model

One of the objectives of this course is to practice OOP: object-oriented programming. In OOP, you organize a program around classes that model real-world objects, using attributes and methods to define how they behave and interact. This is contrasted with the imperative programming you used in CSC108, where you mostly wrote independent functions with behaviour that only depended on the input, not the state of the program.

Here’s an example. First, here’s an imperative programming block:

# Imperative programming
def move(x: int, y: int, x_shift: int, y_shift: int) -> Tuple[int]:
    """Return the given (x, y) coordinates updated by the given shifts."""
    return (x + x_shift, y + y_shift)

coords = (5, 7)
new_coords = move(coords[0], coords[1], 2, 2)  # move 2 down and 2 over  

Now here’s a block doing the same thing in an object-oriented way:

# Object-oriented programming
class Point:
    def __init__(self: Point, x: int, y: int) -> None:
        """Create a Point at the coordinates (x, y)."""
    def move(self: Point, x_shift: int, y_shift: int) -> None:
        self.x = x
        self.y = y
    
        self.x = self.x + x_shift
        """Update this Point's (x, y) coordinates by the given shift."""
        self.y = self.y + y_shift
    
    
    point = Point(5, 7)
    point.move(2, 2)  # move 2 down and 2 over

This time, we have a class that saves (x, y) coordinates. It’s easy to find and refer to, and it simplifies the move function inputs. However, both the code and the documentation got longer.

There are different use cases, and you’re encouraged to take your time to think about other benefits and drawbacks. But either way, you should have both options under your belt.

You are required to use OOP for this exercise. Don’t worry; the starter code below will do a lot of the heavy lifting for your first time around.

Sets

Another concept you’ll be practicing 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 can’t 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. For this exercise, you should look at set union and set difference in particular. You will find sets a valuable tool throughout the exercise.

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. 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 download the starter code and some test examples.

In bard.py, you’ll find four classes have been given to you:

Villager: A single villager who has a name and may be a bard and/or know some songs.

Song: A single song that has a title and may be known by some villagers.

Village: A village full of villagers, songs, and parties. This class should also handle input and general control.

Party: A party with attendees. This class is responsible for figuring out what happens during a party.

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. Finally, you have a run method that must take a filename and return a dictionary of the statistics keyed by name.

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

Testing

We have a thorough barrage of tests to which we’ll subject your code. Everything we’ll test has been discussed here, so no surprises — not that we’re going to spell out all the details. :)

That said, you can have a taste of the tests. The starter code includes 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.

Reminders

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

  • In particular, for the code we’ve given you, do not add or remove any parameters, change any parameters or return types, or change any type annotations.
• Please don’t add additional import statements.
• You can and should add helper functions to keep your code organized.
• You must work by yourself on this exercise.

Submission

Submit your work on MarkUs by Sep 29, 10:00PM.

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

If there’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?
No, they become a bard at the next party they attend where there’s a bard (if they ever attend such a party).