Homework 5: OOP & Mutable Functions
Due by 11:59pm on Tuesday, 7/24
Instructions
Download hw05.zip.
- Questions 1-7 are required and can be found in
hw05.py
- Question 8 is required and can be found in
hw05.scm
. - Question 9 is optional and can be found in
hw05.py
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
Object oriented programming
Q1: Vending Machine
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.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]'
Use Ok to test your code:
python3 ok -q VendingMachine
Q2: Miss Manners
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.
We can also compose multiple instances of MissManners
objects upon
each other (see double_fussy
in doctests). A multilevel MissManners
object
must be politely requested to ask its own MissManners
object. This continues
until we reach the bottom level MissManners
object.
Hint: Use
getattr
(Python docs) andhasattr
(Python docs) to access methods using strings. You may want to search online for some examples of their usage.Hint: Your implementation will need to use the
*args
notation that allows functions to take a flexible number of arguments. If you need a refresher, take a look at your implementation ofmake_averaged
in the Hog project.
class MissManners:
"""A container class that only forwards 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.'
>>> double_fussy = MissManners(m) # Composed MissManners objects
>>> double_fussy.ask('deposit', 10)
'You must learn to say please first.'
>>> double_fussy.ask('please deposit', 10)
'Thanks for asking, but I know not how to deposit.'
>>> double_fussy.ask('please please deposit', 10)
'Thanks for asking, but I know not how to please deposit.'
>>> double_fussy.ask('please ask', 'please deposit', 10)
'Current balance: $10'
"""
def __init__(self, obj):
self.obj = obj
def ask(self, message, *args):
magic_word = 'please '
if not message.startswith(magic_word):
return 'You must learn to say please first.'
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q MissManners
Tree objects
Q3: Long Paths
Implement long_paths
, which returns a list of all paths in a tree with
length at least n
. A path in a tree is a list of node labels that starts with
the root and ends at a leaf. Each subsequent element must be from a label of a
branch of the previous value's node. The length of a path is the number of
edges in the path (i.e. one less than the number of nodes in the path). Paths
are ordered in the output list from left to right in the tree. See the doctests
for some examples.
def long_paths(t, n):
"""Return a list of all paths in t with length at least n.
>>> long_paths(Tree(1), 0)
[[1]]
>>> long_paths(Tree(1), 1)
[]
>>> t = Tree(3, [Tree(4), Tree(4), Tree(5)])
>>> left = Tree(1, [Tree(2), t])
>>> mid = Tree(6, [Tree(7, [Tree(8)]), Tree(9)])
>>> right = Tree(11, [Tree(12, [Tree(13, [Tree(14)])])])
>>> whole = Tree(0, [left, Tree(13), mid, right])
>>> print(whole)
0
1
2
3
4
4
5
13
6
7
8
9
11
12
13
14
>>> for path in long_paths(whole, 2):
... print(path)
...
[0, 1, 2]
[0, 1, 3, 4]
[0, 1, 3, 4]
[0, 1, 3, 5]
[0, 6, 7, 8]
[0, 6, 9]
[0, 11, 12, 13, 14]
>>> for path in long_paths(whole, 3):
... print(path)
...
[0, 1, 3, 4]
[0, 1, 3, 4]
[0, 1, 3, 5]
[0, 6, 7, 8]
[0, 11, 12, 13, 14]
>>> long_paths(whole, 4)
[[0, 11, 12, 13, 14]]
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q long_paths
Q4: Add Leaves
Implement add_d_leaves
, a function that takes in a Tree
instance t
and
mutates it so that at each depth d
in the tree, d
leaves with labels v
are added to each node at that depth. For example, we want to add 1 leaf with
v
in it to each node at depth 1, 2 leaves to each node at depth 2, and so on.
Recall that the depth of a node is the number of edges from that node to the root, so the depth of the root is 0. The leaves should be added to the end of the list of branches.
def add_d_leaves(t, v):
"""Add d leaves containing v to each node at every depth d.
>>> t1 = Tree(1, [Tree(3)])
>>> add_d_leaves(t1, 4)
>>> t1
Tree(1, [Tree(3, [Tree(4)])])
>>> t2 = Tree(2, [Tree(5), Tree(6)])
>>> t3 = Tree(3, [t1, Tree(0), t2])
>>> add_d_leaves(t3, 10)
>>> print(t3)
3
1
3
4
10
10
10
10
10
10
0
10
2
5
10
10
6
10
10
10
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q add_d_leaves
Mutable functions in Python
Q5: Counter
Define a function make_counter
that returns a counter
function, which takes
a string and returns the number of times that the function has been called on
that string.
def make_counter():
"""Return a counter function.
>>> c = make_counter()
>>> c('a')
1
>>> c('a')
2
>>> c('b')
1
>>> c('a')
3
>>> c2 = make_counter()
>>> c2('b')
1
>>> c2('b')
2
>>> c('b') + c2('b')
5
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q make_counter
Q6: 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 ***"
Use Ok to test your code:
python3 ok -q make_withdraw
Q7: Joint Account
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 from 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
Mutable functions in Scheme
Q8: Next Fibonacci
Write a procedure make-fib
that returns a procedure that returns the next
Fibonacci number each time it is called. Recall that the Fibonacci sequence
begins with 0 and then 1, after which each element is the sum of the preceding
two.
(define (make-fib)
(define curr 0) (define next 1)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q make_fib -u
python3 ok -q make_fib
Extra questions
Q9: Next Fibonacci Object
Implement the next
method of the Fib
class. For this class, the value
attribute is a Fibonacci number. The next
method returns a Fib
instance
whose value
is the next Fibonacci number. The next
method should take only
constant time.
Note that in the doctests, nothing is being printed out. Rather, each call to
.next()
returns a Fib
instance, which is represented in the interpreter as
the value of that instance (see the __repr__
method).
Hint: Keep track of the previous number by setting a new instance attribute inside
next
.
class Fib():
"""A Fibonacci number.
>>> start = Fib()
>>> start
0
>>> start.next()
1
>>> start.next().next()
1
>>> start.next().next().next()
2
>>> start.next().next().next().next()
3
>>> start.next().next().next().next().next()
5
>>> start.next().next().next().next().next().next()
8
>>> start.next().next().next().next().next().next() # Ensure start isn't changed
8
"""
def __init__(self, value=0):
self.value = value
def next(self):
"*** YOUR CODE HERE ***"
def __repr__(self):
return str(self.value)
Use Ok to test your code:
python3 ok -q Fib