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
, returnx
n = 1
, applyf1
tox
, or returnf1(x)
n = 2
, applyf1
tox
and thenf2
to the result of that, or returnf2(f1(x))
n = 3
, applyf1
tox
,f2
to the result of applyingf1
, and thenf3
to the result of applyingf2
, orf3(f2(f1(x)))
n = 4
, start the cycle again applyingf1
, thenf2
, thenf3
, thenf1
again, orf1(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