# Homework 4: Nonlocal, OOP, Linked Lists, Trees

*Due by 11:59pm on Wednesday, 11/27*

## Instructions

Download hw04.zip. Inside the archive, you will find a file called
**hw04.py**.

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

# Required questions

## Nonlocal

### Q1: Next Fibonacci

Write a function `make_fib`

that returns a function that returns the
next Fibonacci number each time it is called. (The Fibonacci sequence begins with 0
and then 1, after which each element is the sum of the preceding two.)
Use a `nonlocal`

statement!

```
def make_fib():
"""Returns a function that returns the next Fibonacci number
every time it is called.
>>> fib = make_fib()
>>> fib()
0
>>> fib()
1
>>> fib()
1
>>> fib()
2
>>> fib()
3
>>> fib2 = make_fib()
>>> fib() + sum([fib2() for _ in range(5)])
12
"""
"*** YOUR CODE HERE ***"
```

### Q2: Password Protected Account

In lecture, we saw how to use functions to create mutable objects.
Here, for example, is the function `make_withdraw`

which produces a
function that can withdraw money from an account:

```
def make_withdraw(balance):
"""Return a withdraw function with BALANCE as its starting balance.
>>> withdraw = make_withdraw(1000)
>>> withdraw(100)
900
>>> withdraw(100)
800
>>> withdraw(900)
'Insufficient funds'
"""
def withdraw(amount):
nonlocal balance
if amount > balance:
return 'Insufficient funds'
balance = balance - amount
return balance
return withdraw
```

Write a version of the `make_withdraw`

function that returns
password-protected withdraw functions. That is, `make_withdraw`

should
take a password argument (a string) in addition to an initial balance.
The returned function should take two arguments: an amount to withdraw
and a password.

A password-protected `withdraw`

function should only process
withdrawals that include a password that matches the original. Upon
receiving an incorrect password, the function should:

- Store that incorrect password in a list, and
- Return the string 'Incorrect password'.

If a withdraw function has been called three times with incorrect
passwords `p1`

, `p2`

, and `p3`

, then it is locked. All subsequent
calls to the function should return:

`"Your account is locked. Attempts: [<p1>, <p2>, <p3>]"`

The incorrect passwords may be the same or different:

```
def make_withdraw(balance, password):
"""Return a password-protected withdraw function.
>>> w = make_withdraw(100, 'hax0r')
>>> w(25, 'hax0r')
75
>>> error = w(90, 'hax0r')
>>> error
'Insufficient funds'
>>> error = w(25, 'hwat')
>>> error
'Incorrect password'
>>> new_bal = w(25, 'hax0r')
>>> new_bal
50
>>> w(75, 'a')
'Incorrect password'
>>> w(10, 'hax0r')
40
>>> w(20, 'n00b')
'Incorrect password'
>>> w(10, 'hax0r')
"Your account is locked. Attempts: ['hwat', 'a', 'n00b']"
>>> w(10, 'l33t')
"Your account is locked. Attempts: ['hwat', 'a', 'n00b']"
>>> type(w(10, 'l33t')) == str
True
"""
"*** YOUR CODE HERE ***"
```

## OOP

### Q3: Mint

Complete the `Mint`

and `Coin`

classes so that the coins created by a mint have
the correct year and worth.

- Each
`Mint`

instance has a`year`

stamp. The`update`

method sets the`year`

stamp to the`current_year`

class attribute of the`Mint`

class. - The
`create`

method takes a subclass of`Coin`

and returns an instance of that class stamped with the`mint`

's year (which may be different from`Mint.current_year`

if it has not been updated.) - A
`Coin`

's`worth`

method returns the`cents`

value of the coin plus one extra cent for each year of age beyond 50. A coin's age can be determined by subtracting the coin's year from the`current_year`

class attribute of the`Mint`

class.

```
class Mint:
"""A mint creates coins by stamping on years.
The update method sets the mint's stamp to Mint.current_year.
>>> mint = Mint()
>>> mint.year
2019
>>> dime = mint.create(Dime)
>>> dime.year
2019
>>> Mint.current_year = 2100 # Time passes
>>> nickel = mint.create(Nickel)
>>> nickel.year # The mint has not updated its stamp yet
2019
>>> nickel.worth() # 5 cents + (81 - 50 years)
36
>>> mint.update() # The mint's year is updated to 2100
>>> Mint.current_year = 2175 # More time passes
>>> mint.create(Dime).worth() # 10 cents + (75 - 50 years)
35
>>> Mint().create(Dime).worth() # A new mint has the current year
10
>>> dime.worth() # 10 cents + (106 - 50 years)
116
>>> Dime.cents = 20 # Upgrade all dimes!
>>> dime.worth() # 20 cents + (106 - 50 years)
126
"""
current_year = 2019
def __init__(self):
self.update()
def create(self, kind):
"*** YOUR CODE HERE ***"
def update(self):
"*** YOUR CODE HERE ***"
class Coin:
def __init__(self, year):
self.year = year
def worth(self):
"*** YOUR CODE HERE ***"
class Nickel(Coin):
cents = 5
class Dime(Coin):
cents = 10
```

### Q4: Vending Machine

Create a class called `VendingMachine`

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

object returns strings
describing its interactions.

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()
'Machine is out of stock.'
>>> v.deposit(15)
'Machine is out of stock. Here is your $15.'
>>> v.restock(2)
'Current candy stock: 2'
>>> v.vend()
'You must deposit $10 more.'
>>> v.deposit(7)
'Current balance: $7'
>>> v.vend()
'You must deposit $3 more.'
>>> v.deposit(5)
'Current balance: $12'
>>> v.vend()
'Here is your candy and $2 change.'
>>> v.deposit(10)
'Current balance: $10'
>>> v.vend()
'Here is your candy.'
>>> v.deposit(15)
'Machine is out of stock. Here is your $15.'
>>> w = VendingMachine('soda', 2)
>>> w.restock(3)
'Current soda stock: 3'
>>> w.restock(3)
'Current soda stock: 6'
>>> w.deposit(2)
'Current balance: $2'
>>> w.vend()
'Here is your soda.'
"""
"*** YOUR CODE HERE ***"
```

You may find Python string formatting syntax useful. A quick example:

```
>>> ten, twenty, thirty = 10, 'twenty', [30]
>>> '{0} plus {1} is {2}'.format(ten, twenty, thirty)
'10 plus twenty is [30]'
```

## Linked Lists

Note: The following question covers material that will be gone over in class on 11/20. Do not worry if you cannot attempt it until then.

### Q5: Remove All

Implement a function `remove_all`

that takes a `Link`

, and a `value`

,
and remove any linked list node containing that value. You can assume the
list already has at least one node containing `value`

and the first element is
never removed. Notice that you are not returning anything, so you should mutate the list.

```
def remove_all(link , value):
"""Remove all the nodes containing value in link. Assume that the
first element is never removed.
>>> l1 = Link(0, Link(2, Link(2, Link(3, Link(1, Link(2, Link(3)))))))
>>> print(l1)
<0 2 2 3 1 2 3>
>>> remove_all(l1, 2)
>>> print(l1)
<0 3 1 3>
>>> remove_all(l1, 3)
>>> print(l1)
<0 1>
>>> remove_all(l1, 3)
>>> print(l1)
<0 1>
"""
"*** YOUR CODE HERE ***"
```

## Generators/Trees

Note: The following question covers material that will be gone over in class on 11/20. Do not worry if you cannot attempt it until then.

### Q6: Generate Paths

Define a generator function `generate_paths`

which takes in a Tree `t`

, a value
`x`

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

to a node that has label `x`

.

`t`

is implemented with a class, not as the function-based ADT.

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 (partial) 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 generate_paths(t, x):
"""Yields all possible paths from the root of t to a node with the label x
as a list.
>>> t1 = Tree(1, [Tree(2, [Tree(3), Tree(4, [Tree(6)]), Tree(5)]), Tree(5)])
>>> print(t1)
1
2
3
4
6
5
5
>>> next(generate_paths(t1, 6))
[1, 2, 4, 6]
>>> path_to_5 = generate_paths(t1, 5)
>>> sorted(list(path_to_5))
[[1, 2, 5], [1, 5]]
>>> t2 = Tree(0, [Tree(2, [t1])])
>>> print(t2)
0
2
1
2
3
4
6
5
5
>>> path_to_2 = generate_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 "recurisve call" within its body?