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

1. Pick a positive integer `n` as the start.
2. If `n` is even, divide it by 2.
3. If `n` is odd, multiply it by 3 and add 1.
4. 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
"""
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
"""
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

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.

...     return x + 1
>>> def times2(x):
...     return x * 2
...     return x + 3
>>> identity = my_cycle(0)
>>> identity(5)
5
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
"""
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
"""
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
"""
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
"""
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
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
"""
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``

### 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
True
True``````
``````def deep_reverse(lnk):
"""Return a reversed version of a possibly deep linked list lnk.

<>
<2 1>

>>> deep_reversed = deep_reverse(deep)
<3 2>
>>> first(rest(deep_reversed))
1
>>> rest(rest(deep_reversed)) == empty
True

>>> c_reversed = deep_reverse(c)
>>> first(c_reversed)
2
>>> first(rest(c_reversed))
1
>>> first(first(rest(rest(c_reversed))))
3
<2 1>
>>> deep_reverse(c_reversed) == c
True
"""
``python3 ok -q deep_reverse``