Keeping facts about one thing together
A mountain has a name and a height. Here are four of the highest mountains in Japan, and we want to print them from highest to lowest. A first attempt keeps the names in one list and the heights in another, so that position i in both lists describes the same mountain, and sorts the heights:
names = ['Kita', 'Aino', 'Fuji', 'Okuhotaka']
heights = [3193, 3189, 3776, 3190]
heights.sort(reverse=True)
for i in range(4):
print(names[i], heights[i])The heights come out in the right order, but the program says Kita is 3776 m high, which is the height of Fuji. Sorting moved the heights and left the names where they were, so position i no longer describes one mountain.
The fix is to make each mountain a single value that holds both facts. Then wherever a mountain moves, its name moves with it. A value built from several values is called compound data, and this lesson is about building it and working with it.
Records with named parts
A record is a compound value that describes one thing, with one named part, called a field, for each fact about it. In Python you define a kind of record with a data class: a class statement that names the new type, the line @dataclass above it, and the fields listed inside, each with its type after a colon. A class statement can hold much more than fields, but for a record this pattern is all you need.
Mountain('Fuji', 3776) builds a record, and fuji.name and fuji.height read its fields:
@dataclass
class Mountain:
name: str
height: int
fuji = Mountain('Fuji', 3776)
print(fuji.name, fuji.height)
print(fuji)
print(fuji == Mountain('Fuji', 3776))Python details
from dataclasses import dataclass brings dataclass in from Python's standard library, the way import sys brings in sys.
@dataclass writes the constructor, the function that Mountain(...) calls to build a record. It also writes the text print shows for a record, and ==, which compares two records field by field.
Python does not check the types after the colons; they record what each field should hold.
A data class is a type, as int and str are: you can keep Mountain values in a list, pass one to a function and return one. Here is the sorting program again with one list of records. Python doesn't know how to compare two mountains, and sort with no key stops with TypeError: '<' not supported between instances of 'Mountain' and 'Mountain', so the key says what to sort by:
@dataclass
class Mountain:
name: str
height: int
mountains = [Mountain('Kita', 3193), Mountain('Aino', 3189), Mountain('Fuji', 3776), Mountain('Okuhotaka', 3190)]
mountains.sort(key=lambda m: m.height, reverse=True)
for m in mountains:
print(m.name, m.height)Now every name stays with its height.
Records or tuples
A tuple per mountain, ('Fuji', 3776), would also have fixed the program. A tuple is compound data too. The difference is that its parts are numbered rather than named: m[1] doesn't say what it holds, while m.height does. With two parts that hardly matters. With four parts, read in a dozen places, the names keep a program readable, and the Data abstraction part below shows a bug that numbered parts make easy to write.
Tuples can do two things a plain data class can't. They compare part by part, so a list of tuples sorts with no key. And they are hashable, so a tuple can be a set element or a dictionary key, while putting a Mountain in a set stops with a TypeError saying the type is unhashable. Writing @dataclass(frozen=True) instead of @dataclass makes the records unchangeable, and then they can go in a set too.
So a tuple suits a small value used in one place, such as a sort key or a name to look up in a set, and a record suits a value that travels through several functions. Two problems to practise on: the first is the mountain program with input to read, and in the second, a set of (family name, given name) tuples finds whether two people share a name.
Choosing what a record holds
Once each thing in a problem is a record, the first decision is what one record should hold. In this problem the obvious record, a student's four scores, holds more than the answer needs and leaves out the student's id.
There are students with ids 1 to , given in order of id, and Thomas has id 1. Each student has four exam scores. The results table lists the students by the sum of their scores, highest first, and students with equal sums by smaller id first. Print Thomas's place in the table.
Constraints
- Each score is between 0 and 100
Sample 1 · Input
5 100 98 100 100 100 100 100 100 100 100 99 99 90 99 90 100 100 98 60 99
Output
2
Sample 2 · Input
6 100 80 90 99 60 60 60 60 90 60 100 60 60 100 60 80 100 100 0 100 0 0 0 0
Output
1
The table order depends only on the sum of the four scores, so a record keeps the total instead of the scores. Thomas is found by his id, but the input does not write the ids: student is the -th line, and sorting loses which line a record came from. When a fact is only a position in the input, such as an id, store it in the record before sorting.
The sort itself is a two-part rule: the key (-total, number) puts higher totals first and breaks a tie by the smaller id.
@dataclass
class Student:
total: int
number: int
n = int(input())
students = []
for i in range(n):
scores = list(map(int, input().split()))
students.append(Student(sum(scores), i + 1))
students.sort(key=lambda s: (-s.total, s.number))
for place in range(n):
if students[place].number == 1:
print(place + 1)The next problem also stores a position from the input, but here the records must not be sorted at all.
There are people numbered 1 to , seated in that order clockwise around a round table, so person sits next to person 1. Person has the name and the age ; no two share a name or an age. Starting from the youngest person, print everyone's name in clockwise seating order, one per line.
Constraints
Sample 1 · Input
5 alice 31 bob 41 carol 5 dave 92 ellen 65
Output
carol dave ellen alice bob
Sample 2 · Input
2 takahashi 1000000000 aoki 999999999
Output
aoki takahashi
A person is a name and an age, and the seat is the person's position in the input. Sorting by age would lose who sits next to whom, so the records stay in input order. The program finds the index of the youngest person and prints the names at positions for .
Data abstraction: constructors and selectors
Wherever a program needs a mountain's height, it writes m.height for a record or m[1] for a tuple. That reading code ends up all over a program, and it is where a change to the data hurts. Take a program that keeps mountains as tuples and prints them from highest to lowest:
mountains = [('Kita', 3193), ('Fuji', 3776), ('Aino', 3189)]
for m in sorted(mountains, key=lambda m: m[1], reverse=True):
print(m[0])It prints Fuji, Kita, Aino. Now each mountain also needs its country, and someone writes the tuples as ('Kita', 'Japan', 3193). The key m[1] now reads 'Japan', every mountain gets the same key, and the sort leaves them in input order: the program prints Kita, Fuji, Aino, with no error. To add the country safely, you would have to find every m[1] in the program and work out which ones meant the height.
Code all over the program knows how a mountain is stored. Data abstraction keeps that knowledge in one place. You decide the few operations a kind of data supports, write each as a function, and let the rest of the program use only those functions. A mountain needs a constructor, a function that builds it from its parts, and one selector per part, a function that reads that part.
def make_mountain(name, height):
return (name, height)
def mountain_name(m):
return m[0]
def mountain_height(m):
return m[1]
def second_highest(mountains):
ordered = sorted(mountains, key=mountain_height, reverse=True)
return mountain_name(ordered[1])
mountains = [make_mountain('Kita', 3193), make_mountain('Fuji', 3776), make_mountain('Aino', 3189)]
print(second_highest(mountains))Python details
key=mountain_height passes the selector itself as the sort key, the way key=len passes len.
second_highest never mentions positions 0 and 1; only the constructor and the two selectors know that a mountain is a tuple. To add the country, you change make_mountain and mountain_height, add a mountain_country selector, and second_highest stays as it is. Switching to the Mountain data class means rewriting the same three functions.
The line between the code that uses mountains only through these functions and the code that knows how a mountain is stored is an abstraction barrier. You have used lists from above such a barrier all along, through indexing, append and len, without knowing how a list lays out its elements in memory.
Linked lists: a first element and the rest
So far every field has held a number or a string. A field can also hold another record, even a record of its own type, and that lets a record with a fixed number of fields describe data of any size. The simplest example is a list built from two-part records. A linked list is either empty, or a first element together with the rest of the list, which is itself a linked list.
The list 3, 1, 4 has first element 3, and its rest is the linked list 1, 4. Each two-part record is a link.
@dataclass
class Link:
first: int
rest: 'Link | None'
nums = Link(3, Link(1, Link(4, None)))
print(nums.first)
print(nums.rest.first)
print(nums.rest.rest.first)
print(nums.rest.rest.rest)Python details
None stands for the empty list. The field type is written in quotes because the class Link does not exist yet while its own body is being read.
Reading element means following rest times, so nums.rest.rest.first is the element at index 2. A Python list reaches index in one step, while a linked list of elements takes 99,999 steps to reach its last one.
In return, a linked list grows at the front cheaply. Link(9, nums) makes the list 9, 3, 1, 4 in one step without touching the three existing links, while putting an element at the front of a Python list moves every element one place over. The two lists then share the links 3, 1 and 4.
For the lists in your own programs, Python's list is the better choice almost every time. The linked list is here for its shape: a function on it follows the two cases of its definition, as the next listing shows, and a tree, in the part after this one, is the same idea with several rests instead of one.
A linked list as boxes and arrows
Each link holds an element and an arrow to the rest of the list.
Recursion on a linked list
A linked list has two cases, empty or a first element with a rest, and so does every function that processes one. The empty list adds up to 0, and a non-empty list adds up to its first element plus the total of its rest, which is a smaller linked list that a recursive call can total.
@dataclass
class Link:
first: int
rest: 'Link | None'
def total(lst):
if lst is None:
return 0
return lst.first + total(lst.rest)
def doubled(lst):
if lst is None:
return None
return Link(2 * lst.first, doubled(lst.rest))
def build(values):
lst = None
for x in reversed(values):
lst = Link(x, lst)
return lst
nums = build([3, 1, 4, 1, 5])
print(total(nums))
print(total(nums.rest.rest))
print(total(doubled(nums)))Python details
lst is None asks whether lst is the empty list.
The second line totals the list 4, 1, 5, which is 10, because any rest of a linked list is a linked list too. total makes one call per link plus one for the empty list: calls for elements.
Recursion also builds linked lists. doubled returns the empty list for the empty list, and otherwise a new link holding twice the first element in front of the doubled rest, so the third line totals 6, 2, 8, 2, 10, which is 28.
Each new link goes in front of the list built so far, so build walks the values from last to first, and 3, added last, ends up in front.
Step through total on a linked list
Each call gets its own frame. In the first preset, which totals the list 3, 1, 4, frame f1's lst points at the whole list, f2's at its rest, and so on, until the fourth call receives the empty list.
Stop at the step where the last frame receives None. Every frame above it is still waiting, and none has added anything yet. The additions happen on the way back: the empty list returns 0, the frame on 4 returns 4, the frame on 1 returns 5, and f1 returns 8.
Trees: a label and a list of branches
A linked list gives each element one successor. Some data gives an element several, as a manager has several reports. A tree holds such data, and its definition is recursive too. A tree has a root label and a list of branches, and each branch is itself a tree. A tree with no branches is a leaf.
@dataclass
class Tree:
label: int
branches: list
def is_leaf(t):
return len(t.branches) == 0
t = Tree(3, [Tree(1, []), Tree(2, [Tree(1, []), Tree(1, [])])])
print(t.label)
print(len(t.branches))
print(t.branches[1].label)
print(is_leaf(t.branches[0]), is_leaf(t))Python details
A data class refuses [] as a default: branches: list = [] raises ValueError as soon as the class is defined. branches: list = field(default_factory=list), with field imported from dataclasses, gives each tree its own new list, where [] would be one list shared by every tree.
The tree t
The tree t drawn with its root at the top.
- the root: the node with no parent
- leaves: nodes with no branches
Each label sits at a node, and this tree has five. A node's branches lead to its children, and the node above a child is its parent. The depth of a node is the number of steps from the root down to it, so the two lowest leaves are at depth 2. The height of a tree is the largest depth of any node.
Tree-recursive functions
A function that processes a tree follows its definition, as total followed the definition of a linked list. For a leaf it answers directly. Otherwise it makes one recursive call per branch and combines their answers.
count_leaves returns 1 for a leaf and the sum over the branches otherwise. height returns 0 for a leaf, and otherwise one more than the tallest branch. To test these functions on trees larger than t, halves builds one of any size: its root label is , and unless is 1 its two branches are halves of and of . The tree t above is halves(3).
@dataclass
class Tree:
label: int
branches: list
def is_leaf(t):
return len(t.branches) == 0
def count_leaves(t):
if is_leaf(t):
return 1
count = 0
for b in t.branches:
count += count_leaves(b)
return count
def height(t):
best = 0
for b in t.branches:
best = max(best, 1 + height(b))
return best
def halves(n):
if n == 1:
return Tree(1, [])
return Tree(n, [halves(n // 2), halves(n - n // 2)])
for n in [3, 6, 1000]:
t = halves(n)
print(n, count_leaves(t), height(t))Every leaf of halves(n) has label 1, and the labels of a node's branches add up to its own label, so halves(n) has exactly leaves. Each split roughly halves the label, so the height is the number of halvings that take down to 1: 10 for , since .
Each node is reached along exactly one path from the root, so count_leaves makes one call per node: 1999 calls for the 1000 leaves and 999 inner nodes of halves(1000).
Trees given as a list of parents
Contest problems rarely give nested Tree values. They number the nodes 1 to and give each node's parent, with a value such as for the root, which has none. The program collects each node's children into a list, so children[p] lists the nodes whose parent is p, and a tree-recursive function takes a node number instead of a Tree.
A company has employees numbered 1 to . Each employee has at most one immediate manager, another employee, and there are no cycles of management. Employee is a superior of if is 's immediate manager, or a superior of 's immediate manager. The employees are split into groups for a party so that no group contains two people where one is a superior of the other. Print the smallest possible number of groups.
The first line holds . Line of the next lines holds , the immediate manager of employee , or if employee has none.
Constraints
- or , and
Sample · Input
5 -1 1 2 1 -1
Output
3
In the sample, employees 1 and 5 have no manager, 2 and 4 report to 1, and 3 reports to 2. The chain 1, 2, 3 needs three groups, because each of the three is a superior of the ones below. Three groups are also enough: put everyone at depth 0 in the first group, depth 1 in the second and depth 2 in the third. Two people at the same depth are never superiors of one another.
So the answer is the height of the tallest tree plus 1. The program calls height on every employee with no manager and keeps the largest result. A single chain of 2000 employees makes height recurse 2000 calls deep, past Python's default limit of 1000, so the program raises the limit with sys.setrecursionlimit.
sys.setrecursionlimit(10000)
n = int(input())
children = [[] for _ in range(n + 1)]
roots = []
for i in range(1, n + 1):
p = int(input())
if p == -1:
roots.append(i)
else:
children[p].append(i)
def height(v):
best = 0
for c in children[v]:
best = max(best, 1 + height(c))
return best
print(max(height(r) for r in roots) + 1)Python details
max(height(r) for r in roots) is the largest value of height(r) over all the roots.
The next problem uses the same children lists: a rooted tree is a spruce when every node that has children has at least 3 children that are leaves.
Common mistakes
Sorting by
(total, number)withreverse=Truewhen only the total should go from high to low.- Where it breaks
reverse=Truereverses the tie-break too. In the first sample of The Rank, Thomas and student 3 both have 398, student 3 goes first, and the program prints 3 instead of 2.- The fix
- Negate only the total: the key
(-total, number), or in C++ a comparator that compares totals with>and ids with<.
Forgetting the empty-list case in a linked-list function.
- Where it breaks
- Without
if lst is None: return 0,total(Link(4, None))callstotal(None), which evaluatesNone.firstand stops withAttributeError. In C++,nullptr->firstis undefined behavior; on most systems the program stops with a segmentation fault. - The fix
- Start every linked-list function with the empty case.
Building a linked list by prepending the values in input order.
- Where it breaks
- Reading 3, 1, 4 and doing
lst = Link(x, lst)for each gives the list 4, 1, 3, solst.firstis 4, not 3. - The fix
- Prepend the values from last to first, as
builddoes.
Counting tree height in nodes when the problem counts groups, or the other way round.
- Where it breaks
- On the Party sample,
height(1)is 2, the steps from 1 down to 3, but the chain 1, 2, 3 holds three people and needs 3 groups. - The fix
- Decide whether the answer counts steps or nodes along the longest chain, and add 1 when it counts nodes.
Recall A program stores mountains as tuples behind `make_mountain`, `mountain_name` and `mountain_height`. Which functions change if mountains become data classes?
Only those three. Every other function reads mountains through them, so it keeps working. A function that used m[1] directly would break.
Recall How many calls does `count_leaves` make on a tree with 7 nodes, 4 of them leaves?
Seven: one per node. The 4 leaves each return 1 at once, and the 3 inner nodes add up their branches' results.
Key terms
| Term | Meaning |
|---|---|
| compound data | A value built from several values. |
| record | A compound value with one named part per fact about one thing. |
| field | One named part of a record. C++ calls it a member. |
| data class | A Python class marked @dataclass that lists its fields. |
| struct | A C++ type that lists its members by type and name. |
| data abstraction | Using a kind of data only through a fixed set of functions. |
| constructor | A function that builds a value from its parts. |
| selector | A function that reads one part of a value. |
| abstraction barrier | The line between code that uses data through its functions and code that knows how it is stored. |
| linked list | Either empty, or a first element and the rest, which is a linked list. |
| tree | A root label and a list of branches, each of which is a tree. |
| leaf | A tree with no branches. |
| node | The place of one label in a tree; its branches lead to its children. |
