Homework 5 Solutions

Solution Files

You can find the solutions in hw05.py.

Required Questions


Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

YouTube link


Midsemester Survey

Q1: Mid-Semester Feedback

As part of this assignment, fill out the Mid-Semester Feedback form.

Once you finish the survey, you will be presented with a passphrase. Put this passphrase, as a string, on the line that says passphrase = 'REPLACE_THIS_WITH_PASSPHRASE' in the Python file for this assignment. E.g. if the passphrase is abc, then the line should be passphrase = 'abc'.

Use Ok to test your code:

python3 ok -q midsem_survey


Generators

If you need a refresher on generators, this may be helpful to read:

We can create our own custom iterators by writing a generator function, which returns a special type of iterator called a generator. Generator functions have yield statements within the body of the function instead of return statements. Calling a generator function will return a generator object and will not execute the body of the function.

For example, let's consider the following generator function:

def countdown(n):
    print("Beginning countdown!")
    while n >= 0:
        yield n
        n -= 1
    print("Blastoff!")

Calling countdown(k) will return a generator object that counts down from k to 0. Since generators are iterators, we can call iter on the resulting object, which will simply return the same object. Note that the body is not executed at this point; nothing is printed and no numbers are outputted.

>>> c = countdown(5)
>>> c
<generator object countdown ...>
>>> c is iter(c)
True

So how is the counting done? Again, since generators are iterators, we call next on them to get the next element! The first time next is called, execution begins at the first line of the function body and continues until the yield statement is reached. The result of evaluating the expression in the yield statement is returned. The following interactive session continues from the one above.

>>> next(c)
Beginning countdown!
5

Unlike functions we've seen before in this course, generator functions can remember their state. On any consecutive calls to next, execution picks up from the line after the yield statement that was previously executed. Like the first call to next, execution will continue until the next yield statement is reached. Note that because of this, Beginning countdown! doesn't get printed again.

>>> next(c)
4
>>> next(c)
3

The next 3 calls to next will continue to yield consecutive descending integers until 0. On the following call, a StopIteration error will be raised because there are no more values to yield (i.e. the end of the function body was reached before hitting a yield statement).

>>> next(c)
2
>>> next(c)
1
>>> next(c)
0
>>> next(c)
Blastoff!
StopIteration

Separate calls to countdown will create distinct generator objects with their own state. Usually, generators shouldn't restart. If you'd like to reset the sequence, create another generator object by calling the generator function again.

>>> c1, c2 = countdown(5), countdown(5)
>>> c1 is c2
False
>>> next(c1)
5
>>> next(c2)
5

Here is a summary of the above:

  • A generator function has a yield statement and returns a generator object.
  • Calling the iter function on a generator object returns the same object without modifying its current state.
  • The body of a generator function is not evaluated until next is called on a resulting generator object. Calling the next function on a generator object computes and returns the next object in its sequence. If the sequence is exhausted, StopIteration is raised.

  • A generator "remembers" its state for the next next call. Therefore,

    • the first next call works like this:

      1. Enter the function and run until the line with yield.
      2. Return the value in the yield statement, but remember the state of the function for future next calls.

    • And subsequent next calls work like this:

      1. Re-enter the function, start at the line after the yield statement that was previously executed, and run until the next yield statement.
      2. Return the value in the yield statement, but remember the state of the function for future next calls.
  • Calling a generator function returns a brand new generator object (like calling iter on an iterable object).
  • A generator should not restart unless it's defined that way. To start over from the first element in a generator, just call the generator function again to create a new generator.

Another useful tool for generators is the yield from statement. yield from will yield all values from an iterator or iterable.

>>> def gen_list(lst):
...     yield from lst
...
>>> g = gen_list([1, 2, 3, 4])
>>> next(g)
1
>>> next(g)
2
>>> next(g)
3
>>> next(g)
4
>>> next(g)
StopIteration

Q2: Infinite Hailstone

Write a generator function that yields the elements of the hailstone sequence starting at number n. After reaching the end of the hailstone sequence, the generator should yield the number 1 indefinitely.

Here is a quick reminder 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.

Try to write this generator function recursively. If you are stuck, you can first try writing it iteratively and then seeing how you can turn that implementation into a recursive one.

Hint: Since hailstone returns a generator, you can yield from a call to hailstone!

def hailstone(n):
    """
    Yields the elements of the hailstone sequence starting at n.
    At the end of the sequence, yield 1 infinitely.

    >>> hail_gen = hailstone(10)
    >>> [next(hail_gen) for _ in range(10)]
    [10, 5, 16, 8, 4, 2, 1, 1, 1, 1]
    >>> next(hail_gen)
    1
    """

    yield n
    if n == 1:
        yield from hailstone(n)
    elif n % 2 == 0:
        yield from hailstone(n // 2)
    else:
        yield from hailstone(n * 3 + 1)

Use Ok to test your code:

python3 ok -q hailstone

Q3: Merge

Definition: An infinite iterator is a iterator that never stops providing values when next is called. For example, ones() evaluates to an infinite iterator:

def ones():
    while True:
        yield 1

Write a generator function merge(a, b) that takes two infinite iterators, a and b, as inputs. Both iterators yield elements in strictly increasing order with no duplicates. Your generator should produce all unique elements from both input iterators in increasing order, without any duplicates.

Note: The input iterators do not contain duplicates within themselves, but they may have common elements between them.

def merge(a, b):
    """
    Return a generator that has all of the elements of generators a and b,
    in increasing order, without duplicates.

    >>> def sequence(start, step):
    ...     while True:
    ...         yield start
    ...         start += step
    >>> a = sequence(2, 3) # 2, 5, 8, 11, 14, ...
    >>> b = sequence(3, 2) # 3, 5, 7, 9, 11, 13, 15, ...
    >>> result = merge(a, b) # 2, 3, 5, 7, 8, 9, 11, 13, 14, 15
    >>> [next(result) for _ in range(10)]
    [2, 3, 5, 7, 8, 9, 11, 13, 14, 15]
    """
    a_val, b_val = next(a), next(b)
    while True:
        if a_val == b_val:

            yield a_val
            a_val, b_val = next(a), next(b)
        elif a_val < b_val:

            yield a_val
            a_val = next(a)
        else:

            yield b_val
            b_val = next(b)

Use Ok to test your code:

python3 ok -q merge

Q4: Stair Ways

Imagine that you want to go up a staircase that has n steps, where n is a positive integer. You can take either one or two steps each time you move.

Write a generator function stair_ways that yields all the different ways you can climb the staircase.

Each "way" of climbing a staircase can be represented by a list of 1s and 2s, where each number indicates whether you take one step or two steps at a time.

For example, for a staircase with 3 steps, there are three ways to climb it:

  • You can take one step each time: [1, 1, 1].
  • You can take two steps then one step: [2, 1].
  • You can take one step then two steps: [1, 2]..

Therefore, stair_ways(3) should yield [1, 1, 1], [2, 1], and [1, 2]. These can be yielded in any order.

Hint: Think about the problem recursively. If you're on some step n, which steps could you have just been on?

def stair_ways(n):
    """
    Yield all the ways to climb a set of n stairs taking
    1 or 2 steps at a time.

    >>> list(stair_ways(0))
    [[]]
    >>> s_w = stair_ways(4)
    >>> sorted([next(s_w) for _ in range(5)])
    [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]]
    >>> list(s_w) # Ensure you're not yielding extra
    []
    """

    if n == 0:
        yield []
    elif n == 1:
        yield [1]
    else:
        for way in stair_ways(n - 1):
            yield [1] + way
        for way in stair_ways(n - 2):
            yield [2] + way

Use Ok to test your code:

python3 ok -q stair_ways

Q5: Yield Paths

Write a generator function yield_paths that takes a tree t and a target value. It yields each path from the root of t to any node with the label value.

Each path should be returned as a list of labels from the root to the matching node. The paths can be yielded in any order.

Hint: If you are having trouble getting started, think about how you would approach this problem if it was not a generator function. What would the recursive steps look like?

Hint: Remember, you can iterate over generator objects because they are a type of iterator!

def yield_paths(t, value):
    """
    Yields all possible paths from the root of t to a node with the label
    value as a list.

    >>> t1 = tree(1, [tree(2, [tree(3), tree(4, [tree(6)]), tree(5)]), tree(5)])
    >>> print_tree(t1)
    1
      2
        3
        4
          6
        5
      5
    >>> next(yield_paths(t1, 6))
    [1, 2, 4, 6]
    >>> path_to_5 = yield_paths(t1, 5)
    >>> sorted(list(path_to_5))
    [[1, 2, 5], [1, 5]]

    >>> t2 = tree(0, [tree(2, [t1])])
    >>> print_tree(t2)
    0
      2
        1
          2
            3
            4
              6
            5
          5
    >>> path_to_2 = yield_paths(t2, 2)
    >>> sorted(list(path_to_2))
    [[0, 2], [0, 2, 1, 2]]
    """
    if label(t) == value:

        yield [value]
    for b in branches(t):

        for path in yield_paths(b, value):
            yield [label(t)] + path

Use Ok to test your code:

python3 ok -q yield_paths

If our current label is equal to value, we've found a path from the root to a node containing value containing only our current label, so we should yield that. From there, we'll see if there are any paths starting from one of our branches that ends at a node containing value. If we find these "partial paths" we can simply add our current label to the beinning of a path to obtain a path starting from the root.

In order to do this, we'll create a generator for each of the branches which yields these "partial paths". By calling yield_paths on each of the branches, we'll create exactly this generator! Then, since a generator is also an iterable, we can iterate over the paths in this generator and yield the result of concatenating it with our current label.

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Pensieve to receive credit for it.

Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Pensieve assignment. Lab 00 has detailed instructions.

Exam Practice

Homework assignments will also contain prior exam questions for you to try. These questions have no submission component; feel free to attempt them if you'd like some practice!

  1. Summer 2016 Final Q8: Zhen-erators Produce Power
  2. Spring 2018 Final Q4(a): Apply Yourself