Due at 11:59pm on Monday, 10/24/2016.

## Starter Files

Download lab08.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

## Submission

By the end of this lab, you should have submitted the lab with `python3 ok --submit`. You may submit more than once before the deadline; only the final submission will be graded.

• To receive credit for this lab, you must complete Questions 1, 2, 3, 4 in lab08.py and submit through OK.
• The remaining questions are extra practice. They can be found in the lab08_extra.py file. It is recommended that you complete these problems on your own time.

# Required Questions

### Question 1: Deep Linked List Length

A linked list that contains one or more linked lists as elements is called a deep linked list. Write a function `deep_len` that takes in a (possibly deep) linked list and returns the deep length of that linked list, which is the sum of the deep length of all linked lists contained in a deep linked list.

Hint: Use `isinstance` to check if something is an instance of an object.

``````def deep_len(lnk):
""" Returns the deep length of a possibly deep linked list.
3
4
<<<1 2> 3> <4> 5>
>>> deep_len(levels)
5
"""
"*** YOUR CODE HERE ***"
if lnk is Link.empty:
return 0
elif not isinstance(lnk, Link):
return 1
else:
return deep_len(lnk.first) + deep_len(lnk.rest)``````

Use OK to test your code:

``python3 ok -q deep_len``

### Question 2: Linked Lists as Strings

Stan and Michelle like different ways of displaying the linked list structure in Python. While Stan likes box and pointer diagrams, Michelle prefers a more futuristic way. Write a function `make_to_string` that returns a function that converts the linked list to a string in their preferred style.

Hint: You can convert numbers to strings using the `str` function, and you can combine strings together using `+`.

``````>>> str(4)
'4'
>>> 'cs ' + str(61) + 'a'
'cs 61a'``````
``````def make_to_string(front, mid, back, empty_repr):
""" Returns a function that turns linked lists to strings.

>>> stans_to_string = make_to_string("[", "|-]-->", "", "[]")
>>> michelles_to_string = make_to_string("(", " . ", ")", "()")
>>> stans_to_string(lst)
'[1|-]-->[2|-]-->[3|-]-->[4|-]-->[]'
'[]'
>>> michelles_to_string(lst)
'(1 . (2 . (3 . (4 . ()))))'
'()'
"""
"*** YOUR CODE HERE ***"
def printer(lnk):
if lnk is Link.empty:
return empty_repr
else:
return front + str(lnk.first) + mid + printer(lnk.rest) + back
return printer``````

Use OK to test your code:

``python3 ok -q make_to_string``

## Trees

### Question 3: Tree Map

Define the function `tree_map`, which takes in a tree and a one-argument function as arguments and returns a new tree which is the result of mapping the function over the entries of the input tree.

``````def tree_map(fn, t):
"""Maps the function fn over the entries of tree and returns the
result in a new tree.

>>> numbers = Tree(1,
...                [Tree(2,
...                      [Tree(3),
...                       Tree(4)]),
...                 Tree(5,
...                      [Tree(6,
...                            [Tree(7)]),
...                       Tree(8)])])
>>> print_tree(tree_map(lambda x: 2**x, numbers))
2
4
8
16
32
64
128
256
"""
"*** YOUR CODE HERE ***"
if t.is_leaf():
return Tree(fn(t.root), [])
mapped_subtrees = [tree_map(fn, b) for b in t.branches]
return Tree(fn(t.root), mapped_subtrees)

# Alternate solution
def tree_map(fn, t):
return Tree(fn(t.root), [tree_map(fn, b) for b in t.branches])``````

Use OK to test your code:

``python3 ok -q tree_map``

### Question 4: Add trees

Define the function `add_trees`, which takes in two trees and returns a new tree where each corresponding node from the first tree is added with the node from the second tree. If a node at any particular position is present in one tree but not the other, it should be present in the new tree as well.

Hint: You may want to use the built-in zip function to iterate over multiple sequences at once.

``````def add_trees(t1, t2):
"""
>>> numbers = Tree(1,
...                [Tree(2,
...                      [Tree(3),
...                       Tree(4)]),
...                 Tree(5,
...                      [Tree(6,
...                            [Tree(7)]),
...                       Tree(8)])])
2
4
6
8
10
12
14
16
>>> print_tree(add_trees(Tree(2), Tree(3, [Tree(4), Tree(5)])))
5
4
5
>>> print_tree(add_trees(Tree(2, [Tree(3)]), Tree(2, [Tree(3), Tree(4)])))
4
6
4
>>> print_tree(add_trees(Tree(2, [Tree(3, [Tree(4), Tree(5)])]), \
Tree(2, [Tree(3, [Tree(4)]), Tree(5)])))
4
6
8
5
5
"""
"*** YOUR CODE HERE ***"
if not t1:
return t2 # Could replace with copy_tree(t2)
if not t2:
return t1 # Could replace with copy_tree(t1)
new_entry = t1.root + t2.root
t1_branches, t2_branches = list(t1.branches), list(t2.branches)
length_t1, length_t2 = len(t1_branches), len(t2_branches)
if length_t1 < length_t2:
t1_branches += [None for _ in range(length_t1, length_t2)]
elif length_t1 > length_t2:
t2_branches += [None for _ in range(length_t2, length_t1)]
return Tree(new_entry, [add_trees(branch1, branch2) for branch1, branch2 in zip(t1_branches, t2_branches)])``````

Use OK to test your code:

``python3 ok -q add_trees``

# Optional Questions

## Objects

### Question 5: WWPP: Methods

Use OK to test your knowledge with the following "What Would Python Print?" questions:

``python3 ok -q foobar -u``

Hint: Remember for all WWPP questions, enter `Function` if you believe the answer is `<function ...>` and `Error` if it errors.

``````>>> class Foo:
...     def print_one(self):
...         print('foo')
...     def print_two():
...         print('foofoo')
>>> f = Foo()
>>> f.print_one()
______foo
>>> f.print_two()
______Error
>>> Foo.print_two()
______foofoo
>>> class Bar(Foo):
...     def print_one(self):
...         print('bar')
>>> b = Bar()
>>> b.print_one()
______bar
>>> Bar.print_two()
______foofoo
>>> Bar.print_one = lambda x: print('new bar')
>>> b.print_one()
______new bar``````

### Question 6: WWPP: Attributes

Use OK to test your knowledge with the following "What Would Python Print?" questions:

``python3 ok -q attributes -u``

Hint: Remember for all WWPP questions, enter `Function` if you believe the answer is `<function ...>` and `Error` if it errors.

``````>>> class Foo:
...     a = 10
...     def __init__(self, a):
...         self.a = a
>>> class Bar(Foo):
...     b = 1
>>> a = Foo(5)
>>> b = Bar(2)
>>> a.a
______5
>>> b.a
______2
>>> Foo.a
______10
>>> Bar.b
______1
>>> Bar.a
______10
>>> b.b
______1
>>> Foo.c = 15
>>> Foo.c
______15
>>> a.c
______15
>>> b.c
______15
>>> Bar.c
______15
>>> b.b = 3
>>> b.b
______3
>>> Bar.b
______1``````

## Nonlocal

### Question 7: Advanced Counter

Complete the definition of `make_advanced_counter_maker`, which creates a function that creates counters. These counters can not only update their personal count, but also a shared count for all counters. They can also reset either count.

``````def make_advanced_counter_maker():
"""Makes a function that makes counters that understands the
messages "count", "global-count", "reset", and "global-reset".
See the examples below:

>>> make_counter = make_advanced_counter_maker()
>>> tom_counter = make_counter()
>>> tom_counter('count')
1
>>> tom_counter('count')
2
>>> tom_counter('global-count')
1
>>> jon_counter = make_counter()
>>> jon_counter('global-count')
2
>>> jon_counter('count')
1
>>> jon_counter('reset')
>>> jon_counter('count')
1
>>> tom_counter('count')
3
>>> jon_counter('global-count')
3
>>> jon_counter('global-reset')
>>> tom_counter('global-count')
1
"""
"*** YOUR CODE HERE ***"
global_count = 0
def make_counter():
count = 0
def counter(msg):
nonlocal global_count, count
if msg == 'count':
count += 1
return count
elif msg == 'reset':
count = 0
elif msg == 'global-count':
global_count += 1
return global_count
elif msg == 'global-reset':
global_count = 0
return counter
return make_counter``````

Use OK to test your code:

``python3 ok -q make_advanced_counter_maker``

## Lists

### Question 8: Trade

In the integer market, each participant has a list of positive integers to trade. When two participants meet, they trade the smallest non-empty prefix of their list of integers. A prefix is a slice that starts at index 0.

Write a function `trade` that exchanges the first `m` elements of list `first` with the first `n` elements of list `second`, such that the sums of those elements are equal, and the sum is as small as possible. If no such prefix exists, return the string `'No deal!'` and do not change either list. Otherwise change both lists and return `'Deal!'`. A partial implementation is provided.

``````def trade(first, second):
"""Exchange the smallest prefixes of first and second that have equal sum.

>>> a = [1, 1, 3, 2, 1, 1, 4]
>>> b = [4, 3, 2, 7]
>>> trade(a, b) # Trades 1+1+3+2=7 for 4+3=7
'Deal!'
>>> a
[4, 3, 1, 1, 4]
>>> b
[1, 1, 3, 2, 2, 7]
>>> c = [3, 3, 2, 4, 1]
'No deal!'
>>> b
[1, 1, 3, 2, 2, 7]
>>> c
[3, 3, 2, 4, 1]
'Deal!'
>>> a
[3, 3, 2, 1, 4]
>>> b
[1, 1, 3, 2, 2, 7]
>>> c
[4, 3, 1, 4, 1]
"""
m, n = 1, 1

"*** YOUR CODE HERE ***"
equal_prefix = lambda: sum(first[:m]) == sum(second[:n])
while m < len(first) and n < len(second) and not equal_prefix():
if sum(first[:m]) < sum(second[:n]):
m += 1
else:
n += 1
if False: # change this line!
if equal_prefix():        first[:m], second[:n] = second[:n], first[:m]
return 'Deal!'
else:
return 'No deal!'``````

Use OK to test your code:

``python3 ok -q trade``

## Orders of Growth

### Question 9: Boom (Orders of Growth)

What is the order of growth in time for the following function boom? Use big-θ notation.

``````def boom(n):
sum = 0
a, b = 1, 1
while a <= n*n:
while b <= n*n:
sum += (a*b)
b += 1
b = 0
a += 1
return sum``````

θ(n4)

Use OK to test your code:

``python3 ok -q boom -u``