# Homework 4 Solutions

## Solution Files

You can find the solutions in hw04.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.

## Generators

### Q1: 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 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: 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):
"""Q3: 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: # 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']]
"""
if not seq:
yield []
else:
for p in perms(seq[1:]):
for i in range(len(seq)):
yield p[:i] + [seq[0]] + p[i:]
```

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.

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

## OOP

### Q5: Minty

A mint is a place where coins are made. In this question, you'll implement a `Minty`

class that can output a `Coin`

with the correct year and worth.

- Each
`Minty`

instance has a`year`

stamp. The`update`

method sets the`year`

stamp to the`present_year`

class attribute of the`Minty`

class. - The
`create`

method in`Minty`

returns an instance of`Coin`

stamped with the`Minty`

instance's year (which may be different from`Minty.present_year`

if the stamp has not been updated.) - The
`Coin`

constructor should ensure that each coin has the correct year and denomination value (`cents`

), specific to the type of coin (in our case, just 'Dime' or 'Nickel'). - A
`Coin`

's`worth`

method returns its`cents`

value plus an additional cent for each year of age beyond 50 years. A coin's age can be determined by subtracting the coin's year from the`present_year`

class attribute of the`Minty`

class.

Note: The getting started video for this problem covers a version that includes inheritance, but this problem does not involve inheritance.

```
class Minty:
"""A mint creates coins by stamping on years. The update method sets the mint's stamp to Minty.present_year.
>>> mint = Minty()
>>> mint.year
2021
>>> dime = mint.create('Dime')
>>> dime.year
2021
>>> Minty.present_year = 2101 # Time passes
>>> nickel = mint.create('Nickel')
>>> nickel.year # The mint has not updated its stamp yet
2021
>>> nickel.worth() # 5 cents + (80 - 50 years)
35
>>> mint.update() # The mint's year is updated to 2101
>>> Minty.present_year = 2176 # More time passes
>>> mint.create('Dime').worth() # 10 cents + (75 - 50 years)
35
>>> Minty().create('Dime').worth() # A new mint has the current year
10
>>> dime.worth() # 10 cents + (155 - 50 years)
115
"""
present_year = 2021
def __init__(self):
self.update()
def create(self, type):
return Coin(self.year, type)
def update(self):
self.year = Minty.present_year
class Coin:
cents = 50
def __init__(self, year, type):
self.year = year
if type == ('Dime'):
self.cents = 10
elif type == ('Nickel'):
self.cents = 5
def worth(self):
return self.cents + max(0, Minty.present_year - self.year - 50)
```

Use Ok to test your code:

`python3 ok -q Minty`

### Q6: Vending Machine

In this question you'll create a vending machine that sells a single product and provides change when needed.

Create a class called `VendingMachine`

that represents a vending
machine for some product. A `VendingMachine`

object returns strings
describing its interactions. Make sure your output *exactly* matches the strings in the doctests including punctuation and spacing!

You may find Python's formatted string literals, or f-strings useful. A quick example:

`>>> feeling = 'love' >>> course = '61A!' >>> f'I {feeling} {course}' 'I love 61A!'`

Fill in the `VendingMachine`

class, *adding attributes and methods as appropriate*, such that its behavior matches the following doctests:

```
class VendingMachine:
"""A vending machine that vends some product for some price.
>>> v = VendingMachine('candy', 10)
>>> v.vend()
'Nothing left to vend. Please restock.'
>>> v.add_funds(15)
'Nothing left to vend. Please restock. Here is your $15.'
>>> v.restock(2)
'Current candy stock: 2'
>>> v.vend()
'Please add $10 more funds.'
>>> v.add_funds(7)
'Current balance: $7'
>>> v.vend()
'Please add $3 more funds.'
>>> v.add_funds(5)
'Current balance: $12'
>>> v.vend()
'Here is your candy and $2 change.'
>>> v.add_funds(10)
'Current balance: $10'
>>> v.vend()
'Here is your candy.'
>>> v.add_funds(15)
'Nothing left to vend. Please restock. Here is your $15.'
>>> w = VendingMachine('soda', 2)
>>> w.restock(3)
'Current soda stock: 3'
>>> w.restock(3)
'Current soda stock: 6'
>>> w.add_funds(2)
'Current balance: $2'
>>> w.vend()
'Here is your soda.'
"""
def __init__(self, product, price):
self.product = product
self.price = price
self.stock = 0
self.balance = 0
def restock(self, n):
self.stock += n
return f'Current {self.product} stock: {self.stock}'
def add_funds(self, n):
if self.stock == 0:
return f'Nothing left to vend. Please restock. Here is your ${n}.'
# Alternatively, we could have:
# return self.vend() + f' Here is your ${n}.'
self.balance += n
return f'Current balance: ${self.balance}'
def vend(self):
if self.stock == 0:
return 'Nothing left to vend. Please restock.'
difference = self.price - self.balance
if difference > 0:
return f'Please add ${difference} more funds.'
message = f'Here is your {self.product}'
if difference != 0:
message += f' and ${-difference} change'
self.balance = 0
self.stock -= 1
return message + '.'
```

Use Ok to test your code:

`python3 ok -q VendingMachine`

Reading through the doctests, it should be clear which functions we should add to ensure that the vending machine class behaves correctly.

`__init__`

- This can be difficult to fill out at first. Both
`product`

and`price`

seem pretty obvious to keep around, but`stock`

and`balance`

are quantities that are needed only after attempting other functions.

`restock`

- Even though
`v.restock(2)`

takes only one argument in the doctest, remember that`self`

is bound to the object the`restock`

method is invoked on. Therefore, this function has two parameters. - While implementing this function, you will probably realize that you would
like to keep track of the stock somewhere. While it might be possible to set
the stock in this function as an instance attribute, it would lose whatever
the old stock was.
Therefore, the natural solution is to initialize stock in the constructor, and
then update it in
`restock`

.

`add_funds`

- This behaves very similarly to
`restock`

. See comments above. - Also yes, this is quite the expensive vending machine.

`vend`

The trickiest thing here is to make sure we handle all the cases. You may find it helpful when implementing a problem like this to keep track of all the errors we run into in the doctest.

- No stock
- Not enough balance
- Leftover balance after purchase (return change to customer)
- No leftover balance after purchase

We use some string concatenation at the end when handling case 3 and 4 to try and reduce the amount of code. This isn't necessary for correctness -- it's ok to have something like:

`if difference != 0: return ... else: return ...`

Of course, that would require decrementing the balance and stock beforehand.

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

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-level questions for you to take a look at. These questions have no submission component; feel free to attempt them if you'd like a challenge!

Generators

- 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

Object-Oriented Programming

- Spring 2022 MT2 Q8: CS61A Presents The Game of Hoop.
- Fall 2020 MT2 Q3: Sparse Lists