9c. Prof. Rosenthal’s Review

9c. Prof. Rosenthal’s Review#

A review of Chapter 9: Lists, for students who have already studied the chapter. Use the two lists under Concepts covered as a checklist (click a list’s title to hide it), then work through the Questions, which go from easy to hard. Each question has a suggested answer under Answer. Try the question first, then open the Answer.

Run this page on Colab

Concepts covered#

Python Syntax and Semantics

Creating lists

This creates a list of the values in the brackets, in order:
```
[VALUE1, VALUE2, VALUE3]
```
For example, this makes cheeses refer to a list of three strings:
```
cheeses = ['Cheddar', 'Edam', 'Gouda']
```
The elements of a list can have any type, and different types in one list. A list can be an element of another list: ['spam', 2.0, 5, [10, 20]] has a string, a float, an integer and a list.
[] is an empty list.
len(LIST) returns the number of elements in the list. A nested list counts as one element: len(['spam', 2.0, 5, [10, 20]]) is 4, and len([]) is 0.
list(SEQUENCE) returns a new list with the elements of the sequence. The elements of a string are its characters: list('spam') is ['s', 'p', 'a', 'm'].

Indexes and slices

LIST[INDEX] is the element at that index. The first element has index 0, and a negative index counts back from the end: ['a', 'b', 'c'][0] is 'a', and ['a', 'b', 'c'][-1] is 'c'. Any integer expression can be an index.
Reading or writing an element that does not exist, such as ['a', 'b', 'c'][3], is an IndexError.
Lists are mutable. This replaces the element at INDEX with VALUE:
```
LIST[INDEX] = VALUE
```
For example, this changes the second element of numbers from 123 to 17:
```
numbers = [42, 123]
numbers[1] = 17
```
LIST[START:END] returns a new list with the elements from index START up to END minus 1: ['a', 'b', 'c', 'd'][1:3] is ['b', 'c']. Without START the slice starts at the beginning, and without END it goes to the end: ['a', 'b', 'c', 'd'][2:] is ['c', 'd'].
LIST[:] and list(LIST) return a copy of the list: a new list with the same elements.
VALUE in LIST is True if the value is an element of the list. It does not look inside nested lists: 10 in ['spam', [10, 20]] is False.

Operators and built-in functions

LIST1 + LIST2 returns a new list with the elements of both lists: [1, 2] + [3, 4] is [1, 2, 3, 4]. Neither list changes.
LIST * SOME_INTEGER returns a new list with the elements repeated: ['spam'] * 3 is ['spam', 'spam', 'spam'].
No other arithmetic operators work with lists.
sum(LIST) adds up the elements, and min(LIST) and max(LIST) return the smallest and the largest element: sum([3, 1, 4]) is 8, and max([3, 1, 4]) is 4.

List methods

LIST.append(VALUE) adds the value to the end of the list.
LIST.extend(OTHER_LIST) adds all the elements of OTHER_LIST to the end of the list.
LIST.pop(INDEX) removes the element at that index, and returns it.
LIST.remove(VALUE) removes the first element that is equal to the value. If the value is not in the list, it is a ValueError.
These methods change the list. append, extend and remove return None. String methods are the opposite: they return a new string and do not change the original.
So t = t.remove(3) is a mistake: it makes t refer to None. After it, t.remove(2) is an AttributeError, because None has no attribute remove.

Lists and strings

STRING.split() returns a list of the words in the string (the parts between whitespace: spaces, tabs and newlines): 'pining for the fjords'.split() is ['pining', 'for', 'the', 'fjords'].
STRING.split(DELIMITER) splits the string at each DELIMITER instead: 'ex-parrot'.split('-') is ['ex', 'parrot'].
DELIMITER.join(LIST_OF_STRINGS) returns one string with the elements of the list, with DELIMITER between them: ' '.join(['pining', 'for', 'the', 'fjords']) is 'pining for the fjords'. With the empty string as the delimiter, nothing goes between them: ''.join(['a', 'b', 'c']) is 'abc'.
STRING.strip(CHARACTERS) returns a new string without those characters at its beginning and end: 'plumage!'.strip('!') is 'plumage'.
open(FILE_NAME).read() returns the whole file as one string. open(FILE_NAME).read().split() is a list of the words in the file.

Looping through a list

This runs the body once for each element of the list, in order, with the loop variable referring to that element:
```
for LOOP_VARIABLE in LIST:
    BODY
```
For example, this displays Cheddar, Edam and Gouda on separate lines:
```
for cheese in ['Cheddar', 'Edam', 'Gouda']:
    print(cheese)
```
A loop through an empty list never runs the body.

To make a list in a loop, start with an empty list and append to it:

NEW_LIST = []
for LOOP_VARIABLE in SEQUENCE:
    NEW_LIST.append(VALUE)

Sorting and reversing

sorted(SEQUENCE) returns a new list with the elements in increasing order. The original does not change. It works with any sequence, also a string: sorted('cab') is ['a', 'b', 'c'], and ''.join(sorted('cab')) is 'abc'.
reversed(SEQUENCE) returns the elements in reverse order, as a reversed object. Use list or join to get a list or a string: list(reversed([1, 2, 3])) is [3, 2, 1], and ''.join(reversed('parrot')) is 'torrap'.

Objects, equality and aliasing

A == B is True if A and B have the same value. A is B is True if A and B refer to the same object.
Each list display ([...]) makes a new list object: [1, 2, 3] == [1, 2, 3] is True, but [1, 2, 3] is [1, 2, 3] is False.
b = a does not copy the object: it makes b refer to the same object as a. If the object is a list, a change made with one name is seen with the other name. For example, after this code a is [5, 2, 3]:
```
a = [1, 2, 3]
b = a
b[0] = 5
```
When a list is passed to a function, the parameter refers to the same list. If the function changes the list, the caller sees the change after the function returns.

Definitions, etc.

Definitions

DEFINITION: A list is an object that contains a sequence of values.
DEFINITION: An element is one of the values in a list or another sequence.
DEFINITION: A nested list is a list that is an element of another list.
DEFINITION: An empty list is a list with no elements, [].
DEFINITION: A mutable object can be changed; an immutable object, such as a string, cannot. Lists are mutable.
DEFINITION: A delimiter is a character or string that shows where a string is split, or what goes between the strings that join joins.
DEFINITION: Two objects are equivalent if they have the same value (==).
DEFINITION: Two objects are identical if they are the same object (is). Identical objects are always equivalent; equivalent objects are not always identical.
DEFINITION: A reference is the association between a variable and its value (an object).
DEFINITION: An object is aliased if more than one variable refers to it.
DEFINITION: An attribute is one of the named values (variables or methods) associated with an object.

Other ideas

Do not use list as a variable name, because it is the name of a built-in function.
Read a file once and keep its words in a list, instead of reading the file each time you search it.
Aliasing is useful, but it causes errors that are difficult to find. When you work with mutable objects, it is safer to avoid aliasing (for example, make a copy with [:]). For immutable objects such as strings, aliasing is almost never a problem.
Passing a list to a function makes an alias: the parameter and the caller’s variable refer to the same list.
Most list methods change the list and return None. Do not assign their result to the list variable.
If you see an AttributeError that says 'NoneType' object has no attribute, look back through the program for a list method whose result was assigned.

Questions#

The questions use lists, list methods, split and join, sorted, and aliasing. One question reads words.txt, a list of about 114,000 English words, one per line, in alphabetical order (the first two are aa and aah).

The setup cell below downloads words.txt.

from os.path import basename, exists

def download(url):
    filename = basename(url)
    if not exists(filename):
        from urllib.request import urlretrieve

        local, _ = urlretrieve(url, filename)
        print("Downloaded " + str(local))
    return filename

download('https://raw.githubusercontent.com/AllenDowney/ThinkPython/v3/words.txt');

Summary and questions by Prof. Y. Rosenthal, based on Think Python: 3rd Edition by Allen B. Downey. Text license: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International

Question 1 (easy): what is displayed?#

Predict what this code displays, then open the Answer to check.

t = ['spam', 2.0, 5, [10, 20]]
print(len(t), t[0], t[-1])
print(t[3][1], 10 in t, 5 in t)

Answer

4 spam [10, 20]
20 False True

The nested list [10, 20] counts as one element, so len(t) is 4. t[0] is the first element, and t[-1] is the last element, which is the nested list. t[3] is the nested list, so t[3][1] is the element at index 1 of the nested list: 20. in does not look inside the nested list: 10 in t is False, but 5 in t is True.

Question 2 (easy): what is displayed?#

letters = ['a', 'b', 'c', 'd', 'e']
print(letters[1:3], letters[:2], letters[3:])
print([1, 2] + [3], [0] * 3)
print(sum([3, 1, 4]), min([3, 1, 4]), max(['pear', 'apple', 'fig']))

Answer

['b', 'c'] ['a', 'b'] ['d', 'e']
[1, 2, 3] [0, 0, 0]
8 1 pear

A slice includes the element at the first index, but not the element at the second index: letters[1:3] has the elements at indexes 1 and 2. Without the first index, a slice starts at the beginning; without the second, it goes to the end. + joins two lists into a new list, and * repeats the elements of a list. max of a list of strings is the string that comes last in alphabetical order: max(['pear', 'apple', 'fig']) is 'pear'.

Question 3 (easy): what is displayed?#

t = ['a', 'b', 'c']
t.append('d')
t.extend(['e', 'f'])
print(t)
x = t.pop(1)
t.remove('e')
print(x, t)

Answer

['a', 'b', 'c', 'd', 'e', 'f']
b ['a', 'c', 'd', 'f']

append adds one element to the end of the list, and extend adds each element of its argument. pop(1) removes the element at index 1 and returns it, so x is 'b'. remove('e') removes the element 'e', wherever it is. All four methods change the list t itself.

Question 4 (easy): what is displayed?#

s = 'pining for the fjords'
words = s.split()
print(words, len(words))
print('-'.join(words))
print(list('abc'), 'ex-parrot'.split('-'))

Answer

['pining', 'for', 'the', 'fjords'] 4
pining-for-the-fjords
['a', 'b', 'c'] ['ex', 'parrot']

split with no argument splits the string at the spaces, so words is a list of 4 strings. join is a string method: it is called on the delimiter ('-'), and it puts the delimiter between the elements of the list. list makes a list of the characters of a string, and split('-') splits at each hyphen instead of at the spaces. A list is displayed with the quotes around its strings.

Question 5 (easy): write a function#

Write a function called squares that takes a non-negative integer n and returns a list of the squares of the integers from 1 to n.

Start from this header (replace ... with the body):

def squares(n):
    ...

Examples

print(squares(4))

[1, 4, 9, 16]

print(squares(1), squares(0))

[1] []

Answer

Start with an empty list, and append one square each time through the loop:

def squares(n):
    result = []
    for i in range(n):
        result.append((i + 1) ** 2)
    return result

Then try: print(squares(4)).

range(n) produces 0 to n - 1, so add 1 to i before squaring it. With n equal to 0, the loop body never runs, and the function returns the empty list.

Question 6 (easy): what is displayed?#

t = [[1, 2], [3], []]
for inner in t:
    print(len(inner), sum(inner))
print(len(t))
for x in []:
    print('never')

Answer

The loop variable inner refers to each element of t in turn, and each element is a list. The sum of an empty list is 0. t has 3 elements: the empty list is an element too. The last loop goes through an empty list, so its body never runs.

Question 7 (medium): what is displayed?#

scramble = ['c', 'a', 'b']
result = sorted(scramble)
print(result, scramble)
print(sorted('banana'))
print(''.join(sorted('banana')))
print(sorted([3, 10, 2]), sorted(['3', '10', '2']))

Answer

['a', 'b', 'c'] ['c', 'a', 'b']
['a', 'a', 'a', 'b', 'n', 'n']
aaabnn
[2, 3, 10] ['10', '2', '3']

sorted returns a new list; the original list scramble does not change. sorted works with any sequence: for a string, it returns a list of the characters in order. join with the empty string as the delimiter makes one string of them again. Numbers are sorted by their value, but strings are sorted in alphabetical order, character by character: '10' < '2' is True, because '1' comes before '2'.

Question 8 (medium): what is displayed?#

a = [1, 2, 3]
b = [1, 2, 3]
c = a
d = a[:]
print(a == b, a is b)
print(a == c, a is c)
print(a == d, a is d)

Answer

True False
True True
True False

== checks whether two lists have the same elements (they are equivalent), and is checks whether they are the same object (identical).

a and b were made by two list displays, so they are two different objects with the same elements.
c = a does not make a new list: c refers to the same object as a.
a[:] is a copy: a new list with the same elements.

Question 9 (medium): what is displayed?#

a = [1, 2, 3]
b = a
c = list(a)
b[0] = 5
b.append(4)
c[1] = 7
print(a)
print(b)
print(c)

Answer

[5, 2, 3, 4]
[5, 2, 3, 4]
[1, 7, 3]

a and b refer to the same list (it is aliased), so the changes made with b are seen with a too. list(a) makes a new list, so c is a copy: changing c does not change a, and changing a does not change c.

Question 10 (medium): what is displayed?#

word = 'plumage!'
new_word = word.strip('!')
t = [1, 2, 3]
new_t = t.remove(3)
print(word, new_word)
print(t, new_t)

Answer

plumage! plumage
[1, 2] None

String methods and list methods work in opposite ways:

strip does not change word (strings are immutable): it returns a new string, new_word.
remove changes the list t itself, and returns None. So new_t refers to None.

So t = t.remove(3) would be a mistake: it would make t refer to None. To remove the element, call remove without an assignment:

t = [1, 2, 3]
t.remove(3)
print(t)

[1, 2]

Question 11 (medium): what happens?#

Each part has one mistake. Predict the error for each, then open the Answer to check.

Part a

t = [1, 2, 3]
t = t.remove(3)
t.remove(2)

Part b

t = ['a', 'b', 'c']
t.remove('d')

Part c

t = ['a', 'b', 'c']
print(t[3])

Part d

t = [1, 2]
t = t + 3

Answer

Part a: remove returns None, so after the second line t refers to None, not to a list. None has no method remove, so the third line is an AttributeError.

      1 t = [1, 2, 3]
      2 t = t.remove(3)
----> 3 t.remove(2)

AttributeError: 'NoneType' object has no attribute 'remove'

Part b: 'd' is not in the list, so remove gives a ValueError.

      1 t = ['a', 'b', 'c']
----> 2 t.remove('d')

ValueError: list.remove(x): x not in list

Part c: The list has 3 elements, at indexes 0, 1 and 2. There is no element at index 3, so this is an IndexError.

      1 t = ['a', 'b', 'c']
----> 2 print(t[3])

IndexError: list index out of range

Part d: + joins a list only to another list, not to an integer, so this is a TypeError. To add the number 3 to the end of t, write t = t + [3] or t.append(3).

      1 t = [1, 2]
----> 2 t = t + 3

TypeError: can only concatenate list (not "int") to list

Question 12 (medium): what is displayed?#

def pop_first(lst):
    return lst.pop(0)

letters = ['a', 'b', 'c', 'd']
first = pop_first(letters)
second = pop_first(letters)
print(first, second)
print(letters)

Answer

a b
['c', 'd']

When letters is passed to pop_first, the parameter lst refers to the same list as letters. Each call removes the first element of that list and returns it. So after the two calls the list has lost its first two elements, and letters shows the change.

Question 13 (medium): write a function#

Write a function called acronym that takes a string of words separated by spaces and returns a string of the first letters of the words, in uppercase. Strings have an upper method: 'png'.upper() is 'PNG'.

Start from this header (replace ... with the body):

def acronym(phrase):
    ...

Examples

print(acronym('portable network graphics'))

PNG

print(acronym('as soon as possible'), acronym('Python'))

ASAP P

Answer

Use split to get a list of the words, then take the first letter of each word:

def acronym(phrase):
    result = ''
    for word in phrase.split():
        result += word[0].upper()
    return result

Then try: print(acronym('portable network graphics')).

Another way: make a list of the letters, then use join with the empty string as the delimiter:

def acronym(phrase):
    letters = []
    for word in phrase.split():
        letters.append(word[0])
    return ''.join(letters).upper()

Question 14 (medium): write a function#

Write a function called running_totals that takes a list of numbers and returns a new list in which each element is the sum of the numbers up to and including that position. The function must not change the list it gets.

Start from this header (replace ... with the body):

def running_totals(numbers):
    ...

Examples

print(running_totals([1, 2, 3, 4]))

[1, 3, 6, 10]

print(running_totals([5, -5, 2]), running_totals([]))

[5, 0, 2] []

Answer

Keep a total, and append it to the new list after each number:

def running_totals(numbers):
    result = []
    total = 0
    for x in numbers:
        total += x
        result.append(total)
    return result

Then try: print(running_totals([1, 2, 3, 4])).

Another way: for each index i, the element is the sum of the slice from the beginning up to index i:

def running_totals(numbers):
    result = []
    for i in range(len(numbers)):
        result.append(sum(numbers[:i + 1]))
    return result

The second way adds up the numbers again for each element, so it is slower for long lists.

Question 15 (medium): what is displayed?#

words.txt has one English word per line, in lowercase. Predict what this code displays (you cannot know the number of words, but predict the rest).

word_list = open('words.txt').read().split()
print(len(word_list))
print(word_list[:3], word_list[-1])
print('python' in word_list, 'Python' in word_list)

Answer

113783
['aa', 'aah', 'aahed'] zymurgy
True False

read returns the whole file as one string, with a newline after each word. split with no argument splits at any whitespace, newlines too, so word_list is a list of the words, without the newlines. The words are in alphabetical order, so word_list[:3] is the first three words and word_list[-1] is the last word. The words in the file are in lowercase, so 'Python' is not in the list.

This is faster than reading the file each time you need to search it: read it once, and keep the list.

Question 16 (hard): what is displayed?#

def add_zero(lst):
    lst.append(0)

def add_one(lst):
    lst = lst + [1]

numbers = [5]
add_zero(numbers)
add_one(numbers)
print(numbers)

Answer

[5, 0]

In both functions, the parameter lst first refers to the same list as numbers.

add_zero changes that list with append, so numbers shows the change.
In add_one, lst + [1] makes a new list, and the assignment makes the local variable lst refer to it. The list that numbers refers to does not change, and the new list is lost when the function returns.

To use +, return the new list and assign the result:

def add_one(lst):
    return lst + [1]

numbers = [5]
numbers = add_one(numbers)
print(numbers)

[5, 1]

Question 17 (hard): what is displayed?#

row = [0, 0]
grid = [row, row]
grid[0][1] = 5
print(grid)
print(row)
copies = [row[:], row[:]]
copies[0][0] = 7
print(copies)

Answer

[[0, 5], [0, 5]]
[0, 5]
[[7, 5], [0, 5]]

Both elements of grid refer to the same list, row: the list is aliased three times. So grid[0][1] = 5 changes row, and the change is seen in both elements of grid.

row[:] makes a copy each time, so the two elements of copies are two different lists. Changing one of them does not change the other or row.

Question 18 (hard): write a function#

Write a function called flatten that takes a list of lists and returns a new list with all the elements of the inner lists, in order.

Start from this header (replace ... with the body):

def flatten(nested):
    ...

Examples

print(flatten([[1, 2], [3], [], [4, 5]]))

[1, 2, 3, 4, 5]

print(flatten([['a'], ['b', 'c']]), flatten([]))

['a', 'b', 'c'] []

Answer

extend adds all the elements of a list to the end of another list:

def flatten(nested):
    result = []
    for inner in nested:
        result.extend(inner)
    return result

Then try: print(flatten([[1, 2], [3], [], [4, 5]])).

Another way, with a loop inside a loop:

def flatten(nested):
    result = []
    for inner in nested:
        for element in inner:
            result.append(element)
    return result

result.append(inner) would be a mistake: append adds its argument as one element, so the result would be a copy of the list of lists.

Question 19 (hard): write a function#

Write a function called remove_all that takes a list t and a value, and removes every element of t that is equal to the value. The function changes the list t and returns None.

Start from this header (replace ... with the body):

def remove_all(t, value):
    ...

Examples

numbers = [1, 1, 2]
remove_all(numbers, 1)
print(numbers)

[2]

letters = ['a', 'b', 'a', 'a']
remove_all(letters, 'a')
print(letters)

['b']

Answer

remove removes only the first element that is equal to its argument, so call it once for each element that is equal to the value. Loop through a copy of the list (t[:]), because the loop must not skip elements when remove changes t:

def remove_all(t, value):
    for x in t[:]:
        if x == value:
            t.remove(x)

Then try: numbers = [1, 1, 2], remove_all(numbers, 1) and print(numbers).

Another way: the list has at most len(t) elements equal to the value, so call remove up to len(t) times, as long as the value is in the list:

def remove_all(t, value):
    for i in range(len(t)):
        if value in t:
            t.remove(value)

A loop through t itself skips elements: after remove, each later element moves back one position, so the loop never sees the element just after the one it removed.

def remove_all_wrong(t, value):
    for x in t:
        if x == value:
            t.remove(x)

letters = ['a', 'b', 'a', 'a']
remove_all_wrong(letters, 'a')
print(letters)

['b', 'a']

Making a new list of the other elements and assigning it to t in the function would not work either: it changes only the local variable t, not the caller’s list.

Question 20 (hard): write a function#

Write a function called has_duplicates that takes a list and returns True if any element appears in it more than once, and False otherwise.

Start from this header (replace ... with the body):

def has_duplicates(t):
    ...

Examples

print(has_duplicates([1, 2, 3, 2]), has_duplicates(['a', 'b']))

True False

print(has_duplicates([]), has_duplicates(list('banana')))

False True

Answer

For each index i, check whether the element at i is also in the rest of the list, after i:

def has_duplicates(t):
    for i in range(len(t)):
        if t[i] in t[i + 1:]:
            return True
    return False

Then try: print(has_duplicates([1, 2, 3, 2]), has_duplicates(['a', 'b'])).

Another way: after sorting, equal elements are next to each other, so compare each element with the next one:

def has_duplicates(t):
    s = sorted(t)
    for i in range(len(s) - 1):
        if s[i] == s[i + 1]:
            return True
    return False

Both are linear searches: they return True as soon as they find a duplicate, and False only after the loop. For an empty list, range(len(s) - 1) is range(-1), which produces no values.

Summary and questions by Prof. Y. Rosenthal, based on Think Python: 3rd Edition by Allen B. Downey. Text license: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International

9c. Prof. Rosenthal’s Review

Contents

9c. Prof. Rosenthal’s Review#

Concepts covered#

Questions#

Question 1 (easy): what is displayed?#

Question 2 (easy): what is displayed?#

Question 3 (easy): what is displayed?#

Question 4 (easy): what is displayed?#

Question 5 (easy): write a function#

Question 6 (easy): what is displayed?#

Question 7 (medium): what is displayed?#

Question 8 (medium): what is displayed?#

Question 9 (medium): what is displayed?#

Question 10 (medium): what is displayed?#

Question 11 (medium): what happens?#

Question 12 (medium): what is displayed?#

Question 13 (medium): write a function#

Question 14 (medium): write a function#

Question 15 (medium): what is displayed?#

Question 16 (hard): what is displayed?#

Question 17 (hard): what is displayed?#

Question 18 (hard): write a function#

Question 19 (hard): write a function#

Question 20 (hard): write a function#