Tuples, dictionaries and sets

Lists hold values in order, found again by position. Many CCC problems instead need to pair two values together, look a value up by name instead of position, or ignore every repeat of a value. This lesson covers three more ways Python groups values: the tuple, the dict, and the set.

Pairing values with a tuple

A tuple literal groups values together with parentheses, such as (3, 4). The module on reading input already used this shape without naming it: a, b = ... unpacks a tuple's values into separate names.

1point = (3, 4)2x, y = point3print(point)4print(x, y)

(3, 4)
3 4

point holds (3, 4) as one value. x, y = point unpacks it into two names, the same way multiple assignment unpacked a split line. tuple() converts another sequence, such as a list, into a tuple.

parts = input().split()point = tuple(parts)print(point)

3 4

('3', '4')

tuple(parts) takes the list .split() produced and turns it into a tuple holding the same values, in the same order.

Looking up values by key with a dict

A dict pairs each key with a value, written {key: value, ...}. Reading d[key] looks up the value stored under that key, and assigning d[key] = value stores one, whether or not the key already existed.

1ages = {"Ana": 12, "Bo": 13}2ages["Cy"] = 113print(ages["Bo"])4print("Cy" in ages)5print("Dee" in ages)

13
True
False

ages["Bo"] reads 13, the value stored under "Bo". Assigning ages["Cy"] = 11 adds a new key. "Cy" in ages is True once that assignment has run, and "Dee" in ages is False, since no such key was ever stored.

A dict comprehension builds a dict in one line, written {key: value for name in sequence}.

words = input().split()lengths = {w: len(w) for w in words}print(lengths)

cat mouse ox

{'cat': 3, 'mouse': 5, 'ox': 2}

{w: len(w) for w in words} builds a dict pairing every word with its own length, all in one comprehension.

Testing membership and removing duplicates with a set

A set holds values with no duplicates and no order, built with set() or a set literal like {1, 2, 3}. An empty set needs set(), since {} alone means an empty dict instead.

1seen = set()2seen.add(3)3seen.add(3)4seen.add(5)5print(len(seen))6print(3 in seen)7unique = {int(x) for x in input().split()}8print(sorted(unique))

2 2 3 4 3

2
True
[2, 3, 4]

Adding 3 to seen twice still leaves only one 3 in it, so len(seen) is 2, not 3. 3 in seen is True, checked the same way as in on a dict's keys. {int(x) for x in input().split()} builds a set comprehension, keeping only one copy of each number the line held; sorting it afterward gives a predictable order to print.

Using a tuple as a dict key

A dict key has to be a value Python can hash. A list cannot be one. A list can change after it is stored, so its hash would no longer match. A tuple never changes once built, so it can be a key. This is exactly why the pairing shape from the start of this lesson matters, beyond just grouping two numbers together.

Suppose a problem gives you a set of grid coordinates already visited. You need to check a new (row, col) pair against it in one step. visited = set() starts empty. visited.add((row, col)) records one coordinate as a single tuple. (new_row, new_col) in visited checks the pair together, instead of checking the row and column separately. A dict works the same way: distances = {} can hold distances[(row, col)] = 3, pairing a whole coordinate with a value. This comes up constantly in grid and graph problems, where a single number never identifies a position on its own.

Sets and dicts as ways to prune duplicate work

A set's real value in a contest is not just "no duplicates" as a fact about the data. It changes what a program has to do. Checking whether a value has been seen before, using a plain list, means scanning every earlier value one at a time. That scan gets slower as the list grows. Checking the same thing against a set costs the same small amount of work, no matter how many values are already in it. A loop that adds each new value to a set, and skips it if it is already present, turns a slow duplicate-removal pass into a fast one, with no change to the surrounding logic.

Dictionaries earn their keep the same way. Whenever a problem asks "how many of X have I seen" or "what is the most recent Y for this key," a dict answers in one pass over the data. Both questions look, at first, like they need a second pass to answer. They do not, since every lookup and every update on a dict costs the same small amount, regardless of how much has been stored already.

Common mistakes with dicts and sets

Reading d[key] for a key that was never stored raises a KeyError and stops the program. A list index that is out of range fails differently, but it still fails. .get(key, default) is the fix whenever a key might be missing, exactly as the vote-counting example above uses it. Only use plain d[key] when you are certain the key is already there.

Iterating over a dict directly, as in for k in d:, walks its keys, not its values and not its pairs. Reach for d.values() when you only need the values. Reach for d.items() when you need both the key and the value together. Either one saves you from writing d[k] a second time inside the loop, just to fetch what .items() would have handed you directly.

Building a set or a dict comprehension from data that should keep its repeats is an easy slip. A set silently throws that information away the moment two equal values collide into one entry. If the order or the count of repeats matters to the problem, reach for a list instead. Use a set only when repeats are noise, not signal.

Counting with a dict, traced

(nothing printed yet)

c.get(v, 0) reads the count so far for v, falling back to 0 the first time that name appears, instead of raising a KeyError for a key that was never stored. Adding 1 and storing the result back grows that one name's count by one, leaving every other name's count untouched. Both presets read four votes and end with the same total count of votes, however they are split between names.

Recap

This lesson covered pairing values with a tuple, looking up and storing values by key with a dict, and testing membership and removing duplicates with a set. It also covered a dict comprehension, a set comprehension, and counting how many times each value appears with .get() for a default. The three problems below all look values up by key or check them against a small set of rules.