Diagnostic 4: Week 4 review
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
"""
"*** YOUR CODE HERE ***"
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):
"*** YOUR CODE HERE ***"
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
"""
"*** YOUR CODE HERE ***"
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
"""
"*** YOUR CODE HERE ***"
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
"""
"*** YOUR CODE HERE ***"
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
"""
"*** YOUR CODE HERE ***"
total = [0]
def accumulator(amount):
total[0] += amount
return total[0]
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
"""
"*** YOUR CODE HERE ***"
total = 0
def accumulator(amount):
nonlocal total
total += amount
return total
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]
"""
"*** YOUR CODE HERE ***"
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]
"""
"*** YOUR CODE HERE ***"
# 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)
ObjectOriented 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'
>>> steven.ask("preserve abstraction barriers")
'Would you please preserve abstraction barriers'
>>> steven.repeat()
'Would you please preserve abstraction barriers'
"""
def __init__(self, name):
self.name = name
"*** YOUR CODE HERE ***"
self.previous = "I squirreled it away before it could catch on fire."
def say(self, stuff):
"*** YOUR CODE HERE ***"
self.previous = stuff return stuff
def ask(self, stuff):
return self.say("Would you please " + stuff)
def greet(self):
return self.say("Hello, my name is " + self.name)
def repeat(self):
"*** YOUR CODE HERE ***"
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.