Tutorial 6: The reading club

The university library is starting a reading club. Readers specify the literary genres they enjoy. We want to store these preferences and suggest groups of people who share an interest.

We represent preferences using a dictionary: keys are reader names; values are lists of genres. Each list contains at least one genre and has no duplicates. Reader names are unique identifiers. Names and genres are nonempty strings without ; or newline characters, and with no leading or trailing whitespace. Internal spaces are allowed. Genres are written in lowercase.

Group rule: in Exercises 1–8, a reader may belong to several groups. Each group has a genre, and every member must enjoy that genre. The optional final exercise will introduce groups with no shared members.

Except in Exercise 2, your functions must not modify their input dictionaries or lists. Dictionaries are compared by their contents, not the order of their keys. The order of elements in a list matters. Unless specified otherwise, preserve the order in which readers or genres are encountered when iterating over the input.

Create a new program file called reading_club.py. Make sure you get the filename right, or else the testing code won’t work.

We will use two global variables for testing. Add the following line to your file reading_club.py:

preferences = {'Alice': ['crime', 'science fiction'], 'Basile': ['fantasy', 'science fiction'], 'Chloe': ['crime', 'historical'], 'Diego': ['science fiction', 'fantasy'], 'Emma': ['historical', 'crime'], 'Farid': ['poetry'], 'Gaelle': ['fantasy'], 'Hugo': ['crime', 'science fiction']}

small_club = {'Anna': ['crime', 'poetry'], 'Ben': ['poetry'], 'Cara': ['fantasy']}

Exercise 1: Printing Preferences

Define print_preferences, which prints one line per reader: their name, followed by a colon and a single space, then their genres separated by a comma and a single space.

Your function should start as follows:

def print_preferences(preferences):
    """Print each reader's name and preferred genres."""
    pass

In the console, we expect the following behavior:

In [1]: print_preferences({'Lina': ['historical']})
Lina: historical

In [2]: print_preferences({'Anne Marie': ['science fiction', 'crime']})
Anne Marie: science fiction, crime

In [3]: print_preferences(small_club)
Anna: crime, poetry
Ben: poetry
Cara: fantasy

The order of printed reader lines may differ, but preserve the order of genres on each line. An empty dictionary produces no lines.

Test your function by replicating these examples and printing the full club’s preferences. Run the tests for Exercise 1.

Save your file reading_club.py.

Exercise 2: Adding a Preference

Readers may join the club or add a genre to their preferences.

Define add_preference, which modifies the dictionary passed as an argument:

• if name is not a key, create an entry whose value is [genre];
• otherwise, append genre only if it is not already in the reader’s list.

The function returns None. Existing genres keep their order. Different readers must have independent lists.

def add_preference(preferences, name, genre):
    """Add a reader's preference in place, without duplicate genres."""
    pass

In [4]: new_club = {}

In [5]: add_preference(new_club, 'Alice', 'crime')

In [6]: new_club
Out[6]: {'Alice': ['crime']}

In [7]: add_preference(new_club, 'Alice', 'science fiction')

In [8]: new_club
Out[8]: {'Alice': ['crime', 'science fiction']}

In [9]: add_preference(new_club, 'Alice', 'crime')

In [10]: new_club
Out[10]: {'Alice': ['crime', 'science fiction']}

In [11]: add_preference(new_club, 'Basile', 'fantasy')

In [12]: add_preference(new_club, 'Alice', 'historical')

In [13]: new_club['Basile']
Out[13]: ['fantasy']

In [14]: new_club['Alice']
Out[14]: ['crime', 'science fiction', 'historical']

In [15]: add_preference(new_club, 'Anne Marie', 'science fiction')

In [16]: new_club['Anne Marie']
Out[16]: ['science fiction']

Save your file reading_club.py.

Exercise 3: Reading Preferences from a File

Rather than typing preferences by hand, we want to read registrations from text files. The format is as follows:

• a nonblank line contains exactly one name;genre pair;
• spaces or tabs may surround either field;
• blank lines, including lines containing only whitespace, must be ignored;
• readers may appear on several lines, including repeated occurrences of the same preference;
• neither field contains ;, and both are nonempty after stripping whitespace.

For example, readers_spaces.txt contains extra spaces, a whitespace-only line, and a repeated preference. readers.txt contains:

Alice;crime
Alice;science fiction
Basile;fantasy
Basile;science fiction
Chloe;crime
Chloe;historical
Diego;science fiction
Diego;fantasy
Emma;historical
Emma;crime
Farid;poetry
Gaelle;fantasy
Hugo;crime
Hugo;science fiction
Alice;crime

Define read_preferences, which returns a preferences dictionary. Keep each reader’s genres in their order of first appearance. Reuse add_preference to avoid duplicates.

def read_preferences(file_name):
    """Read registrations and return a reader-to-genres dictionary."""
    pass

In [17]: read_preferences('readers.txt') == preferences
Out[17]: True

In [18]: read_preferences('readers_empty.txt')
Out[18]: {}

In [19]: read_preferences('readers_single.txt')
Out[19]: {'Lina': ['poetry']}

In [20]: read_preferences('readers_spaces.txt')
Out[20]: {'Alice': ['crime', 'science fiction'], 'Farid': ['poetry']}

In [21]: read_preferences('readers_names.txt')
Out[21]: {'Anne Marie': ['science fiction', 'historical'], 'Leo': ['science fiction']}

In [22]: read_preferences('readers_ties.txt')
Out[22]: {'Zoe': ['poetry'], 'Yann': ['poetry'], 'Alice': ['crime'], 'Basile': ['crime']}

In [23]: len(read_preferences('readers.txt'))
Out[23]: 8

In [24]: read_preferences('readers.txt')['Alice'].count('crime')
Out[24]: 1

Save your file reading_club.py.

Exercise 4: Finding Common Genres

Define common_genres, which returns the genres enjoyed by both readers. Both names are keys in preferences; they may be equal. The result follows the genre order of name1, without duplicates.

def common_genres(preferences, name1, name2):
    """Return common genres in the order used by name1."""
    pass

In [25]: common_genres(preferences, 'Alice', 'Hugo')
Out[25]: ['crime', 'science fiction']

In [26]: common_genres(preferences, 'Alice', 'Basile')
Out[26]: ['science fiction']

In [27]: common_genres(preferences, 'Alice', 'Farid')
Out[27]: []

In [28]: common_genres(preferences, 'Emma', 'Emma')
Out[28]: ['historical', 'crime']

In [29]: common_genres(small_club, 'Anna', 'Ben')
Out[29]: ['poetry']

In [30]: common_genres(small_club, 'Ben', 'Cara')
Out[30]: []

In [31]: reverse_order = {'A': ['poetry', 'crime'], 'B': ['crime', 'poetry']}

In [32]: common_genres(reverse_order, 'A', 'B')
Out[32]: ['poetry', 'crime']

In [33]: common_genres(reverse_order, 'B', 'A')
Out[33]: ['crime', 'poetry']

Save your file reading_club.py.

Exercise 5: From Readers to Genres

To form groups, we need a dictionary whose keys are genres and values are lists of readers.

Define readers_by_genre, which constructs this new dictionary. In each list, readers must occur in the order in which they are encountered in preferences. Each reader occurs at most once per genre.

def readers_by_genre(preferences):
    """Return a dictionary mapping each genre to the readers who enjoy it."""
    pass

In [34]: readers_by_genre(small_club)
Out[34]: {'crime': ['Anna'], 'poetry': ['Anna', 'Ben'], 'fantasy': ['Cara']}

In [35]: readers_by_genre({'Lina': ['poetry', 'historical']})
Out[35]: {'poetry': ['Lina'], 'historical': ['Lina']}

In [36]: readers_by_genre({})
Out[36]: {}

In [37]: by_genre = readers_by_genre(preferences)

In [38]: by_genre['crime']
Out[38]: ['Alice', 'Chloe', 'Emma', 'Hugo']

In [39]: by_genre['science fiction']
Out[39]: ['Alice', 'Basile', 'Diego', 'Hugo']

In [40]: by_genre['fantasy']
Out[40]: ['Basile', 'Diego', 'Gaelle']

In [41]: by_genre['historical']
Out[41]: ['Chloe', 'Emma']

In [42]: by_genre['poetry']
Out[42]: ['Farid']

In [43]: readers_by_genre({'Zoe': ['poetry'], 'Alice': ['poetry']})
Out[43]: {'poetry': ['Zoe', 'Alice']}

The order of dictionary keys may differ from the displayed result. Do not alphabetically sort the reader lists.

Save your file reading_club.py.

Exercise 6: Keeping Large Enough Groups

The library will only run groups with at least minimum members. We assume minimum is an integer greater than or equal to 2.

Define form_groups, which returns a genre-to-readers dictionary containing only groups with at least minimum readers. Reuse readers_by_genre. Readers may still belong to more than one group.

def form_groups(preferences, minimum):
    """Return the genre groups containing at least minimum readers."""
    pass

In [44]: form_groups(small_club, 2)
Out[44]: {'poetry': ['Anna', 'Ben']}

In [45]: form_groups(small_club, 3)
Out[45]: {}

In [46]: form_groups({}, 2)
Out[46]: {}

In [47]: groups = form_groups(preferences, 3)

In [48]: groups == {'crime': ['Alice', 'Chloe', 'Emma', 'Hugo'], 'science fiction': ['Alice', 'Basile', 'Diego', 'Hugo'], 'fantasy': ['Basile', 'Diego', 'Gaelle']}
Out[48]: True

In [49]: form_groups(preferences, 2)['historical']
Out[49]: ['Chloe', 'Emma']

In [50]: len(form_groups(preferences, 2))
Out[50]: 4

In [51]: len(form_groups(preferences, 4))
Out[51]: 2

In [52]: form_groups(preferences, 5)
Out[52]: {}

In [53]: form_groups({'A': ['crime'], 'B': ['crime']}, 2)
Out[53]: {'crime': ['A', 'B']}

Test a group with exactly the required number of readers. Make sure the function does not remove readers or genres from preferences.

Save your file reading_club.py.

Exercise 7: Writing Groups to a File

Define write_groups, which writes a genre-to-readers dictionary to a text file. Write one group per line: its genre, then its readers, all separated by ;, with no extra spaces around separators. End every line with a newline.

def write_groups(groups, file_name):
    """Write one genre and its readers per line to file_name."""
    pass

In [54]: write_groups({'poetry': ['Anna', 'Ben']}, 'example_groups.txt')

In [55]: with open('example_groups.txt') as stream: print(stream.read(), end='')
poetry;Anna;Ben

In [56]: write_groups(form_groups(preferences, 3), 'example_groups.txt')

In [57]: with open('example_groups.txt') as stream: lines = stream.read().splitlines()

In [58]: sorted(lines)
Out[58]: ['crime;Alice;Chloe;Emma;Hugo', 'fantasy;Basile;Diego;Gaelle', 'science fiction;Alice;Basile;Diego;Hugo']

In [59]: write_groups({'science fiction': ['Anne Marie', 'Leo']}, 'example_groups.txt')

In [60]: with open('example_groups.txt') as stream: text = stream.read()

In [61]: text
Out[61]: 'science fiction;Anne Marie;Leo\n'

In [62]: write_groups({}, 'example_groups.txt')

In [63]: with open('example_groups.txt') as stream: text = stream.read()

In [64]: text
Out[64]: ''

Save your file reading_club.py.

Exercise 8: Putting Things Together

Define organize_session, which:

1. reads preferences from readers_file;
2. forms groups with at least minimum members;
3. writes the groups to groups_file;
4. prints the number of registered readers, then the number of suggested groups, using the exact labels below;
5. returns the groups dictionary.

def organize_session(readers_file, groups_file, minimum):
    """Read registrations, write and return the groups, and print a summary."""
    pass

In [65]: result = organize_session('readers.txt', 'example_groups.txt', 3)
Registered readers: 8
Suggested groups: 3

In [66]: result['fantasy']
Out[66]: ['Basile', 'Diego', 'Gaelle']

In [67]: result == form_groups(preferences, 3)
Out[67]: True

In [68]: result = organize_session('readers.txt', 'example_groups.txt', 5)
Registered readers: 8
Suggested groups: 0

In [69]: result
Out[69]: {}

In [70]: result = organize_session('readers_single.txt', 'example_groups.txt', 2)
Registered readers: 1
Suggested groups: 0

In [71]: result = organize_session('readers_empty.txt', 'example_groups.txt', 2)
Registered readers: 0
Suggested groups: 0

In [72]: with open('example_groups.txt') as stream: text = stream.read()

In [73]: text
Out[73]: ''

In [74]: result = organize_session('readers_spaces.txt', 'example_groups.txt', 2)
Registered readers: 2
Suggested groups: 0

In [75]: result = organize_session('readers_ties.txt', 'example_groups.txt', 2)
Registered readers: 4
Suggested groups: 2

In [76]: result == {'poetry': ['Zoe', 'Yann'], 'crime': ['Alice', 'Basile']}
Out[76]: True

Submit your file reading_club.py. Do not put console experiments or calls to input() at module level: importing your file must only define your functions. If you want to keep experiments in the file, place them inside if __name__ == '__main__':.

Exercise 9: Recommending Reading Partners

The proximity score of two readers is the number of genres they have in common.

Define recommend_partners, which returns a dictionary mapping other readers to their proximity scores with name. Do not include name itself or anyone with score zero. Assume name is a key in preferences. Reuse common_genres.

def recommend_partners(preferences, name):
    """Return other readers with positive proximity scores to name."""
    pass

In [77]: recommend_partners(preferences, 'Alice')
Out[77]: {'Basile': 1, 'Chloe': 1, 'Diego': 1, 'Emma': 1, 'Hugo': 2}

In [78]: recommend_partners(preferences, 'Farid')
Out[78]: {}

In [79]: recommend_partners(small_club, 'Ben')
Out[79]: {'Anna': 1}

In [80]: recommend_partners(small_club, 'Cara')
Out[80]: {}

In [81]: recommend_partners({'Lina': ['poetry']}, 'Lina')
Out[81]: {}

In [82]: recommend_partners({'A': ['crime', 'poetry'], 'B': ['poetry', 'crime']}, 'A')
Out[82]: {'B': 2}

Save your file reading_club.py.

Exercise 10: One Group per Reader

All groups now meet at the same time: each reader can join at most one group. We will apply the following rule:

1. Count how many available readers enjoy each genre.
2. Choose the genre with the largest count. Break ties by choosing the first genre in alphabetical order.
3. If this count is less than minimum, stop.
4. Otherwise, create a group with all available readers who enjoy this genre, then mark these readers as unavailable.
5. Repeat from Step 1, recomputing the counts after every group.

Define assign_readers. Return a pair (groups, remaining): a genre-to-readers dictionary and a list of readers who were not assigned to a group. Keep the original reader order within each group and within remaining. Insert the group keys into the result dictionary in the order in which the groups are created. Do not modify the original preferences or their lists. Assume minimum is an integer at least 2.

def assign_readers(preferences, minimum):
    """Return (groups, remaining) using the largest-available-group rule."""
    pass

In [83]: assigned, remaining = assign_readers(preferences, 3)

In [84]: assigned == {'crime': ['Alice', 'Chloe', 'Emma', 'Hugo'], 'fantasy': ['Basile', 'Diego', 'Gaelle']}
Out[84]: True

In [85]: remaining
Out[85]: ['Farid']

In [86]: assign_readers(small_club, 2)
Out[86]: ({'poetry': ['Anna', 'Ben']}, ['Cara'])

In [87]: assign_readers(small_club, 3)
Out[87]: ({}, ['Anna', 'Ben', 'Cara'])

In [88]: assign_readers({}, 2)
Out[88]: ({}, [])

In [89]: assign_readers({'Lina': ['poetry']}, 2)
Out[89]: ({}, ['Lina'])

In [90]: tied_club = read_preferences('readers_ties.txt')

In [91]: tied_groups, remaining = assign_readers(tied_club, 2)

In [92]: list(tied_groups)
Out[92]: ['crime', 'poetry']

In [93]: tied_groups['poetry']
Out[93]: ['Zoe', 'Yann']

In [94]: remaining
Out[94]: []

In [95]: recount_club = read_preferences('readers_recount.txt')

In [96]: recount_groups, remaining = assign_readers(recount_club, 2)

In [97]: recount_groups == {'crime': ['A', 'B', 'C'], 'poetry': ['E', 'F']}
Out[97]: True

In [98]: remaining
Out[98]: ['D']

In tied_club, poetry is encountered first, but crime must be selected first because of the alphabetical tie-break. In recount_club, fantasy initially has three candidates, but only D is still available after the crime group is formed. No fantasy group can therefore be created.

Test that each original reader appears exactly once, either in one group or in remaining. Verify that every group’s members share its genre and that each group has enough members. Check the alphabetical tie-break and recounting examples.

This rule makes a local choice at each step. It does not guarantee that as many readers as possible will be assigned to groups. Implement the specified rule; you do not need to find an optimal partition.

Save your file reading_club.py.