Homework 5
Due by 11:59pm on Wednesday, 10/7
Instructions
Download hw05.zip. Inside the archive, you will find a file called hw05.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. See Lab 1 for 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:
Trees
The following problems use the same tree
data abstraction as lecture, but
with a different implementation. The code you write should not need to refer to
'<root>'
or '<branches>'
directly; that's an abstraction barrier violation.
The print_tree
function is provided for convenience:
##############################################################
# An alternative implementation of the tree data abstraction #
##############################################################
def tree(root, branches=[]):
for branch in branches:
assert is_tree(branch), 'branches must be trees'
return {'<root>': root, '<branches>': branches}
def root(tree):
return tree['<root>']
def branches(tree):
return tree['<branches>']
def is_tree(tree):
if type(tree) != dict or '<root>' not in tree or '<branches>' not in tree:
return False
for branch in branches(tree):
if not is_tree(branch):
return False
return True
def is_leaf(tree):
return not branches(tree)
numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
def print_tree(t, indent=0):
"""Print a representation of this tree in which each node is
indented by two spaces times its depth from the root.
>>> print_tree(tree(1))
1
>>> print_tree(tree(1, [tree(2)]))
1
2
>>> print_tree(numbers)
1
2
3
4
5
6
7
"""
print(' ' * indent + str(root(t)))
for branch in branches(t):
print_tree(branch, indent + 1)
Mobiles
Acknowledgements. This mobile example is based on a classic problem from Structure and Interpretation of Computer Programs, Section 2.2.2.
A mobile is a type of hanging sculpture. A binary mobile consists of two sides. Each side is a rod of a certain length, from which hangs either a weight or another mobile.
We will represent a binary mobile using the data abstractions below, which use
the tree
data abstraction for their representation.
- A
mobile
has a left side (index 0) and a right side (index 1). - A
side
has a length and a structure, which is either amobile
orweight
. - A
weight
has a size, which is a positive number.
Question 1
Implement the weight
data abstraction by completing the weight
constructor, the size
selector, and the is_weight
predicate so that a weight is represented using a tree. The total_weight
example is provided to demonstrate use of the mobile, side, and weight
abstractions.
def mobile(left, right):
"""Construct a mobile from a left side and a right side."""
return tree(None, [left, right])
def sides(m):
"""Select the sides of a mobile."""
return branches(m)
def side(length, mobile_or_weight):
"""Construct a side: a length of rod with a mobile or weight at the end."""
return tree(length, [mobile_or_weight])
def length(s):
"""Select the length of a side."""
return root(s)
def end(s):
"""Select the mobile or weight hanging at the end of a side."""
return branches(s)[0]
def weight(size):
"""Construct a weight of some size."""
assert size > 0
"*** YOUR CODE HERE ***"
def size(w):
"""Select the size of a weight."""
"*** YOUR CODE HERE ***"
def is_weight(w):
"""Whether w is a weight, not a mobile."""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q total_weight
Question 2
Implement the with_totals
function, which takes a mobile
and returns a tree
representation of that same mobile in which the root value of each mobile tree
is the total weight of the mobile it represents (instead of None
).
Hint: You should not need to violate the tree
abstraction, but this function
does need to assume that a mobile is a tree.
def with_totals(m):
"""Return a mobile with total weights stored as the root of each mobile.
>>> t, u, v = examples()
>>> print_tree(t)
None
1
2
2
1
>>> print_tree(with_totals(t))
3
1
2
2
1
>>> print_tree(t) # t should not change
None
1
2
2
1
>>> print_tree(with_totals(v))
9
4
3
1
2
2
1
2
6
5
1
1
5
2
3
3
2
>>> print_tree(v) # v should not change
None
4
None
1
2
2
1
2
None
5
1
1
None
2
3
3
2
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q with_totals
Question 3
Implement the balanced
function, which returns whether m
is a balanced
mobile. A mobile is said to be balanced if the torque applied by its left
side is equal to that applied by its right side (that is, if the length
of the left rod multiplied by the total weight hanging from that rod is equal
to the corresponding product for the right side) and if each of the submobiles
hanging off its sides is balanced.
def balanced(m):
"""Return whether m is balanced.
>>> t, u, v = examples()
>>> balanced(t)
True
>>> balanced(v)
True
>>> w = mobile(side(3, t), side(2, u))
>>> balanced(w)
False
>>> balanced(mobile(side(1, v), side(1, w)))
False
>>> balanced(mobile(side(1, w), side(1, v)))
False
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q balanced
Mutation
Question 4
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
>>> 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 ***"
Use OK to test your code:
python3 ok -q make_withdraw
Question 5
Suppose that our banking system requires the ability to make joint
accounts. Define a function make_joint
that takes three arguments.
- A password-protected
withdraw
function, - The password with which that
withdraw
function was defined, and - A new password that can also access the original account.
The make_joint
function returns a withdraw
function that provides
additional access to the original account using either the new or old
password. Both functions draw down the same balance. Incorrect
passwords provided to either function will be stored and cause the
functions to be locked after three wrong attempts.
Hint: The solution is short (less than 10 lines) and contains no string
literals! The key is to call withdraw
with the right password and amount,
then interpret the result. You may assume that all failed attempts to withdraw
will return some string (for incorrect passwords, locked accounts, or
insufficient funds), while successful withdrawals will return a number.
Use type(value) == str
to test if some value
is a string:
def make_joint(withdraw, old_password, new_password):
"""Return a password-protected withdraw function that has joint access to
the balance of withdraw.
>>> w = make_withdraw(100, 'hax0r')
>>> w(25, 'hax0r')
75
>>> make_joint(w, 'my', 'secret')
'Incorrect password'
>>> j = make_joint(w, 'hax0r', 'secret')
>>> w(25, 'secret')
'Incorrect password'
>>> j(25, 'secret')
50
>>> j(25, 'hax0r')
25
>>> j(100, 'secret')
'Insufficient funds'
>>> j2 = make_joint(j, 'secret', 'code')
>>> j2(5, 'code')
20
>>> j2(5, 'secret')
15
>>> j2(5, 'hax0r')
10
>>> j2(25, 'password')
'Incorrect password'
>>> j2(5, 'secret')
"Your account is locked. Attempts: ['my', 'secret', 'password']"
>>> j(5, 'secret')
"Your account is locked. Attempts: ['my', 'secret', 'password']"
>>> w(5, 'hax0r')
"Your account is locked. Attempts: ['my', 'secret', 'password']"
>>> make_joint(w, 'hax0r', 'hello')
"Your account is locked. Attempts: ['my', 'secret', 'password']"
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q make_joint
Objects
Question 6
Create a class called VendingMachine
that represents a vending
machine for some product. A VendingMachine
object returns strings
describing its interactions. See the doctest below for examples:
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(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.'
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q VendingMachine
Question 7
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.
Hint: Your implementation will need to use the *args
notation that
allows functions to take a flexible number of arguments.
Hint: Use getattr
and hasattr
to manipulate attributes using strings.
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.'
>>> really_fussy = MissManners(m)
>>> really_fussy.ask('deposit', 10)
'You must learn to say please first.'
>>> really_fussy.ask('please deposit', 10)
'Thanks for asking, but I know not how to deposit.'
>>> really_fussy.ask('please please deposit', 10)
'Thanks for asking, but I know not how to please deposit.'
>>> really_fussy.ask('please ask', 'please deposit', 10)
'Current balance: $10'
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q MissManners
Extra Question
Coming soon (probably)!