Associative containers in Python — exercises with durations, music genres and a song recommender (and the empty braces that were not a set)

I wanted to count how many different songs I had listened to in a day. It was crystal clear to me: a set, because sets do not store repeats. I started with empty braces, seen = {}, went through the history doing seen.add(song) and Python answered: AttributeError: 'dict' object has no attribute 'add'.

“Dict? But I made a set.” No. Empty braces {} create an empty dictionary, not a set, and dictionaries have no add. For an empty set you have to write set(). It is one of those bugs you hit once and never forget, and it is the first snippet of “What’s wrong here?”.

Today we practise with three exercises of increasing difficulty, three snippets to debug and a cheat sheet to take away. These exercises use the associative containers theory and review the practice. You can do them without those, but it will be harder.

How to use this article

1. Read the statement of a level and do not look at the solution yet.
2. Write your version, run it and compare your output with the expected one.
3. If you get stuck, look only at the 🔵 hint and try again.
4. When you finish, compare with the solution and pay attention to why it is written that way, not just that it gives the same output.

Level 1 · Basic: the durations

Statement. Start from the dictionary durations = {"Lights of Neon": 215, "Coffee at 3": 187} (title → seconds) and do, in this order:

1. Add "Pixel" with 176 seconds.
2. Change the duration of "Coffee at 3" to 190.
3. Remove "Lights of Neon" keeping its duration in a variable. Show the dictionary and that variable.
4. Show the duration of "March", which is not there, without any error: it has to be 0.
5. Show whether "Pixel" and "March" are in the dictionary.
6. Go through the dictionary in alphabetical order showing each song in minutes:seconds format (with two digits for the seconds) and, at the end, the total seconds.

Expected output:

{'Coffee at 3': 190, 'Pixel': 176} 215
0
True False
Coffee at 3: 3:10
Pixel: 2:56
Total: 366 seconds

Level 2 · Intermediate: genres and artists

Statement. You have the catalogue as a list of tuples (title, artist, genre):

SONGS = [
    ("Lights of Neon", "Marea Alta", "pop"),
    ("Coffee at 3", "Los Turnos", "indie"),
    ("Easy Sunday", "Noa Vela", "indie"),
    ("Kilometre 0", "Marea Alta", "pop"),
    ("Pixel", "Bit Bang", "electronic"),
    ("Way Back Home", "Lía Sur", "indie"),
    ("Below Zero", "Bit Bang", "pop"),
]

Write three functions:

• count_genres(songs): dictionary genre → number of songs.
• artists_by_genre(songs): dictionary genre → set of artists of that genre.
• most_varied(artists): receives the previous dictionary and returns the genre with the most different artists (in case of a tie, the first one to appear).

Show the count, the artists of each genre (genres in alphabetical order and artists sorted), the most varied genre and the artists that have songs both in pop and in electronic.

Expected output:

{'pop': 3, 'indie': 3, 'electronic': 1}
electronic: ['Bit Bang']
indie: ['Los Turnos', 'Lía Sur', 'Noa Vela']
pop: ['Bit Bang', 'Marea Alta']
Genre with most artists: indie
In pop and in electronic: ['Bit Bang']

Level 3 · Challenge: a song recommender

Statement. Each user has a set with their saved songs:

SAVED = {
    "ana": {"Lights of Neon", "Coffee at 3", "Pixel", "Easy Sunday"},
    "luis": {"Pixel", "Coffee at 3", "Way Back Home"},
    "sara": {"Easy Sunday", "Lights of Neon", "Coffee at 3", "Below Zero"},
    "pablo": {"March"},
}

Write three functions:

• affinity(a, b): the shared part of two sets, from 0 to 1: len(a & b) / len(a | b). If both are empty, 0.
• most_similar(user, saved): the other user with the most affinity. If nobody shares anything with them, None.
• recommend(user, saved): a tuple with the most similar user and the sorted list of their songs that user does not have yet. If there is nobody similar, (None, []).

Go through all the users showing their recommendation (or no recommendations) and, at the end, the affinity between Ana and Sara as a percentage.

Expected output:

ana: is similar to sara -> ['Below Zero']
luis: is similar to ana -> ['Easy Sunday', 'Lights of Neon']
sara: is similar to ana -> ['Pixel']
pablo: no recommendations
Affinity ana-sara: 60%

What’s wrong here?

Three snippets with one bug each. Before reading the explanation, do two things: predict whether it raises an error and, if it does not, what it prints.

Snippet 1

seen.py

history = ["Pixel", "March", "Pixel"]
seen = {}
for song in history:
    seen.add(song)
print(len(seen))

*Think about it before going on: we want to count the different songs. What does python3 seen.py print?*

Explanation. It is the bug from the beginning:

Traceback (most recent call last):
  File "seen.py", line 4, in <module>
    seen.add(song)
    ^^^^^^^^
AttributeError: 'dict' object has no attribute 'add'

{} creates an empty dictionary. The message says it clearly: the object is a 'dict', and dictionaries have no add method (in a dictionary you add with seen[key] = value). The empty braces belong to dictionaries because they arrived in the language before sets.

Fix. An empty set is created with set():

history = ["Pixel", "March", "Pixel"]
seen = set()               # a real empty set
for song in history:
    seen.add(song)         # the second "Pixel" is not added again
print(len(seen))

2

Snippet 2

favourites.py

ratings = {}
ratings[["Pixel", "Bit Bang"]] = 5
print(ratings)

Does it raise an error? What does it print? We want to rate a song identifying it by title and artist.

Explanation. There is an error:

Traceback (most recent call last):
  File "favourites.py", line 2, in <module>
    ratings[["Pixel", "Bit Bang"]] = 5
    ~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^
TypeError: unhashable type: 'list'

Unhashable means that object cannot be a key. Dictionary keys have to be immutable, and a list can change after being used as a key (with an append, for example). If that happened, Python would no longer know where it stored it, so it simply does not allow it.

Fix. A tuple stores the same and is immutable:

ratings = {}
ratings[("Pixel", "Bit Bang")] = 5      # a tuple can be a key
print(ratings)
print(ratings[("Pixel", "Bit Bang")])

{('Pixel', 'Bit Bang'): 5}
5

Snippet 3

search.py

songs = {"c01": "Lights of Neon", "c02": "Coffee at 3"}
if "Coffee at 3" in songs:
    print("I have it")
else:
    print("I don't have it")

Does it raise an error? What does it print? We want to know whether we have the song “Coffee at 3”.

Explanation. It does not raise an error, but the answer is wrong:

I don't have it

The song is there, but as a value. in on a dictionary only looks at the keys, which here are the codes "c01" and "c02". For Python, the question was “is there any key called Coffee at 3?”, and the correct answer is no.

Fix. Ask explicitly about the values:

songs = {"c01": "Lights of Neon", "c02": "Coffee at 3"}
if "Coffee at 3" in songs.values():     # search among the VALUES
    print("I have it")
else:
    print("I don't have it")

I have it

Solutions

Look at this section only when you have tried the exercise. If your code is different but gives the same output, it is also a valid solution.

Level 1 solution

durations.py

durations = {"Lights of Neon": 215, "Coffee at 3": 187}

durations["Pixel"] = 176                     # add a new pair
durations["Coffee at 3"] = 190               # change the value of a key that already exists
removed = durations.pop("Lights of Neon")    # remove it and keep its value
print(durations, removed)

print(durations.get("March", 0))             # key that is not there: 0, no error
print("Pixel" in durations, "March" in durations)

total = 0
for title in sorted(durations):              # the keys, in alphabetical order
    seconds = durations[title]               # we have the key: direct lookup
    total += seconds
    print(f"{title}: {seconds // 60}:{seconds % 60:02d}")
print("Total:", total, "seconds")

Why it is written this way:

• Lines 3 and 4 have exactly the same shape, durations[key] = value, but they do different things: the first one adds (Pixel did not exist) and the second one replaces (Coffee at 3 did).
• pop removes the pair and returns the value, so removed is 215. With del the pair would also disappear, but we would lose the value.
• get("March", 0) returns the default value because the key does not exist. With durations["March"] a KeyError would have jumped out.
• In the loop, sorted(durations) gives a list with the sorted keys, and since we have each key, we read its value directly with brackets. No need for get: we know the key exists, because we just took it from the dictionary itself.
• 190 seconds are 190 // 60 = 3 minutes and 190 % 60 = 10 seconds: 3:10. The total is 190 + 176 = 366.

Level 2 solution

genres.py

SONGS = [
    ("Lights of Neon", "Marea Alta", "pop"),
    ("Coffee at 3", "Los Turnos", "indie"),
    ("Easy Sunday", "Noa Vela", "indie"),
    ("Kilometre 0", "Marea Alta", "pop"),
    ("Pixel", "Bit Bang", "electronic"),
    ("Way Back Home", "Lía Sur", "indie"),
    ("Below Zero", "Bit Bang", "pop"),
]


def count_genres(songs):
    """Dictionary genre -> number of songs."""
    counts = {}
    for title, artist, genre in songs:
        counts[genre] = counts.get(genre, 0) + 1      # the usual counter
    return counts


def artists_by_genre(songs):
    """Dictionary genre -> set of artists (without repeats)."""
    result = {}
    for title, artist, genre in songs:
        if genre not in result:           # first time the genre appears
            result[genre] = set()         # its empty set
        result[genre].add(artist)         # the set already takes care of not repeating
    return result


def most_varied(artists):
    """Genre with the most different artists."""
    best = None
    for genre, artist_set in artists.items():
        if best is None or len(artist_set) > len(artists[best]):
            best = genre
    return best


print(count_genres(SONGS))
artists = artists_by_genre(SONGS)
for genre in sorted(artists):
    print(f"{genre}: {sorted(artists[genre])}")
print("Genre with most artists:", most_varied(artists))
print("In pop and in electronic:", sorted(artists["pop"] & artists["electronic"]))

Why it is written this way:

• The for of the first two functions unpacks each tuple into three variables, even though each function only uses some of them. If you wrote two variables, the unpacking would fail.
• count_genres is the counter with get(genre, 0) + 1. Pop and indie come out with 3 songs.
• artists_by_genre builds a dictionary of sets. It follows the same two steps as the dictionary of lists in the practice (make sure the set exists and then add), but now there is no need to check for repeats: Marea Alta appears twice in pop and the repeated add does nothing.
• That is why pop, with 3 songs, only has 2 artists (Marea Alta and Bit Bang), while indie has 3. The most varied genre is indie, even though both have the same number of songs.
• most_varied is the maximum-by-hand pattern, but comparing set sizes: len(artist_set) > len(artists[best]). It only keeps the name of the genre and looks up its set when it needs it.
• The last line is an intersection: Bit Bang has a pop song (Below Zero) and an electronic one (Pixel).

Level 3 solution

recommender.py

SAVED = {
    "ana": {"Lights of Neon", "Coffee at 3", "Pixel", "Easy Sunday"},
    "luis": {"Pixel", "Coffee at 3", "Way Back Home"},
    "sara": {"Easy Sunday", "Lights of Neon", "Coffee at 3", "Below Zero"},
    "pablo": {"March"},
}


def affinity(a, b):
    """Shared part of two sets, from 0 to 1 (0 if both are empty)."""
    union = a | b
    if not union:                       # an empty set is "false"
        return 0
    return len(a & b) / len(union)


def most_similar(user, saved):
    """Other user with the most affinity, or None if nobody shares anything."""
    best, best_affinity = None, 0
    for other, songs in saved.items():
        if other == user:               # not compared with themselves
            continue
        value = affinity(saved[user], songs)
        if value > best_affinity:       # with a strict >, affinity 0 never wins
            best, best_affinity = other, value
    return best


def recommend(user, saved):
    """(most similar user, their songs that this one does not have, sorted)."""
    other = most_similar(user, saved)
    if other is None:
        return None, []
    return other, sorted(saved[other] - saved[user])


for user in SAVED:
    other, listing = recommend(user, SAVED)
    if other is None:
        print(f"{user}: no recommendations")
    else:
        print(f"{user}: is similar to {other} -> {listing}")
print(f"Affinity ana-sara: {affinity(SAVED['ana'], SAVED['sara']):.0%}")

This is the map of affinities the program computes. Each row is a user, and in coral is the column that wins for that row:

Why it is written this way:

• affinity computes the union first and checks whether it is empty with if not union:. An empty set counts as false, so the condition is only met when both sets are empty. Without that check, we would divide by 0.
• Ana and Sara share 3 songs (Lights of Neon, Coffee at 3 and Easy Sunday) and between the two they have 5 different ones: 3 / 5 = 0.6, that is 60%.
• most_similar uses two variables at once, best and best_affinity, which are assigned together with a multiple assignment. The continue skips the user themselves: otherwise, everyone would be most similar to themselves (affinity 1).
• Starting best_affinity at 0 and comparing with > means an affinity of 0 never wins. Pablo shares nothing with anyone, so best stays None.
• Look at Luis’s row in the drawing: his affinity with Ana is 40% and with Sara, 17%. Ana wins, and the recommendation is what Ana has and Luis does not: ANA - LUIS, sorted.
• recommend always returns a two-element tuple, also when there is nobody similar (None, []). That way, the loop below can always unpack into other, listing without worrying about which case it is.
• The final loop goes through SAVED directly, that is, its keys: the names of the users.

Watch it step by step in Python Tutor

The bug in snippet 3 is much easier to understand live. Python Tutor runs the code line by line and draws the dictionary as a table with the keys on the left and the values on the right. Choose Python 3 and paste this program:

songs = {"c01": "Lights of Neon", "c02": "Coffee at 3"}
print("c02" in songs)
print("Coffee at 3" in songs)
print("Coffee at 3" in songs.values())
for code in songs:
    print(code, songs)

Expected output:

True
False
True
c01 Lights of Neon
c02 Coffee at 3

What to watch, step by step:

1. As soon as songs is created, Python Tutor draws two rows. Look at what is on the left ("c01", "c02"): those are the keys, the only thing in looks at.
2. The first check looks for "c02" in that left column and finds it: True.
3. The second one looks for "Coffee at 3" in the same column. Although you can see it in the table, it is in the right-hand column: False.
4. The third one uses .values(), which is exactly the right-hand column: now it is True.
5. In the final loop, watch how code takes the keys one by one and how songs jumps to the matching row to get the title.

Cheat sheet: Associative containers

The essentials in 30 seconds

• Dictionary: key: value pairs. You search by key, and searching by key is instant.
• **d[k] = v adds if the key is new and replaces if it already existed. Reading** a key that does not exist gives KeyError.
• **in and for look at the keys.** For values, .values(); for pairs, .items().
• **get(k, default)** reads without fear. The counter is d[k] = d.get(k, 0) + 1.
• Keys must be immutable: strings, numbers, tuples. Never lists.
• Set: unique elements with no order. Empty with set(), never with {}.
• Algebra: | union, & intersection, - difference, ^ symmetric.

Dictionary syntax

I want to…	Code	Result
Create empty	d = {} or dict()	{}
Create with data	{"Pixel": 176, "March": 198}	Dictionary with 2 pairs
From pairs	dict([("pop", 3), ("indie", 2)])	{'pop': 3, 'indie': 2}
Add or change	d["Pixel"] = 180	Creates or replaces
Read (sure it exists)	d["Pixel"]	The value or KeyError
Read without error	d.get("Pixel", 0)	The value or 0
Does the key exist?	"Pixel" in d	True / False
Does the value exist?	176 in d.values()	True / False
Remove and keep the value	d.pop("Pixel")	The removed value
Just remove	del d["Pixel"]	—
Number of pairs	len(d)	Integer
Go through keys	for k in d:	Keys in insertion order
Go through pairs	for k, v in d.items():	Unpacked tuples
Sorted keys	sorted(d)	List
Sum of the values	sum(d.values())	Number
Counter	d[k] = d.get(k, 0) + 1	Adds 1 to the key
Nested	d["c02"]["title"]	One bracket per level

Set syntax

I want to…	Code	Result
Create empty	set()	set()
Create with data	{"pop", "indie"}	Set of 2 elements
Remove repeats from a list	set(items)	Set
Add one	s.add("rock")	If already there, no change
Add several	s.update(["jazz", "funk"])	Adds each element
Remove (must be there)	s.remove("rock")	KeyError if missing
Remove (if there)	s.discard("rock")	Never raises an error
Union	a | b	What either of them has
Intersection	a & b	What both have
Difference	a - b	What a has that b does not
Symmetric difference	a ^ b	What they do not share
Subset	a <= b / a < b	True / False
Show in a fixed order	sorted(s)	Sorted list

Exercise templates

Counter (Levels 1 and 2):

counts = {}
for element in data:
    counts[element] = counts.get(element, 0) + 1

Dictionary of sets (or of lists) (Level 2):

result = {}
for title, artist, genre in songs:
    if genre not in result:
        result[genre] = set()          # or [] if you want a list
    result[genre].add(artist)          # or .append(…) with lists

Maximum by hand over a dictionary (Level 2):

best = None
for key, value in d.items():
    if best is None or value > d[best]:
        best = key

Affinity and recommendation with sets (Level 3):

def affinity(a, b):
    union = a | b
    if not union:
        return 0
    return len(a & b) / len(union)

recommended = sorted(saved[other] - saved[user])

Most common errors

Symptom	Likely cause
KeyError: 'Pixel'	You read a key that does not exist: use in or get
KeyError in a counter with +=	d[k] += 1 needs to read first: use d[k] = d.get(k, 0) + 1
KeyError when doing append	The key does not have its list yet: create it first (if k not in d: d[k] = [])
AttributeError: 'dict' object has no attribute 'add'	You created the empty set with {}: use set()
TypeError: unhashable type: 'list'	You use a list as a key or as a set element: use a tuple
in says False and the data is there	You search among the keys and it is a value: use .values()
RuntimeError: dictionary changed size during iteration	You add or delete keys while going through: go through list(d)
ValueError: too many values to unpack	You go through the dictionary without .items() and unpack into two variables
The set comes out in a different order each time	Sets have no order: show it with sorted
TypeError: unsupported operand type(s) for +: 'set' and 'set'	Union is written with |, not with +

Before handing in, ask yourself

1. Can any of the keys I read be missing? If so, do I protect it with in or with get?
2. Do I search by key (direct) or among the values (I have to go through)? Am I using in in the right place?
3. Are my empty sets created with set() and are my keys immutable?
4. Do I show sets with sorted so the output is always the same?

If you want to review the topic from the basics, go back to the associative containers theory.

Keep goingAll Python (en) articles

Did this article help you? Here is how you can support SergioLearns →