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

## Control

### Question 1: 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`

### Question 2: Amicable

Implement a function `amicable`

that takes a positive integer `n`

. It returns
the smallest amicable number greater than `n`

.

Two **different** numbers are both amicable if the sum of the proper divisors
of each is equal to the other. Any number that's part of such a pair is an
amicable number.

*Hint*: You may want to create a separate function to sum proper divisors.

```
def amicable(n):
"""Return the smallest amicable number greater than positive integer n.
Every amicable number x has a buddy y different from x, such that
the sum of the proper divisors of x equals y, and
the sum of the proper divisors of y equals x.
For example, 220 and 284 are both amicable because
1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 is 284, and
1 + 2 + 4 + 71 + 142 is 220
>>> amicable(5)
220
>>> amicable(220)
284
>>> amicable(284)
1184
>>> r = amicable(5000)
>>> r
5020
>>> amicable(100483)
100485
"""
"*** YOUR CODE HERE ***"
n = n + 1
while True:
m = sum_divisors(n)
if m != n and sum_divisors(m) == n:
return n
n = n + 1
def sum_divisors(n):
d, total = 1, 0
while d < n:
if n % d == 0:
total = total + d
d = d + 1
return total
```

Use OK to test your code:

`python3 ok -q amicable`

## Higher Order Functions

### Question 3: I Heard You Liked Functions...

Define a function `cycle`

that takes in three functions `f1`

, `f2`

,
`f3`

, as arguments. `cycle`

will return another function that should
take in an integer argument `n`

and return another function. That
final function should take in an argument `x`

and cycle through
applying `f1`

, `f2`

, and `f3`

to `x`

, depending on what `n`

was. Here's what the final function should do to `x`

for a few
values of `n`

:

`n = 0`

, return`x`

`n = 1`

, apply`f1`

to`x`

, or return`f1(x)`

`n = 2`

, apply`f1`

to`x`

and then`f2`

to the result of that, or return`f2(f1(x))`

`n = 3`

, apply`f1`

to`x`

,`f2`

to the result of applying`f1`

, and then`f3`

to the result of applying`f2`

, or`f3(f2(f1(x)))`

`n = 4`

, start the cycle again applying`f1`

, then`f2`

, then`f3`

, then`f1`

again, or`f1(f3(f2(f1(x))))`

- And so forth.

*Hint*: most of the work goes inside the most nested function.

```
def cycle(f1, f2, f3):
"""Returns a function that is itself a higher-order function.
>>> def add1(x):
... return x + 1
>>> def times2(x):
... return x * 2
>>> def add3(x):
... return x + 3
>>> my_cycle = cycle(add1, times2, add3)
>>> identity = my_cycle(0)
>>> identity(5)
5
>>> add_one_then_double = my_cycle(2)
>>> add_one_then_double(1)
4
>>> do_all_functions = my_cycle(3)
>>> do_all_functions(2)
9
>>> do_more_than_a_cycle = my_cycle(4)
>>> do_more_than_a_cycle(2)
10
>>> do_two_cycles = my_cycle(6)
>>> do_two_cycles(1)
19
"""
"*** YOUR CODE HERE ***"
def ret_fn(n):
def ret(x):
i = 0
while i < n:
if i % 3 == 0:
x = f1(x)
elif i % 3 == 1:
x = f2(x)
else:
x = f3(x)
i += 1
return x
return ret
return ret_fn
```

Use OK to test your code:

`python3 ok -q cycle`

## Recursion

### Question 4: Partition

The number of partitions of a positive integer `n`

is the number of
ways in which `n`

can be expressed as the sum of positive integers in
increasing order. For example, the number `5`

has `7`

partitions.

```
5 = 5
5 = 1 + 4
5 = 2 + 3
5 = 1 + 1 + 3
5 = 1 + 2 + 2
5 = 1 + 1 + 1 + 2
5 = 1 + 1 + 1 + 1 + 1
```

Write a tree-recursive function `part(n)`

that returns the number of
partitions of `n`

.

Hint: Introduce a helper function that computes partitions of `n`

using
only a subset of the integers less than or equal to `n`

. Once you have
done so, you can use very similar logic to the `count_change`

function
from the lecture notes:

```
def part(n):
"""Return the number of partitions of positive integer n.
>>> part(5)
7
>>> part(10)
42
>>> part(15)
176
>>> part(20)
627
"""
"*** YOUR CODE HERE ***"
return part_max(n, n)
def part_max(n, m):
"""Return the number of partitions of n using integers up to m.
>>> part_max(5, 3)
5
"""
if n < 0 or m <= 0:
return 0
if n == 0:
return 1
return part_max(n-m, m) + part_max(n, m-1)
```

Use OK to test your code:

`python3 ok -q part`

### Question 5: Knapsack

You're are a thief, and your job is to pick among `n`

items that are of
different weights and values. You have a knapsack that supports `c`

pounds, and
you want to pick some subset of the items so that you maximize the value you've
stolen.

Define `knapsack`

, which takes a list `weights`

, list `values`

and a capacity
`c`

, and returns that max value. You may assume that item 0 weighs
`weights[0]`

pounds, and is worth `values[0]`

; item 1 weighs `weights[1]`

pounds, and is worth `values[1]`

; etc.

```
def knapsack(weights, values, c):
"""
>>> w = [2, 6, 3, 3]
>>> v = [1, 5, 3, 3]
>>> knapsack(w, v, 6)
6
"""
"*** YOUR CODE HERE ***"
if weights == []:
return 0
else:
first_weight, rest_weights = weights[0], weights[1:]
first_value, rest_values = values[0], values[1:]
with_first = first_value + knapsack(rest_weights, rest_values, c-first_weight)
without_first = knapsack(rest_weights, rest_values, c)
if first_weight <= c:
return max(with_first, without_first)
return without_first
```

Use OK to test your code:

`python3 ok -q knapsack`

## Trees

### Question 6: Sprout leaves

Define a function `sprout_leaves`

that, given a tree, `t`

, and a list
of values, `vals`

, and produces a tree with every leaf having new
branches that contain each of the items in `vals`

. Do not add new
branches to non-leaf nodes.

```
def sprout_leaves(t, vals):
"""Sprout new leaves containing the data in vals at each leaf in
the original tree t and return the resulting tree.
>>> t1 = tree(1, [tree(2), tree(3)])
>>> print_tree(t1)
1
2
3
>>> new1 = sprout_leaves(t1, [4, 5])
>>> print_tree(new1)
1
2
4
5
3
4
5
>>> t2 = tree(1, [tree(2, [tree(3)])])
>>> print_tree(t2)
1
2
3
>>> new2 = sprout_leaves(t2, [6, 1, 2])
>>> print_tree(new2)
1
2
3
6
1
2
"""
"*** YOUR CODE HERE ***"
if is_leaf(t):
return tree(root(t), [tree(v) for v in vals])
return tree(root(t), [sprout_leaves(s, vals) for s in branches(t)])
```

Use OK to test your code:

`python3 ok -q sprout_leaves`

## Lists

### Question 7: Group

Write a recursive function that divides an input sequence (Python list, tuple, string, or range) into a list of smaller sequences that each contain 4 or 5 elements from the original sequence. For example, an input sequence of 14 elements should be divided into sequences of 4, 5, and 5 elements. Use as few 5-element sequences as necessary in the result, and all 5-element sequences should be at the end. Finally, preserve the relative ordering of elements from the original sequence.

*Hint*: You may assume that the input sequence has length at least 12.
Think carefully about how many base cases you need, and what they
should be.

```
def group(seq):
"""Divide a sequence of at least 12 elements into groups of 4 or
5. Groups of 5 will be at the end. Returns a list of sequences, each
corresponding to a group.
>>> group(range(14))
[range(0, 4), range(4, 9), range(9, 14)]
>>> group(list(range(17)))
[[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11], [12, 13, 14, 15, 16]]
"""
num = len(seq)
assert num >= 12
"*** YOUR CODE HERE ***"
if num == 12 or num == 13:
return [seq[:4], seq[4:8], seq[8:]]
elif num == 14:
return [seq[:4], seq[4:9], seq[9:]]
elif num == 15:
return [seq[:5], seq[5:10], seq[10:]]
return [seq[:4]] + group(seq[4:])
```

### Question 8: Deep Length

A list that contains one or more lists as elements is called a *deep* list. For
example, `[1, [2, 3], 4]`

is a deep list.

A deep list of integers is a list containing either integers or deep lists.
Implement `deep_len`

, which takes in a deep list of integers `lst`

. It returns
the number of integers that appear anywhere within `lst`

.

*Hint*: you can check if something is a list by using the built-in `type`

function. For example,

```
>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True
```

```
def deep_len(lst):
"""Returns the deep length of the list.
>>> deep_len([1, 2, 3]) # normal list
3
>>> x = [1, [2, 3], 4] # deep list
>>> deep_len(x)
4
>>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
>>> deep_len(x)
6
>>> x = []
>>> for i in range(100):
... x = [x] + [i] # very deep list
...
>>> deep_len(x)
100
"""
"*** YOUR CODE HERE ***"
if not isinstance(lst, list):
return 1
else:
return sum([deep_len(e) for e in lst])
```

Use OK to test your code:

`python3 ok -q deep_len`

## Linked Lists

### Question 9: Deep Reverse

A linked list that contains one or more linked lists as elements is called a
*deep* linked list. Write a function `deep_reverse`

that takes in a (possibly
deep) linked list and returns a new linked list with the elements in reverse
order. You may write and use helper functions if you find them useful.

*Hint*: You may find Lab 5 helpful.

You can check if something is a linked list by using the provided `is_link`

function. For example,

```
>>> is_link(1)
False
>>> is_link(empty)
True
>>> is_link(link(1, link(2, empty)))
True
```

```
def deep_reverse(lnk):
"""Return a reversed version of a possibly deep linked list lnk.
>>> print_link(deep_reverse(empty))
<>
>>> print_link(deep_reverse(link(1, link(2, empty))))
<2 1>
>>> deep = link(1, link(link(2, link(3, empty)), empty))
>>> deep_reversed = deep_reverse(deep)
>>> print_link(first(deep_reversed))
<3 2>
>>> first(rest(deep_reversed))
1
>>> rest(rest(deep_reversed)) == empty
True
>>> # Additional correctness tests
>>> a = link(1, link(2, empty))
>>> b = link(a, link(3, empty))
>>> c = link(b, a)
>>> c_reversed = deep_reverse(c)
>>> first(c_reversed)
2
>>> first(rest(c_reversed))
1
>>> first(first(rest(rest(c_reversed))))
3
>>> print_link(first(rest(first(rest(rest(c_reversed))))))
<2 1>
>>> deep_reverse(c_reversed) == c
True
"""
"*** YOUR CODE HERE ***"
deep_reversed = empty
while lnk != empty:
elem = first(lnk)
if is_link(elem):
deep_reversed = link(deep_reverse(elem), deep_reversed)
else:
deep_reversed = link(elem, deep_reversed)
lnk = rest(lnk)
return deep_reversed
```

Use OK to test your code:

`python3 ok -q deep_reverse`