# Homework 4: Nonlocal, OOP, Linked Lists, Trees hw04.zip

Due by 11:59pm on Monday, 7/29

## Instructions

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

Submission: When you are done, submit with python3 ok --submit. 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 okpy.org. 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 effort, not correctness. However, there is no partial credit; you must show substantial effort on every problem to receive any points.

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

Use Ok to test your code:

python3 ok -q make_fib

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:

1. Store that incorrect password in a list, and
2. 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:

>>> w = make_withdraw(100, 'hax0r')
>>> w(25, 'hax0r')
75
>>> error = w(90, 'hax0r')
>>> error
'Insufficient funds'
>>> error = w(25, 'hwat')
>>> error
>>> new_bal = w(25, 'hax0r')
>>> new_bal
50
>>> w(75, 'a')
>>> w(10, 'hax0r')
40
>>> w(20, 'n00b')
>>> 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
"""

Use Ok to test your code:

python3 ok -q make_withdraw

## 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):

def update(self):

class Coin:
def __init__(self, year):
self.year = year

def worth(self):

class Nickel(Coin):
cents = 5

class Dime(Coin):
cents = 10

Use Ok to test your code:

python3 ok -q Mint

### 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()
>>> 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()
"""

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]'

Use Ok to test your code:

python3 ok -q VendingMachine

Note: The following question covers material that will be gone over in class on 7/24. 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.

"""Remove all the nodes containing value in link. Assume that the
first element is never removed.

>>> 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>
"""

Use Ok to test your code:

python3 ok -q remove_all

## Generators/Trees

Note: The following question covers material that will be gone over in class on 7/24. 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]]
"""