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:

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

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)

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