14 Review: the whole course as seven things the final can ask you to do

Tracing a list that indexes itself

The program from the failed attempt above. Do not read it; run it on paper.

a = [3, 0, 2, 1]
i = 0
total = 0
while i < len(a):
    total = total + a[a[i]]
    i = i + 1
print(total)
print(a)

A loop variable that is assigned inside the loop

A nested loop, with one line in the body that looks like it changes the loop.

for i in range(3):
    for j in range(3):
        if j == 1:
            j = 2
        print(i, j, end='  ')
    print()

One append, seen through two names

Three names, two of them for the same list, and then an append through each.

first = [4, 7]
second = first
third = first[:]
second.append(9)
third.append(1)
print(first)
print(second)
print(third)
print(first is second, first is third, first == third)

The run:

[4, 7, 9]
[4, 7, 9]
[4, 7, 1]
True False False

A default parameter that remembers

A function whose default value is a list, called four times.

def collect(item, bag=[]):
    bag.append(item)
    return bag

print(collect('a'))
print(collect('b'))
print(collect('c', []))
print(collect('d'))

The run:

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

Mutating the caller's list against building a new one

Two functions, one line apart in what they do to their argument.

def grow_in_place(values):
    """Append a zero to the caller's list and hand nothing back."""
    values.append(0)

def grow_by_copy(values):
    """Build a longer list and hand it back, leaving the caller's alone."""
    values = values + [0]
    return values

nums = [5, 6]
grow_in_place(nums)
print(nums)
other = grow_by_copy(nums)
print(nums, other)
print(grow_in_place(nums))
print(nums)

The run:

[5, 6, 0]
[5, 6, 0] [5, 6, 0, 0]
None
[5, 6, 0, 0]

Reading a module level name against assigning to it

A counter at module level and a function that tries to raise it.

count = 0

def bump():
    count = count + 1

bump()

The run:

Traceback (most recent call last):
  ...
UnboundLocalError: cannot access local variable 'count' where it is not associated with a value

With one line added it works:

count = 0

def bump():
    """Add one to the module level counter."""
    global count
    count = count + 1

bump()
bump()
print(count)

The run:

2

sort against sorted, printed side by side

Four prints, in the order that makes the difference visible.

marks = [70, 45, 90]
print(marks.sort())
print(marks)
print(sorted(marks, reverse=True))
print(marks)

The run:

None
[45, 70, 90]
[90, 70, 45]
[45, 70, 90]

A strip that was thrown away

A line read from a file, cleaned up, split, and turned into a number.

line = '  CS115 , 78 \n'
line.strip()
print(repr(line))
parts = line.strip().split(',')
print(parts)
code = parts[0].strip().lower()
mark = int(parts[1])
print(code, mark + 1)

The run:

'  CS115 , 78 \n'
['CS115 ', ' 78']
cs115 79

A tally built in a dictionary, then taken apart

The counting pattern, then pop, then the keys.

tally = {}
words = ['red', 'blue', 'red', 'green', 'red']
for w in words:
    if w in tally:
        tally[w] = tally[w] + 1
    else:
        tally[w] = 1
print(tally)
print(tally.pop('blue'), tally)
print(list(tally.keys()))

The run:

{'red': 3, 'blue': 1, 'green': 1}
1 {'red': 3, 'green': 1}
['red', 'green']

Two instances, one mark, two letters

A class, a subclass that redefines one method, and three prints.

class Student(object):
    def __init__(self, name, mark):
        """Hold one name and one mark."""
        self.name = name
        self.mark = mark

    def grade(self):
        """Return the letter this mark earns."""
        if self.mark >= 85:
            return 'A'
        elif self.mark >= 70:
            return 'B'
        return 'C'

    def __str__(self):
        return self.name + ' (' + self.grade() + ')'


class GradStudent(Student):
    def __init__(self, name, mark, advisor):
        Student.__init__(self, name, mark)
        self.advisor = advisor

    def grade(self):
        """Graduate marks are judged on a stricter scale."""
        if self.mark >= 90:
            return 'A'
        elif self.mark >= 80:
            return 'B'
        return 'C'


a = Student('Deniz', 88)
b = GradStudent('Ece', 88, 'Kaya')
print(a)
print(b)
print(b.advisor, isinstance(b, Student))

The run:

Deniz (A)
Ece (B)
Kaya True

A list on the class, shared by every instance

The class body assigns a list, and one instance appends to it.

class Team(object):
    members = []

    def __init__(self, name):
        """Hold this team's own name."""
        self.name = name

    def add(self, who):
        """Add a member to this team."""
        self.members.append(who)


x = Team('alpha')
y = Team('beta')
x.add('Ada')
print(x.members, y.members)
print(x.name, y.name)

The run:

['Ada'] ['Ada']
alpha beta

Counting the comparisons a selection sort makes

The sort with a counter added, so that the count comes out of a run rather than out of a formula.

def selection_sort(values):
    """Sort in place and return how many comparisons it took."""
    checks = 0
    for start in range(len(values)):
        smallest = start
        for i in range(start + 1, len(values)):
            checks = checks + 1
            if values[i] < values[smallest]:
                smallest = i
        values[start], values[smallest] = values[smallest], values[start]
    return checks


data = [5, 2, 9, 1, 6]
n = len(data)
print(selection_sort(data), n * (n - 1) // 2)
print(data)

The run:

10 10
[1, 2, 5, 6, 9]

Probes used by a halving search, present and absent

The search with a probe counter, run twice: once for a value that is there and once for one that is not.

def bisect_steps(values, target):
    """Return whether target is there, and how many probes it took."""
    low = 0
    high = len(values) - 1
    probes = 0
    while low <= high:
        mid = (low + high) // 2
        probes = probes + 1
        if values[mid] == target:
            return True, probes
        elif values[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return False, probes


sorted_marks = [11, 18, 23, 30, 42, 55, 61, 70]
print(bisect_steps(sorted_marks, 61))
print(bisect_steps(sorted_marks, 12))

The run:

(True, 3)
(False, 3)

Reading a recursion from its own printed trace

The recursion prints one line on the way down and one on the way back up, so the stack is visible.

def count_down(n, depth=0):
    """Add n down to 0, printing a line on the way in and on the way out."""
    print('  ' * depth + 'enter ' + str(n))
    if n == 0:
        print('  ' * depth + 'base')
        return 0
    result = n + count_down(n - 1, depth + 1)
    print('  ' * depth + 'leave ' + str(n) + ' -> ' + str(result))
    return result


print(count_down(3))

The run:

enter 3
  enter 2
    enter 1
      enter 0
      base
    leave 1 -> 1
  leave 2 -> 3
leave 3 -> 6
6

A per course report read from a file

The specification: a file holds one line per mark in the form course,mark. Print one line per course, in alphabetical order, with the number of marks and their average to one decimal, the course in a nine wide column and the count in a three wide one. The program writes its own data file first, so that the run repeats.

def write_sample(name):
    """Create the data file this program reads, so the run repeats."""
    out = open(name, 'w')
    out.write('cs115,70\ncs115,88\nmath101,55\ncs115,64\nmath101,91\n')
    out.close()


def read_marks(name):
    """Return a dictionary of course to list of marks, read from the file."""
    marks = {}
    f = open(name, 'r')
    for line in f:
        line = line.strip()
        if line == '':
            continue
        course, mark = line.split(',')
        if course in marks:
            marks[course].append(int(mark))
        else:
            marks[course] = [int(mark)]
    f.close()
    return marks


def report(marks):
    """Print one line per course in name order, average to one decimal."""
    for course in sorted(marks.keys()):
        values = marks[course]
        average = sum(values) / len(values)
        print('{0:<9}{1:>3}{2:>8}'.format(course, len(values),
                                          format(average, '.1f')))


write_sample('marks.txt')
data = read_marks('marks.txt')
report(data)

Sample Run:

cs115      3    74.0
math101    2    73.0

Row and column summaries of a rectangular grid

The specification: given a rectangular grid of numbers, print each row followed by its total, then the list of column totals, then which column is largest, counting from one.

def column_totals(grid):
    """Return a list holding the total of each column of a rectangular grid."""
    totals = []
    for c in range(len(grid[0])):
        running = 0
        for r in range(len(grid)):
            running = running + grid[r][c]
        totals.append(running)
    return totals


def widest(totals):
    """Return the position of the largest total, counting from 1."""
    best = 0
    for i in range(len(totals)):
        if totals[i] > totals[best]:
            best = i
    return best + 1


sales = [[4, 9, 2], [7, 1, 5], [3, 8, 6]]
for row in sales:
    print(row, sum(row))
totals = column_totals(sales)
print(totals)
print('best column', widest(totals))

Sample Run:

[4, 9, 2] 15
[7, 1, 5] 13
[3, 8, 6] 17
[14, 18, 13]
best column 2