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

### Q1: Infinite Hailstone

Write a generator function that yiels the elements of the hailstone sequence starting at number `n`

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

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):
"""Q1: 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`

### 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):
"""Q2:
>>> 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]
"""
first_a, first_b = next(a), next(b)
while True:
if first_a == first_b:
yield first_a
first_a, first_b = next(a), next(b)
elif first_a < first_b:
yield first_a
first_a = next(a)
else:
yield first_b
first_b = next(b)
```

Use Ok to test your code:

`python3 ok -q merge`

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

```
def yield_paths(t, value):
"""Q4: 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
```

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`

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 Gradescope to receive credit for it.

## Submit

Submit this assignment by uploading any files you've edited **to the appropriate Gradescope 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!

- 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