# Lab 8: Midterm Review lab08.zip

Due at 11:59pm on Friday, 10/20/2017.

## 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. Check that you have successfully submitted your code on okpy.org.

• To receive credit for this lab, you must complete Questions 1, 2, 3, and 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

Note: For your reference, the `Link` and `Tree` classes can be found at the bottom of lab08.py.

### Q1: 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
>>> print(levels)
<<<1 2> 3> <4> 5>
>>> deep_len(levels)
5
"""
return 0
return 1
else:
return deep_len(lnk.first) + deep_len(lnk.rest)``````

Use Ok to test your code:

``python3 ok -q deep_len``

### Q2: Linked Lists as Strings

Kevin and Jerry like different ways of displaying the linked list structure in Python. While Kevin likes box and pointer diagrams, Jerry 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.

>>> kevins_to_string = make_to_string("[", "|-]-->", "", "[]")
>>> jerrys_to_string = make_to_string("(", " . ", ")", "()")
>>> kevins_to_string(lst)
'[1|-]-->[2|-]-->[3|-]-->[4|-]-->[]'
'[]'
>>> jerrys_to_string(lst)
'(1 . (2 . (3 . (4 . ()))))'
'()'
"""
def printer(lnk):
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

### Q3: 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 t 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_map(lambda x: 2**x, numbers))
2
4
8
16
32
64
128
256
"""
if t.is_leaf():
return Tree(fn(t.label), [])
mapped_subtrees = [tree_map(fn, b) for b in t.branches]
return Tree(fn(t.label), mapped_subtrees)

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

Use Ok to test your code:

``python3 ok -q tree_map``

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
5
4
5
>>> print(add_trees(Tree(2, [Tree(3)]), Tree(2, [Tree(3), Tree(4)])))
4
6
4
>>> print(add_trees(Tree(2, [Tree(3, [Tree(4), Tree(5)])]), \
Tree(2, [Tree(3, [Tree(4)]), Tree(5)])))
4
6
8
5
5
"""
if not t1:
return t2.copy_tree()
if not t2:
return t1.copy_tree()
new_label = t1.label + t2.label
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_label, [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

### Q5: 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``````

### Q6: 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``````

### Q7: Keyboard

We'd like to create a `Keyboard` class that takes in an arbitrary number of `Button`s and stores these `Button`s in a dictionary. The keys in the dictionary will be ints that represent the postition on the `Keyboard`, and the values will be the respective `Button`. Fill out the methods in the `Keyboard` class according to each description, using the doctests as a reference for the behavior of a `Keyboard`.

``````class Keyboard:
"""A Keyboard takes in an arbitrary amount of buttons, and has a
dictionary of positions as keys, and values as Buttons.

>>> b1 = Button(0, "H")
>>> b2 = Button(1, "I")
>>> k = Keyboard(b1, b2)
>>> k.buttons[0].key
'H'
>>> k.press(1)
'I'
>>> k.typing([0, 1])
'HI'
>>> k.typing([1, 0])
'IH'
>>> b1.pressed
2
>>> b2.pressed
3
"""

def __init__(self, *args):
self.buttons = {}
for button in args:
self.buttons[button.pos] = button
def press(self, info):
"""Takes in a position of the button pressed, and
returns that button's output"""
if info in self.buttons.keys():
b = self.buttons[info]
b.pressed += 1
return b.key
return ''
def typing(self, typing_input):
"""Takes in a list of positions of buttons pressed, and
returns the total output"""
accumulate = ''
for pos in typing_input:
accumulate+=self.press(pos)
return accumulate
class Button:
def __init__(self, pos, key):
self.pos = pos
self.key = key
self.pressed = 0``````

Use Ok to test your code:

``python3 ok -q Keyboard``

## Nonlocal

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:

>>> 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
"""
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

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]
'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

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

### Q10: Zap (Orders of Growth)

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

``````def zap(n):
i, count = 1, 0
while i <= n:
while i <= 5 * n:
count += i
print(i / 6)
i *= 3
return count``````

θ(log n)

Here, the stopping condition of both loops rely on the same variable `i`. You might notice that completion of the inner loop will guarantee completion of the outer loop; after all, if `i` is greater than `5 * n`, then it will be greater than `n`. Therefore, the overall runtime is just the runtime of the inner loop. Since `i` begins at 1 and is multiplied by 3 at every iteration of the inner loop, the inner loop will have `log n` iterations overall. Each iteration does contant work, so the overall runtime will be `log n`.