Corrected exercises: lists, dictionaries and the structure to choose, COMP 202

a) With append the list becomes [1, 2, [3, 4]], three elements, the third being a LIST. With extend it becomes [1, 2, 3, 4], four elements. append adds exactly one thing, whatever that thing is; extend walks its argument and adds each element. The difference shows up at once with len, which is 3 in the first case and 4 in the second, and it is the standard way of accidentally building a list of lists.

b) It leaves None, because append changes the list and returns nothing, and the assignment then throws the list away and stores that None. The next line that touches values raises TypeError, NoneType object is not subscriptable, or something equally puzzling. The correct line is values.append(5) on its own, with no assignment. Same story as sort in the functions set: a mutating call is a statement, not an expression.

c) values.remove(3) removes the first element whose VALUE is 3, and raises ValueError when there is none. del values[3] removes the element at POSITION 3, and raises IndexError when the list is shorter. values.pop(3) also removes the element at position 3, and additionally RETURNS it, which is what makes it the right call when the removed element is still needed. Confusing the value with the position is the classic here, and it is silent whenever the list happens to contain small integers.

d) It raises ValueError, 3 is not in list. The safe shape is to test first, if 7 in values: then read values.index(7); or to accept the exception and handle it. Note the asymmetry with strings, where find returns -1 and index raises: lists have only the raising version, so the membership test is the way to look before leaping.

e) values.append(x), values = values + [x], and values += [x]. The first is what a marker expects: it is the one that says add one element and nothing else, and it changes the list in place at constant cost. The second builds a brand new list of n+1 elements and rebinds the name, so it is quadratic inside a loop and it does NOT change the list the caller may still be holding. The third looks like the second and behaves like the first, since on a list the augmented assignment extends in place, which is exactly the kind of subtlety to avoid in an assignment.

a) b[0].append(9) changes a as well, because b[0] and a[0] are the SAME inner list: the slice copied the outer list only, so both lists point at the same two inner ones, and a becomes [[1, 2, 9], [3, 4]]. b.append([9]) does not touch a, because the outer lists really are two different objects: b gains a third element and a keeps two. That pair of results is the whole exercise, and it is why the word copy has to be qualified.

b) The module is copy and the call is deepcopy: import copy at the top, then b = copy.deepcopy(a). It walks the whole structure and rebuilds every level, so nothing at all is shared afterwards. There is also copy.copy, which is the shallow one and does exactly what the slice does.

c) b = list(a) and b = a.copy() are the other two. On a flat list of numbers all three, plus the slice, do the same thing, because the elements are immutable: sharing an int between two lists is undetectable, since nothing can change a 3 into a 4 in place. That is the real rule behind the whole chapter, and it explains why a shallow copy is enough far more often than not: only MUTABLE elements make the depth visible.

d) It needs a deep copy, and it costs one full traversal of the structure plus the memory to hold a second one. For a grid of a thousand by a thousand that is real money, which is the argument for the other design: return a new structure built by comprehension, [[f(v) for v in row] for row in grid], which allocates the same memory but does the work once instead of copying and then modifying. The one thing that is never acceptable is to promise a copy in the docstring and modify the argument.

e) Every row is the same list, so grid[0][0] = 1 shows up in all three rows and the grid prints as [[1, 0, 0], [1, 0, 0], [1, 0, 0]]. The multiplication repeated the REFERENCE three times, exactly as the slice shared the inner lists in question a). The correct build is grid = [[0] * 3 for r in range(3)], where the comprehension runs the inner expression once per row and therefore creates three distinct lists. The inner [0] * 3 is safe because its elements are immutable.

a) marks = {'Ana': 7.5, 'Ben': 6.0, 'Chen': 8.0}. Adding is an assignment to a key that does not exist yet, marks['Dan'] = 5.5, and changing is an assignment to one that does, marks['Ben'] = 6.5. That the two are written identically is deliberate, and it is also the reason a typo in a key adds an entry instead of reporting an error, which is worth remembering when a dictionary mysteriously grows.

b) marks['Dan'] raises KeyError, with the missing key as its message. marks.get('Dan') returns None and raises nothing. marks.get('Dan', 0) returns 0, the default given. The choice is the same one as between index and find on a string: the raising version is right when absence is a bug, the get version is right when absence is a normal case with a sensible answer, and the classic use of the second is the counting of the next exercise.

c) It walks over the KEYS, so for k in marks: print(k, marks[k]) prints the pairs; the more direct form is for k, v in marks.items(). The class average is sum(marks.values()) / len(marks), which reads as what it is. Note that len of a dictionary is its number of entries, and that iterating gives the keys in the order they were INSERTED, a guarantee since Python 3.7 that is worth knowing but not worth relying on for a sorted report.

d) TypeError, unhashable type: list. A dictionary computes a position from the key, so the key must never change afterwards, and Python enforces that by requiring an immutable type. A tuple can be a key, and that is the standard way of keying a grid by its coordinates, scores[(row, col)]. A float can be a key, though comparing floats makes it a bad idea. A list cannot, and neither can a dictionary.

e) It holds ONE entry, with the value of the last assignment: keys are unique by construction, and assigning to an existing key overwrites. That is exactly what makes the counting idiom work, since counts[word] = counts.get(word, 0) + 1 is meant to overwrite the previous count. It is also what makes a dictionary the wrong structure when several values must be kept per key, where the value has to become a LIST.

a) counts = {} before the loop, then for w in words: counts[w] = counts.get(w, 0) + 1. That single line is the whole idiom: get supplies the starting value 0 for a word never seen, the addition does the counting, and the assignment writes the result back. Reading it aloud gives the count of w, or zero if it is new, plus one.

b) for w in words: if w in counts: counts[w] = counts[w] + 1, else: counts[w] = 1. It is correct and it is four lines instead of one, with the number 1 written twice, once as the increment and once as the starting value, so a change of unit has to be made in two places. Submit the get version. There is no special case in it because the default IS the special case, handled by the call itself, and removing special cases is what makes code short in a useful way rather than a clever one.

c) sorted(counts.items(), key=lambda pair: pair[1], reverse=True). It returns a LIST of tuples, name and count, sorted by the second element of each; the dictionary itself is unchanged, and it has no order to change. Taking the top three is then a slice of that list, which is one more reason the sorting returns a list rather than a dictionary.

d) Nothing in the sort decides it beyond stability: Python's sort is stable, so tied items keep the order they had in the list handed to it, which is the insertion order of the dictionary, that is the order of FIRST appearance in the text. That is predictable, and it is a poor thing to rely on in a report. To make it explicit, sort on a pair, key=lambda p: (-p[1], p[0]), which ranks by decreasing count and then alphabetically.

e) The dictionary version reads each of the 10000 words once and does one lookup each, so about 10000 operations. The list version scans the list of words once for every distinct word, that is 2000 scans of 10000 elements, about 20 million comparisons: two thousand times more work for the same answer. That ratio is the whole reason the dictionary exists, and it is why the right question is not which structure can do this but which structure answers the question I keep asking.

a) unique = set(names) removes them, or unique = list(set(names)) to get a list back. What is lost is the ORDER, since a set has none, and also the count of each name. The order is recovered by sorting, sorted(set(names)), which gives alphabetical order, or by walking the original list and keeping the names not seen yet, which preserves the order of first appearance and is worth four lines when that order matters.

b) Turn the forbidden list into a set once, before the loop: forbidden = set(forbidden_list). Membership in a list is a scan, so the test costs up to 5000 comparisons and the whole job costs up to 50 million; membership in a set computes a position from the value itself and costs the same whatever the size, so the job costs 10000 lookups. One line, three orders of magnitude, and it is the single most useful optimisation of a first course.

c) Union with the vertical bar: {'Ana', 'Ben'} | {'Ben', 'Chen'} is {'Ana', 'Ben', 'Chen'}, three elements, since Ben is not counted twice. Intersection with the ampersand: the result is {'Ben'}, one element. Difference with the minus sign: {'Ana', 'Ben'} - {'Ben', 'Chen'} is {'Ana'}, and taken the other way round it is {'Chen'}, which is worth stating because the difference is the one operation of the three that is not symmetric.

d) First, a point does not change: making it a tuple says so, and any attempt to write to it fails immediately rather than corrupting a structure somewhere else. Second, a tuple can be a dictionary key, so a grid can be stored as scores[(row, col)] and a sparse board needs no nested lists at all. A third reason in passing: returning several values from a function already builds a tuple, so the type is met whether it is chosen or not.

e) Because a dictionary computes a position from the key when the entry is created, and that computation must give the same answer for ever. A tuple of immutable things cannot change, so it qualifies; a list can change, so it does not, and Python reports TypeError, unhashable type: list. A tuple that CONTAINS a list is refused as a key for the same reason, with the same error: the tuple itself is fixed, but what it holds is not, so the guarantee is broken one level down. Immutability, like copying, is a question of depth.

a) board = [['X', 'O', 'X'], ['O', 'X', ' '], ['O', ' ', 'X']]. board[0][2] is the top right square, 'X'. board[2][0] is the bottom left square, 'O'. The two indices are not symmetric even though the board is square, and the way to keep it straight is to read the first bracket as choosing a row from the outer list, which really does return a whole row.

b) The loop: empty = 0, then for row in board: for square in row: if square == ' ': empty = empty + 1. The comprehension does it in one line, empty = sum([1 for row in board for square in row if square == ' ']), where the two for clauses are written in the same order as the nested loops they replace. The answer here is 2. The double comprehension is worth knowing precisely because the order of its clauses trips people up: outer first, exactly as in the loops.

c) column = [row[1] for row in board], which gives ['O', 'X', ' ']. A row is one element of the outer list, so board[1] hands it over directly; a column has one element in each row, so it has to be gathered. That asymmetry is a property of the representation, not of the problem, and it is the reason a program that works on rows is usually written first and the column version arrives late and buggy.

d) For a row, all([square == 'X' for square in board[r]]), or the shorter board[r] == ['X', 'X', 'X'] since a list comparison compares element by element. For the main diagonal, all([board[i][i] == 'X' for i in range(3)]), the squares whose two indices are equal. The other diagonal uses board[i][2 - i], and writing that expression correctly is the whole difficulty of a tic tac toe assignment.

e) for row in board: print('|'.join(row)) prints three lines with a separator between the squares. print(board) prints the Python literal, brackets, quotes and commas included, which is the representation of the structure rather than a board: useful while debugging, never as the output of a program. Turning a structure into text for a human is a job of its own, and it belongs to the display half of the program, as in the functions set.

a) stock['B07'] is the whole inner record, a dict of three entries. stock['B07']['qty'] is 120, an int: the first bracket chooses the article, the second chooses the field. stock['B07']['name'][0] is 'p', a string of one character: the third bracket indexes the STRING that the second one returned. Reading a chain of brackets from left to right, naming the type after each one, is the technique the whole exercise rests on.

b) stock['B07']['qty'] = stock['B07']['qty'] - 3, or the augmented form with the minus equals sign. Adding an article is one assignment to a new key with a whole record as its value, stock['D02'] = {'name': 'ruler', 'qty': 25, 'price': 0.95}. Note that nothing checks the shape of that record: a typo in a field name creates a new field rather than reporting an error, and that is the price of a dictionary where a class would later give a guarantee.

c) total = 0, then for code in stock: total = total + stock[code]['qty'] * stock[code]['price']. The one line version is sum([a['qty'] * a['price'] for a in stock.values()]), which walks the VALUES since the codes are not needed. The result is $40 \times 3{,}25 + 120 \times 1{,}10 + 15 \times 6{,}40 = 130 + 132 + 96 = 358$ dollars. Iterating over values rather than over keys and indexing back is shorter and says what is meant.

d) With a loop: best = None, then for code in stock: if best is None or stock[code]['qty'] > stock[best]['qty']: best = code. With max: max(stock, key=lambda c: stock[c]['qty']), which walks the keys and compares them on the quantity, returning 'B07'. The loop version is the one to be able to write from scratch; the max version is the one to prefer once the key parameter of the functions set is understood, since it says find the code that maximises the quantity in one line.

e) Removing entries while iterating over the dictionary raises RuntimeError, dictionary changed size during iteration: the loop is walking the very structure being modified, which is the same rule as for a list, enforced here with a clear message instead of silently skipping elements. The repair is to collect first and delete after: empties = [c for c in stock if stock[c]['qty'] == 0], then for c in empties: del stock[c]. Building the list of keys first is the general shape, and it also makes the deletion easy to log or undo.

a) False for a list of lists. The slice copies the outer list only, so the inner objects are shared. The counterexample: a = [[1, 2]], b = a[:], then b[0].append(9), and a is now [[1, 2, 9]]. Correct version: a slice makes a SHALLOW copy, which is enough when the elements are immutable and not otherwise; copy.deepcopy duplicates every level.

b) False. append returns None, so the assignment stores None and the list is lost from that name onward. The counterexample: values = [1, 2], then values = values.append(3), then print(values) shows None, and len(values) raises TypeError. Correct version: values.append(3) as a statement of its own. The Python convention is that a call which changes something returns nothing.

c) False since Python 3.7. A dictionary keeps its keys in INSERTION order, and iterating twice gives the same order twice. The counterexample: build {'b': 1, 'a': 2} and iterate; 'b' comes first, not 'a', and not a different one each run. Correct version: the order is the order of first insertion, which is defined but is not sorted; a report that must be alphabetical sorts explicitly.

d) False, and this one costs seconds of runtime rather than marks. A list is scanned element by element, so the test costs up to n comparisons; a set computes a position from the value and answers in constant time. The counterexample is measurable: testing 10000 words against a list of 5000 does up to 50 million comparisons, against a set it does 10000 lookups. Correct version: for repeated membership tests, build a set once and test against it.

e) False in one case. A tuple that CONTAINS a list is itself unusable as a key, since what it holds can still change: {(1, [2]): 'x'} raises TypeError, unhashable type: list. The counterexample is that literal. Correct version: a tuple may be a key when everything inside it is immutable too, which is the usual case of coordinates and pairs of strings.

a) In both: the intersection, len(one & two), which is 2, namely Ben and Chen. In at least one: the union, len(one | two), which is 5, since the two shared names are counted once. In exactly one: the symmetric difference, len(one ^ two), which is 3, namely Ana, Dan and Eve. Note the arithmetic that must come out right: $4 + 3 = 7$ names read, $5$ distinct students, and the difference of 2 is exactly the size of the intersection.

b) A dictionary whose values are LISTS: marks = {}, then for name, value in records: marks[name] = marks.get(name, []) + [value]. Reading it aloud: the marks of that student so far, or an empty list, plus this one. The alternative with setdefault is marks.setdefault(name, []).append(value), which appends in place and is the version seen in most textbooks. What must not be written is marks[name] = value, which keeps only the last mark of each student and silently loses the first file.

c) averages = {name: sum(values) / len(values) for name, values in marks.items()}, a dictionary comprehension, or the same thing as a loop. For a student with one mark it gives that mark, which is arithmetically right and worth flagging in the report all the same: an average over one value carries no information about consistency, and a marker will expect the number of marks to appear beside it. The division is safe here because a name is only ever created by adding a mark, so no list is empty.

d) The two spellings are two different keys, so the student appears twice, each with half of the marks, and the class size is one too many. The fix belongs at the moment of READING, name = name.strip().lower(), so that everything downstream is already normalised. Applied at the end it is too late: the two entries have to be found and merged, which needs the very normalisation that would have prevented them, and any report already printed is wrong. Normalise at the border, once, as with the newline of the strings set.

e) for name in sorted(averages): print(f'{name:<10}{averages[name]:>6.2f}'). The dictionary alone cannot produce it because it has an order, the order of insertion, and that order is the order the files happened to be read in. Sorting returns a LIST of keys, which is exactly the point of the chapter: the dictionary answers what belongs to this key, and a list answers in what order, so a report that needs both uses both.

a) A list: marks = [], then marks.append(new_mark). The questions asked will be what was the third assignment, what is the average, what is the trend, and all three are questions about ORDER and position. A dictionary keyed by the assignment number would answer the first as well, and it is defensible if the assignments are numbered and some are missing, but it costs order for nothing when they arrive one after another.

b) A set: seen = set(), then if number in seen: reject, else seen.add(number). The question asked is have I seen this one, twenty thousand times, and that is the definition of a set. A list would answer the same question with up to twenty thousand comparisons each time, that is up to four hundred million in total, and would additionally allow the duplicate to be stored, which is precisely what must not happen.

c) A dictionary: capitals = {'Quebec': 'Quebec City', 'Ontario': 'Toronto'}. The question is what belongs to this province, which is the definition of a dictionary, and the keys are natural, unique and immutable. Two parallel lists, one of provinces and one of capitals, would answer it too, at the cost of keeping them in step for ever, and that is the design a dictionary exists to replace.

d) A tuple: position = (row, col), then visited[position] = True or visited.add(position). It must be a tuple because a dictionary key must be immutable and a list is not, and it is a natural fit anyway since a point has a fixed number of parts that never change. This is the case where the choice is forced by the language rather than by taste.

e) A dictionary whose values are lists: marks[name] = marks.get(name, []) + [value]. The outer question is what belongs to this student, so a dictionary; the inner question is how many and in what order, so a list. That combination is the answer whenever a key has several values, and recognising it early is what stops the alternative from being written, namely a list of pairs that has to be scanned in full for every lookup.