Homework 11
Due at 11:59:59 pm on Sunday, 11/29/2020.

hw11.zip

Instructions

Download hw11.zip. Inside the archive, you will find starter files for the questions in this homework, along with a copy of the OK autograder.

Submission: When you are done, submit with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on okpy.org. See this article for more instructions on okpy and submitting assignments.

Readings: This homework relies on following references:

Tree Questions

Question 1: 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 t 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_map(lambda x: 2**x, numbers))
    2
      4
        8
        16
      32
        64
          128
        256
    >>> print(numbers)
    1
      2
        3
        4
      5
        6
          7
        8
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q tree_map

Question 2: Add Leaves

Implement add_d_leaves, a function that takes in a Tree instance t and mutates it so that at each depth d in the tree, d leaves with labels v are added to each node at that depth. For example, we want to add 1 leaf with v in it to each node at depth 1, 2 leaves to each node at depth 2, and so on.

Recall that the depth of a node is the number of edges from that node to the root, so the depth of the root is 0. The leaves should be added to the end of the list of branches.

def add_d_leaves(t, v):
    """Add d leaves containing v to each node at every depth d.

    >>> t1 = Tree(1, [Tree(3)])
    >>> add_d_leaves(t1, 4)
    >>> t1
    Tree(1, [Tree(3, [Tree(4)])])
    >>> t2 = Tree(2, [Tree(5), Tree(6)])
    >>> t3 = Tree(3, [t1, Tree(0), t2])
    >>> add_d_leaves(t3, 10)
    >>> print(t3)
    3
      1
        3
          4
            10
            10
            10
          10
          10
        10
      0
        10
      2
        5
          10
          10
        6
          10
          10
        10
    """
    def add_leaves(t, d):
        "*** YOUR CODE HERE ***"
    add_leaves(t, 0)

Use OK to test your code:

python3 ok -q add_d_leaves

Iterator/Generator Questions

Question 3: Restart

Implement an iterator class called IteratorRestart that will reset to the beginning when __iter__ is called again.

class IteratorRestart:
    """
    >>> iterator = IteratorRestart(2, 7)
    >>> for num in iterator:
    ...     print(num)
    2
    3
    4
    5
    6
    7
    >>> for num in iterator:
    ...     print(num)
    2
    3
    4
    5
    6
    7
    """
    def __init__(self, start, end):
        "*** YOUR CODE HERE ***"

    def __next__(self):
        "*** YOUR CODE HERE ***"

    def __iter__(self):
        "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q IteratorRestart

Question 4: Primes

Write a generator that generates prime numbers. Fill out the is_prime helper function and use that to create your generator.

def is_prime(n):
    """
    Return True if n is prime, false otherwise.

    >>> is_prime(1)
    False
    >>> is_prime(2)
    True
    >>> is_prime(19)
    True
    """
    "*** YOUR CODE HERE ***"
 
def primes():
    """
    An infinite generator that outputs primes. 

    >>> p = primes()
    >>> for i in range(3):
    ...     print(next(p))
    ...
    2
    3
    5
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q is_prime

Use OK to test your code:

python3 ok -q primes

Question 5: Merge

Implement merge(s0, s1), which takes two iterables s0 and s1 whose elements are ordered. merge yields elements from s0 and s1 in sorted order, eliminating repetition. You may also assume s0 and s1 represent infinite sequences; that is, their iterators never raise StopIteration.

See the doctests for example behavior.

def merge(s0, s1):
    """Yield the elements of strictly increasing iterables s0 and s1 and
    make sure to remove the repeated values in both.
    You can also assume that s0 and s1 represent infinite sequences.

    >>> twos = naturals(initial = 2, step = 2)
    >>> threes = naturals(initial = 3, step = 3)
    >>> m = merge(twos, threes)
    >>> type(m)
    <class 'generator'>
    >>> [next(m) for _ in range(10)]
    [2, 3, 4, 6, 8, 9, 10, 12, 14, 15]
    """
    i0, i1 = iter(s0), iter(s1)
    e0, e1 = next(i0), next(i1)
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q merge

Submit

Make sure to submit this assignment by running:

python3 ok --submit

Project

Friendy reminder to work on your project! The checkpoint is due November 20th! Good luck!