61A Homework 8

Due by 11:59pm on Wednesday, 7/23

Readings: You might find the following references useful:

Submission: See the online submission instructions. We have provided a hw8.py starter file for the questions below.

Table of Contents

Nonlocal

Question 1

Define a function make_accumulator that returns an accumulator function, which takes one numerical argument and returns the sum of all arguments ever passed to accumulator. You should use a list to store all of the arguments passed to accumulator. Do not use a nonlocal statement.

def make_accumulator():
    """Return an accumulator function that takes a single numeric argument and
    accumulates that argument into total, then returns total.

    >>> acc = make_accumulator()
    >>> acc(15)
    15
    >>> acc(10)
    25
    >>> acc2 = make_accumulator()
    >>> acc2(7)
    7
    >>> acc3 = acc2
    >>> acc3(6)
    13
    >>> acc2(5)
    18
    >>> acc(4)
    29
    """
    "*** YOUR CODE HERE ***"

Question 2

Define a function make_accumulator_nonlocal that returns an accumulator function, which takes one numerical argument and returns the sum of all arguments ever passed to accumulator. Use a nonlocal statement, but no list or dict.

def make_accumulator_nonlocal():
    """Return an accumulator function that takes a single numeric argument and
    accumulates that argument into total, then returns total.

    >>> acc = make_accumulator_nonlocal()
    >>> acc(15)
    15
    >>> acc(10)
    25
    >>> acc2 = make_accumulator_nonlocal()
    >>> acc2(7)
    7
    >>> acc3 = acc2
    >>> acc3(6)
    13
    >>> acc2(5)
    18
    >>> acc(4)
    29
    """
    "*** YOUR CODE HERE ***"

Object Oriented Programming

Question 3

Write a class Amount that represents a collection of nickels and pennies. Include a property called value that computes the total monetary value of the amount from the nickels and pennies. Do not add an instance attribute called value to each Amount instance. Instead, an Amount should have only two instance attributes: nickels and pennies. value should be a property method, which is a method that can be accessed as though it were an instance attribute. See the relevant Python Property docs. In particular, look at the @property decorator. You do not need to support direct assignment to value, although you are welcome to add that feature as well.

Finally, write a subclass MinimalAmount with base class Amount that overrides the constructor so that all amounts are minimal upon construction. An Amount instance is minimal if it has no more than four pennies, but the same value as the nickel and penny quantities passed as arguments. Note that if the pennies instance attribute is changed after the object is constructed, it is fine if the amount is no longer minimal.

class Amount(object):
    """An amount of nickels and pennies.

    >>> a = Amount(3, 7)
    >>> a.nickels
    3
    >>> a.pennies
    7
    >>> a.value
    22
    >>> a.nickels = 5
    >>> a.value
    32

    """
    "*** YOUR CODE HERE ***"

class MinimalAmount(Amount):
    """An amount of nickels and pennies that is initialized with no more than
    four pennies, by converting excess pennies to nickels.

    >>> a = MinimalAmount(3, 7)
    >>> a.nickels, a.pennies, a.value  # Creates a tuple
    (4, 2, 22)
    >>> a = MinimalAmount(7, 3)
    >>> a.nickels, a.pennies, a.value
    (7, 3, 38)
    >>> a = MinimalAmount(0, 50)
    >>> a.nickels, a.pennies, a.value
    (10, 0, 50)
    """
    "*** YOUR CODE HERE ***"

Question 4

Create a class called VendingMachine that represents a vending machine for some product. A VendingMachine object returns strings describing its interactions. See the doctest for examples.

You may find the format method of strings helpful:

>>> 'I {0}, you {0}, we all {0} for {1}!'.format('scream', 'ice cream')
'I scream, you scream, we all scream for ice cream!'

The format method can take a variable number of arguments.

class VendingMachine:
    """A vending machine that vends some product for some price.

    >>> v = VendingMachine('candy', 10)
    >>> v.vend()
    'Machine is out of stock.'
    >>> v.restock(1)
    'Current candy stock: 1'
    >>> v.vend()
    'You must deposit $10 more.'
    >>> v.deposit(7)
    'Current balance: $7'
    >>> v.vend()
    'You must deposit $3 more.'
    >>> v.restock(1)
    'Current candy stock: 2'
    >>> 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.'
    >>> v.vend()
    'Machine is out of stock.'
    >>> p = VendingMachine('pepsi', 21)
    >>> p.restock(100)
    'Current pepsi stock: 100'
    >>> p.deposit(100)
    'Current balance: $100'
    >>> p.vend()
    'Here is your pepsi and $79 change.'
    >>> p.deposit(21)
    'Current balance: $21'
    >>> p.vend()
    'Here is your pepsi.'
    """
    "*** YOUR CODE HERE ***"

Question 5

Create a class called MissManners that promotes politeness among our objects. A MissManners object takes another object on construction. It has one method, called ask. It responds by calling methods on the object it contains, but only if the caller said please first.

You will need to use getattr and hasattr. Try the following in the interpreter to see how they work:

class Foo:
    bar = 3
    def __init__(self, baz):
        self.baz = baz
    def change_baz(self, new_baz):
        self.baz = new_baz

f = Foo(10)
f.bar
f.baz
hasattr(f, 'baz')
hasattr(f, 'garply')
hasattr(f, 'bazbar'[:3])
hasattr(f, 'bazbar'[3:])
getattr(f, 'baz')
getattr(f, 'bar')
getattr(f, 'garply')
setattr(f, 'garply', 20)
f.garply
hasattr(f, '__init__')
hasattr(f, 'change_baz')
getattr(f, 'change_baz')
getattr(f, 'change_baz')(42)
f.baz

Hint: Your implementation will need to use the *args notation that allows functions to take a variable number of arguments.

class MissManners:
    """A container class that only forward messages that say please.

    >>> v = VendingMachine('teaspoon', 10)
    >>> v.restock(2)
    'Current teaspoon stock: 2'
    >>> m = MissManners(v)
    >>> m.ask('vend')
    'You must learn to say please first.'
    >>> m.ask('please vend')
    'You must deposit $10 more.'
    >>> m.ask('please deposit', 20)
    'Current balance: $20'
    >>> m.ask('now will you vend?')
    'You must learn to say please first.'
    >>> m.ask('please hand over a teaspoon')
    'Thanks for asking, but I know not how to hand over a teaspoon'
    >>> m.ask('please vend')
    'Here is your teaspoon and $10 change.'
    """
    "*** YOUR CODE HERE ***"

Optional Problems

Question 6

The textbook shows 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. If a withdraw function has been called three times with incorrect passwords then it is locked. All subsequent calls to the function should specify that the account is locked, and list the incorrect password attempts. 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
    >>> w(90, 'hax0r')
    'Insufficient funds'
    >>> w(25, 'hwat')
    'Incorrect password'
    >>> w(25, 'hax0r')
    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']"
    """
    "*** YOUR CODE HERE ***"

Question 7: Challenge Problem (optional)

Recall the count_change function from earlier in the semester. (We have converted it to use a Python list rather than a linked list to represent a coin sequence, but it is otherwise the same.) It was quite slow on larger inputs, since it repeated the same computation many times. Write a function make_count_change that produces a more efficient version of count_change. This more efficient version should only perform any computation if it is called with a new pair of arguments. If it is called with a pair of arguments previously seen, then it should just return the previously computed value. This technique is known as memoization.

Once you are done, compare the two versions on a large number such as 500 to make sure that your code is faster than the original version.

# Old version
def count_change(a, coins=(50, 25, 10, 5, 1)):
    if a == 0:
        return 1
    elif a < 0 or len(coins) == 0:
        return 0
    return count_change(a, coins[1:]) + count_change(a - coins[0], coins)

# Version 2.0
def make_count_change():
    """Return a function to efficiently count the number of ways to make
    change.

    >>> cc = make_count_change()
    >>> cc(500, (50, 25, 10, 5, 1))
    59576
    """
    "*** YOUR CODE HERE ***"