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