# Lab 7: Midterm Review

## Starter Files

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

## Submission

This lab will not be graded. You do not need to submit anything.

## Control

### Question 1: Abundant

Implement a function `abundant`

that takes a positive integer `n`

. It prints
all ways of multiplying two positive integers to make `n`

. It returns
whether `n`

is an *abundant* number, meaning that the sum of its proper
divisors is greater than `n`

. A proper divisor of `n`

is an integer smaller
than `n`

that evenly divides `n`

.

*Hint*: To print `1 * 2`

, use the expression `print(1, '*', 2)`

```
def abundant(n):
"""Print all ways of forming positive integer n by multiplying two positive
integers together, ordered by the first term. Then, return whether the sum
of the proper divisors of n is greater than n.
A proper divisor of n evenly divides n but is less than n.
>>> abundant(12) # 1 + 2 + 3 + 4 + 6 is 16, which is larger than 12
1 * 12
2 * 6
3 * 4
True
>>> abundant(14) # 1 + 2 + 7 is 10, which is not larger than 14
1 * 14
2 * 7
False
>>> abundant(16)
1 * 16
2 * 8
4 * 4
False
>>> abundant(20)
1 * 20
2 * 10
4 * 5
True
>>> abundant(22)
1 * 22
2 * 11
False
>>> r = abundant(24)
1 * 24
2 * 12
3 * 8
4 * 6
>>> r
True
>>> r = abundant(25)
1 * 25
5 * 5
>>> r
False
>>> r = abundant(156)
1 * 156
2 * 78
3 * 52
4 * 39
6 * 26
12 * 13
>>> r
True
"""
"*** YOUR CODE HERE ***"
d, total = 1, 0
while d*d <= n:
if n % d == 0:
print(d, '*', n//d)
total = total + d
if d > 1 and d*d < n:
total = total + n//d
d = d + 1
return total > n
```

Use OK to test your code:

`python3 ok -q abundant`

### Question 2: Same hailstone

Implement `same_hailstone`

, which returns whether positive integer arguments
`a`

and `b`

are part of the same hailstone sequence. A hailstone sequence is
defined in Homework 1 as the following:

- Pick a positive integer
`n`

as the start. - If
`n`

is even, divide it by 2. - If
`n`

is odd, multiply it by 3 and add 1. - Continue this process until
`n`

is 1.

```
def same_hailstone(a, b):
"""Return whether a and b are both members of the same hailstone
sequence.
>>> same_hailstone(10, 16) # 10, 5, 16, 8, 4, 2, 1
True
>>> same_hailstone(16, 10) # order doesn't matter
True
>>> result = same_hailstone(3, 19) # return, don't print
>>> result
False
Extra tests:
>>> same_hailstone(19, 3)
False
>>> same_hailstone(4858, 61)
True
>>> same_hailstone(7, 6)
False
"""
"*** YOUR CODE HERE ***"
return in_hailstone(a, b) or in_hailstone(b, a)
def in_hailstone(a, b):
"""Return whether b is in hailstone sequence of a."""
while a > 1:
if a == b:
return True
elif a % 2 == 0:
a = a // 2
else:
a = a * 3 + 1
return False
```

Use OK to test your code:

`python3 ok -q same_hailstone`

## Higher-Order Functions

### Question 3: Piecewise

Implement `piecewise`

, which takes two one-argument functions, `f`

and `g`

,
along with a number `b`

. It returns a new function that takes a number `x`

and
returns either `f(x)`

if `x`

is less than `b`

, or `g(x)`

if `x`

is greater than
or equal to `b`

.

```
def piecewise(f, g, b):
"""Returns the piecewise function h where:
h(x) = f(x) if x < b,
g(x) otherwise
>>> def negate(x):
... return -x
>>> identity = lambda x: x
>>> abs_value = piecewise(negate, identity, 0)
>>> abs_value(6)
6
>>> abs_value(-1)
1
"""
"*** YOUR CODE HERE ***"
def h(x):
if x < b:
return f(x)
return g(x)
return h
```

Use OK to test your code:

`python3 ok -q piecewise`

### Question 4: Smoothing

The idea of smoothing a function is a concept used in signal
processing among other things. If `f`

is a one-argument function and `dx`

is some small
number, then the smoothed version of `f`

is the function whose value at
a point `x`

is the average of `f(x - dx)`

, `f(x)`

, and `f(x + dx)`

.
Write a function `smooth`

that takes as input a function `f`

and a
value to use for `dx`

and returns a function that computes the smoothed
version of `f`

. Do not use any `def`

statements inside of `smooth`

; use
`lambda`

expressions instead.

```
def smooth(f, dx):
"""Returns the smoothed version of f, g where
g(x) = (f(x - dx) + f(x) + f(x + dx)) / 3
>>> square = lambda x: x ** 2
>>> round(smooth(square, 1)(0), 3)
0.667
"""
"*** YOUR CODE HERE ***"
return lambda x: (f(x - dx) + f(x) + f(x + dx)) / 3
```

Use OK to test your code:

`python3 ok -q smooth`

It is sometimes valuable to repeatedly smooth a function (that is,
smooth the smoothed function, and so on) to obtain the `n`

-fold
smoothed function. Show how to generate the `n`

-fold smoothed function,
`n_fold_smooth`

, of any given function using your `smooth`

function and
`repeated`

function:

```
def repeated(f, n):
"""Returns a single-argument function that takes a value, x, and applies
the single-argument function F to x N times.
>>> repeated(lambda x: x*x, 3)(2)
256
"""
def h(x):
for k in range(n):
x = f(x)
return x
return h
```

As with `smooth`

, use `lambda`

expressions
rather than `def`

statements in the body of `n_fold_smooth`

.

```
def n_fold_smooth(f, dx, n):
"""Returns the n-fold smoothed version of f
>>> square = lambda x: x ** 2
>>> round(n_fold_smooth(square, 1, 3)(0), 3)
2.0
"""
"*** YOUR CODE HERE ***"
return repeated(lambda g: smooth(g, dx), n)(f)
```

The `repeated`

function takes in a single-argument function `f`

and
returns a new single-argument function that repeatedly applies `f`

to
its argument. We want to repeatedly apply `smooth`

, but `smooth`

is a
two-argument function. So we first have to convert it to a one-argument
function, using a `lambda`

expression. Then `repeated`

returns a
function that repeatedly smooths its input function, and we apply this
to `f`

to get an `n`

-fold smoothed version of `f`

.

Use OK to test your code:

`python3 ok -q n_fold_smooth`

## Lambdas

### Question 5: Lambda the Plentiful

Try drawing an environment diagram for the following code and predict what Python will output.

**Note**: This is a challenging problem! Work together with your neighbors and
see if you can arrive at the correct answer.

You can check your work with the Online Python Tutor, but try drawing it yourself first!

```
>>> def go(bears):
... gob = 3
... print(gob)
... return lambda ears: bears(gob)
>>> gob = 4
>>> bears = go(lambda ears: gob)
______3
>>> bears(gob)
______4
```

Hint: What is the parent frame for a lambda function?

### Question 6: Palindrome

A number is considered a palindrome if it reads the same forwards and backwards. Fill in the blanks '_' to help determine if a number is a palindrome. In the spirit of exam style questions, please do not edit any parts of the function other than the blanks.

```
def is_palindrome(n):
"""
Fill in the blanks '_____' to check if a number
is a palindrome.
>>> is_palindrome(12321)
True
>>> is_palindrome(42)
False
>>> is_palindrome(2015)
False
>>> is_palindrome(55)
True
"""
x, y = n, 0
f = lambda: _____
f = lambda: y * 10 + x % 10 while x > 0:
x, y = _____, f()
x, y = x // 10, f() return y == n
```

Use OK to test your code:

`python3 ok -q is_palindrome`

## Linked Lists

### Question 7: 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.

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

Use OK to test your code:

`python3 ok -q deep_len`

### Question 8: Linked Lists as Strings

Marvin and Brian like different ways of displaying the linked list
structure in Python. While Marvin likes box and pointer diagrams,
Brian 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.
>>> marvins_to_string = make_to_string("[", "|-]-->", "", "[]")
>>> brians_to_string = make_to_string("(", " . ", ")", "()")
>>> lst = link(1, link(2, link(3, link(4, empty))))
>>> marvins_to_string(lst)
'[1|-]-->[2|-]-->[3|-]-->[4|-]-->[]'
>>> marvins_to_string(empty)
'[]'
>>> brians_to_string(lst)
'(1 . (2 . (3 . (4 . ()))))'
>>> brians_to_string(empty)
'()'
"""
"*** YOUR CODE HERE ***"
def printer(lst):
if lst == empty:
return empty_repr
else:
return front + str(first(lst)) + mid + printer(rest(lst)) + back
return printer
```

Use OK to test your code:

`python3 ok -q make_to_string`

## Trees

### Question 9: 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 children(t) == []:
return tree(fn(entry(t)), [])
mapped_subtrees = []
for subtree in children(t):
mapped_subtrees += [ tree_map(fn, subtree) ]
return tree(fn(entry(t)), mapped_subtrees)
# Alternate solution
def tree_map(fn, t):
return tree(fn(entry(t)), [tree_map(fn, t) for t in children(t)])
```

Use OK to test your code:

`python3 ok -q tree_map`

### Question 10: 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)])])
>>> print_tree(add_trees(numbers, numbers))
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
if not t2:
return t1
new_entry = entry(t1) + entry(t2)
t1_children, t2_children = children(t1), children(t2)
length_t1, length_t2 = len(t1_children), len(t2_children)
if length_t1 < length_t2:
t1_children += [None for _ in range(length_t1, length_t2)]
elif len(t1_children) > len(t2_children):
t2_children += [None for _ in range(length_t2, length_t1)]
return tree(new_entry, [add_trees(child1, child2) for child1, child2 in zip(t1_children, t2_children)])
```

Use OK to test your code:

`python3 ok -q add_trees`