Diagnostics are meant for you to check your understanding of the week's material. They are not worth any points and are not counted towards midterm recovery points; instead, diagnostics are solely for your benefit. If you find yourself struggling with the questions in this diagnostic, consider signing up for Tutoring.

## Trees

### Question 1: Countdown

Define the function `countdown_tree` so that it returns the specific tree below. Make sure to use the tree constructor from the Data Abstraction!

``````    10
/ \
/   \
9     7
|     |
8     6
|
5``````

The doctest below shows the `print_tree` representation:

``````def countdown_tree():
"""Return a tree that has the following structure.

>>> print_tree(countdown_tree())
10
9
8
7
6
5
"""
return tree(10, [tree(9, [tree(8)]),
tree(7, [tree(6, [tree(5)])])])``````

### Question 2

Define `max_tree`, which takes a tree and returns the largest entry in teh tree.

``````def max_tree(t):
if is_leaf(t):
return entry(t)
return max(entry(t), max([max_tree(s) for s in subtrees(t)]))``````

### Question 3: Size

Define the function `size_of_tree`, which takes in a tree as an argument and returns the number of entries in the tree.

``````def size_of_tree(t):
"""Return the number of entries in the tree.

>>> print_tree(numbers)
1
2
3
4
5
6
7
>>> size_of_tree(numbers)
7
"""
return 1 + sum([size_of_tree(t) for t in subtrees(t)])

# Alternate solution
def size_of_tree(t):
subtrees_sum = 0
for subtree in subtrees(t):
subtrees_sum += size_of_tree(subtree)
return 1 + subtrees_sum``````

### Question 4: Same shape

Define a function `same_shape` that, given two trees, `t1` and `t2`, returns `True` if the two trees have the same shape (but not necessarily the same data in each node) and False otherwise.

``````def same_shape(t1, t2):
"""Return True if t1 is indentical in shape to t2.

>>> test_tree1 = tree(1, [tree(2), tree(3)])
>>> test_tree2 = tree(4, [tree(5), tree(6)])
>>> test_tree3 = tree(1,
...                   [tree(2,
...                         [tree(3)])])
>>> test_tree4 = tree(4,
...                   [tree(5,
...                         [tree(6)])])
>>> same_shape(test_tree1, test_tree2)
True
>>> same_shape(test_tree3, test_tree4)
True
>>> same_shape(test_tree2, test_tree4)
False
"""
s1, s2 = subtrees(t1), subtrees(t2)
if len(s1) != len(s2):
return False
for index in range(len(s1)):
if not same_shape(s1[index], s2[index]):
return False
return True

# Alternate solution
def same_shape(t1, t2):
children_same = all(map(same_shape, subtrees(t1), subtrees(t2)))
return len(subtrees(t1)) == len(subtrees(t2)) and children_same``````

## Mutability

### Question 5: Fibonacci

Write a function `make_fib` that returns a function that returns the next Fibonacci number each time it is called.

``````def make_fib():
"""Returns a function that returns the next Fibonacci number
every time it is called.

>>> fib = make_fib()
>>> fib()
0
>>> fib()
1
>>> fib()
1
>>> fib()
2
>>> fib()
3
"""
cur, next = 0, 1
def fib():
nonlocal cur, next
result = cur
cur, next = next, cur + next
return result
return fib``````

### Question 6

Define a function `make_accumulator` that returns an `accumulator` function, which takes one numerical argument and returns the sum of all arguments ever passed to `accumulator`. Use a `list` and not a `nonlocal` statement:

``````def make_accumulator():
"""Return an accumulator function that takes a single numeric argument and
accumulates that argument into total, then returns total.

>>> acc = make_accumulator()
>>> acc(15)
15
>>> acc(10)
25
>>> acc2 = make_accumulator()
>>> acc2(7)
7
>>> acc3 = acc2
>>> acc3(6)
13
>>> acc2(5)
18
>>> acc(4)
29
"""
total = 
def accumulator(amount):
total += amount
return accumulator``````

### Question 7

Define a function `make_accumulator_nonlocal` that returns an `accumulator` function, which takes one numerical argument and returns the sum of all arguments ever passed to `accumulator`. Use a `nonlocal` statement, but no `list` or `dict`:

``````def make_accumulator_nonlocal():
"""Return an accumulator function that takes a single numeric argument and
accumulates that argument into total, then returns total.

>>> acc = make_accumulator_nonlocal()
>>> acc(15)
15
>>> acc(10)
25
>>> acc2 = make_accumulator_nonlocal()
>>> acc2(7)
7
>>> acc3 = acc2
>>> acc3(6)
13
>>> acc2(5)
18
>>> acc(4)
29
"""
total = 0
def accumulator(amount):
nonlocal total
total += amount
return accumulator``````

### Question 8: Filter

Write a function that filters a list, only keeping elements that satisfy the predicate. Be sure to mutate the original list.

This function should NOT return anything. This is to emphasize that this function should utilize mutability.

``````def filter(pred, lst):
"""Filters lst with pred using mutation.
>>> original_list = [5, -1, 2, 0]
>>> filter(lambda x: x % 2 == 0, original_list)
>>> original_list
[2, 0]
"""
i = len(lst) - 1
while i >= 0:
if not pred(lst[i]):
lst.pop(i)
i -= 1

def filter(pred, lst):
"""Filters lst with pred using mutation.
>>> original_list = [5, -1, 2, 0]
>>> filter(lambda x: x % 2 == 0, original_list)
>>> original_list
[2, 0]
"""
if lst:
temp = lst.pop(0)
filter(pred, lst)
if pred(temp):
lst.insert(0, temp)``````

### Question 9: Reverse

Write a function that reverses the given list. Be sure to mutate the original list.

This function should NOT return anything. This is to emphasize that this function should utilize mutability.

``````def reverse(lst):
"""Reverses lst using mutation.
>>> original_list = [5, -1, 29, 0]
>>> reverse(original_list)
>>> original_list
[0, 29, -1, 5]
"""
# iterative solution
midpoint = len(lst) // 2
last = len(lst) - 1
for i in range(midpoint):
lst[i], lst[last - i] = lst[last - i], lst[i]

# Recursive solution
def reverse(lst):
"""Reverses lst using mutation.
>>> original_list = [5, -1, 29, 0]
>>> reverse(original_list)
>>> original_list
[0, 29, -1, 5]
"""
if len(lst) > 1:
temp = lst.pop()
reverse(lst)
lst.insert(0, temp)

# Alternative recursive solution
def reverse(lst):
"""Reverses lst using mutation.
>>> original_list = [5, -1, 29, 0]
>>> reverse(original_list)
>>> original_list
[0, 29, -1, 5]
"""
midpoint = len(lst) // 2
last = len(lst) - 1
def helper(i):
if i == midpoint:
return
lst[i], lst[last - i] = lst[last - i], lst[i]
helper(i + 1)
helper(0)``````

## Object-Oriented Programming

### Question 10: Person

Modify the following `Person` class to add a `repeat` method, which repeats the last thing said. See the doctests for an example of its use.

Hint: you will have to modify other methods as well, not just the `repeat` method.

``````class Person(object):
"""Person class.

>>> steven = Person("Steven")
>>> steven.repeat()       # starts at whatever value you'd like
'I squirreled it away before it could catch on fire.'
>>> steven.say("Hello")
'Hello'
>>> steven.repeat()
'Hello'
>>> steven.greet()
'Hello, my name is Steven'
>>> steven.repeat()
'Hello, my name is Steven'
'Would you please preserve abstraction barriers'
>>> steven.repeat()
'Would you please preserve abstraction barriers'
"""
def __init__(self, name):
self.name = name
self.previous = "I squirreled it away before it could catch on fire."
def say(self, stuff):
self.previous = stuff        return stuff

return self.say("Would you please " + stuff)

def greet(self):
return self.say("Hello, my name is " + self.name)

def repeat(self):
return self.say(self.previous)``````

### Question 11: DoubleTalker

Suppose now that we wanted to define a class called `DoubleTalker` to represent people who always say things twice:

``````>>> steven = DoubleTalker("Steven")
>>> steven.say("hello")
"hello hello"
>>> steven.say("the sky is falling")
"the sky is falling the sky is falling"``````

Consider the following three definitions for `DoubleTalker` that inherit from the `Person` class:

``````class DoubleTalker(Person):
def __init__(self, name):
Person.__init__(self, name)
def say(self, stuff):
return Person.say(self, stuff) + " " + self.repeat()

class DoubleTalker(Person):
def __init__(self, name):
Person.__init__(self, name)
def say(self, stuff):
return stuff + " " + stuff

class DoubleTalker(Person):
def __init__(self, name):
Person.__init__(self, name)
def say(self, stuff):
return Person.say(self, stuff + " " + stuff)``````

Determine which of these definitions work as intended. Also determine for which of the methods the three versions would respond differently. (Don't forget about the `repeat` method!)

The last one works as intended. For the first and second ones, calling `repeat` would fail.