Homework 6

Due by 11:59pm on Sunday, 10/30/16

Instructions

Download hw06.zip. Inside the archive, you will find a file called hw06.py, along with a copy of the OK autograder. Upload the zip file to Jupyter to complete the assignment. See Lab 0 for instructions on using Jupyter to complete assignments.

Submission: When you are done, submit the assignment by uploading the .py file to okpy.org. You may submit more than once before the deadline; only the final submission will be scored. See Lab 0 for instructions on submitting assignments.

Readings: This homework relies on following references:

Generators

Question 1: Hailstone

Write a generator that outputs the hailstone sequence from homework 1.

Here's a quick remainder of how the hailstone sequence is defined:

  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 hailstone(n):
    """
    >>> for num in hailstone(10):
    ...     print(num)
    ...
    10
    5
    16
    8
    4
    2
    1
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python ok -q hailstone --local

Question 2: Scale

Implement the generator function scale(s, k), which yields elements of the given iterable s, scaled by k.

def scale(s, k):
    """Yield elements of the iterable s scaled by a number k.

    >>> s = scale([1, 5, 2], 5)
    >>> type(s)
    <class 'generator'>
    >>> list(s)
    [5, 25, 10]

    >>> m = scale(naturals(), 2)
    >>> [next(m) for _ in range(5)]
    [2, 4, 6, 8, 10]
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python ok -q scale --local

Question 3: 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 = scale(naturals(), 2)
    >>> threes = scale(naturals(), 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:

python ok -q merge --local

Question 4: Remainder generator

Like functions, generators can also be higher-order. For this problem, we will be writing remainders_generator, which yields a series of generator objects.

remainders_generator takes in an integer m, and yields m different generators. The first generator is a generator of multiples of m, i.e. numbers where the remainder is 0. The second, a generator of natural numbers with remainder 1 when divided by m. The last generator yield natural numbers with remainder m - 1 when divided by m.

def remainders_generator(m):
    """
    Takes in an integer m, and yields m different remainder groups
    of m.

    >>> remainders_mod_four = remainders_generator(4)
    >>> for rem_group in remainders_mod_four:
    ...     for _ in range(3):
    ...         print(next(rem_group))
    0
    4
    8
    1
    5
    9
    2
    6
    10
    3
    7
    11
    """
    "*** YOUR CODE HERE ***"

Note that if you have implemented this correctly, each of the generators yielded by remainder_generator will be infinite - you can keep calling next on them forever without running into a StopIteration exception.

Hint: Consider defining an inner generator function. What arguments should it take in? Where should you call it?

Use OK to test your code:

python ok -q remainders_generator --local