# Homework 5: Generators

*Due by 11:59pm on Thursday, March 9*

## Instructions

Download hw05.zip. Inside the archive, you will find a file called
hw05.py, along with a copy of the `ok`

autograder.

**Submission:** When you are done, submit the assignment by uploading all code files you've edited to Gradescope. 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 Gradescope. See Lab 0 for more instructions on
submitting assignments.

**Using Ok:** If you have any questions about using Ok, please
refer to this guide.

**Readings:** You might find the following references
useful:

**Grading:** Homework is graded based on
correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus.
**This homework is out of 2 points.**

# 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.

### Q1: Infinite Hailstone

Write a generator function that outputs the hailstone sequence starting at number `n`

.
After reaching the end of the hailstone sequence, the generator should yield the value 1 infinitely.

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

- Pick a positive integer
`n`

as the start. - If
`n`

is even, divide it by 2. - If
`n`

is odd, multiply it by 3 and add 1. - Continue this process until
`n`

is 1.

Try to write this generator function recursively. If you're 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
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q hailstone`

### Q2: Merge

Write a generator function `merge`

that takes in two infinite generators `a`

and `b`

that are in increasing order without duplicates and returns a generator that has all the elements of both generators, in increasing order, without duplicates.

```
def merge(a, b):
"""
>>> 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]
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q merge`

### Q3: Generate Permutations

Given a sequence of unique elements, a *permutation* of the sequence is a list
containing the elements of the sequence in some arbitrary order. For example,
`[2, 1, 3]`

, `[1, 3, 2]`

, and `[3, 2, 1]`

are some of the permutations of the
sequence `[1, 2, 3]`

.

Implement `perms`

, a generator function that takes in a sequence `seq`

and returns a generator that yields all permutations of `seq`

. For this question,
assume that `seq`

will not be empty.

Permutations may be yielded in any order. Note that the doctests test whether
you are yielding all possible permutations, but not in any particular order.
The built-in `sorted`

function takes in an iterable object and returns a list
containing the elements of the iterable in non-decreasing order.

Hint:If you had the permutations of all but one of the elements in`seq`

, how could you use that to generate the permutations of the full`seq`

? For example, you can use`perms([1,2])`

to generate permutations for`perms([1,2,3])`

:Try drawing a similar diagram for

`perms([1,2,3,4])`

.

Hint:Remember, it's possible to loop over generator objects because generators are iterators!

```
def perms(seq):
"""Generates all permutations of the given sequence. Each permutation is a
list of the elements in SEQ in a different order. The permutations may be
yielded in any order.
>>> p = perms([100])
>>> type(p)
<class 'generator'>
>>> next(p)
[100]
>>> try: #this piece of code prints "No more permutations!" if calling next would cause an error
... next(p)
... except StopIteration:
... print('No more permutations!')
No more permutations!
>>> sorted(perms([1, 2, 3])) # Returns a sorted list containing elements of the generator
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
>>> sorted(perms((10, 20, 30)))
[[10, 20, 30], [10, 30, 20], [20, 10, 30], [20, 30, 10], [30, 10, 20], [30, 20, 10]]
>>> sorted(perms("ab"))
[['a', 'b'], ['b', 'a']]
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q perms`

### Q4: Yield Paths

Define a generator function `yield_paths`

which takes in a tree `t`

, a value
`value`

, and returns a generator object which yields each path from the root
of `t`

to a node that has label `value`

.

Each path should be represented as a list of the labels along that path in the tree. You may yield the paths in any order.

We have provided a skeleton for you. You do not need to use this skeleton, but if your implementation diverges significantly from it, you might want to think about how you can get it to fit the skeleton.

```
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]]
"""
"*** YOUR CODE HERE ***"
for _______________ in _________________:
for _______________ in _________________:
"*** YOUR CODE HERE ***"
```

Hint:If you're having trouble getting started, think about how you'd approach this problem if it wasn't a generator function. What would your recursive calls be? With a generator function, what happens if you make a "recursive call" within its body?

Hint:Try coming up with a few simple cases of your own! How should this function work when`t`

is a leaf node?

Hint:Remember, it's possible to loop over generator objects because generators are iterators!

Note: Remember that this problem should

yield paths-- do not return a list of paths!

Use Ok to test your code:

`python3 ok -q yield_paths`

## Submit

Make sure to submit this assignment by uploading any files you've edited **to the appropriate Gradescope assignment.** For a refresher on how to do this, refer to Lab 00.

# Optional Questions

### Q5: 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 is a generator of natural numbers
with remainder 1 when divided by `m`

. The last generator yields natural numbers
with remainder `m - 1`

when divided by `m`

.

Hint: To create a generator of infinite natural numbers, you can call the`naturals`

function that's provided in the starter code.

Hint: Consider defining an inner generator function. Each yielded generator varies only in that the elements of each generator have a particular remainder when divided by`m`

. What does that tell you about the argument(s) that the inner function should take in?

```
def remainders_generator(m):
"""
Yields m generators. The ith yielded generator yields natural numbers whose
remainder is i when divided by m.
>>> import types
>>> [isinstance(gen, types.GeneratorType) for gen in remainders_generator(5)]
[True, True, True, True, True]
>>> remainders_four = remainders_generator(4)
>>> for i in range(4):
... print("First 3 natural numbers with remainder {0} when divided by 4:".format(i))
... gen = next(remainders_four)
... for _ in range(3):
... print(next(gen))
First 3 natural numbers with remainder 0 when divided by 4:
4
8
12
First 3 natural numbers with remainder 1 when divided by 4:
1
5
9
First 3 natural numbers with remainder 2 when divided by 4:
2
6
10
First 3 natural numbers with remainder 3 when divided by 4:
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.

Use Ok to test your code:

`python3 ok -q remainders_generator`

# 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!

- Summer 2018 Final Q7a,b: Streams and Jennyrators
- Spring 2019 Final Q1: Iterators are inevitable
- Spring 2021 MT2 Q8: The Tree of L-I-F-E
- Summer 2016 Final Q8: Zhen-erators Produce Power
- Spring 2018 Final Q4a: Apply Yourself