Homework 4
Due by 11:59pm on Monday, 3/6
Instructions
Download hw04.zip.
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:
Vitamins
Question 1: 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
Question 2: 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 ***"
Use OK to test your code:
python3 ok -q make_fib
Required questions
You may choose to work with a partner on homework questions, but you must submit your own solution. That is, try to share ideas rather than code.
Recursion
Question 3: Towers of Hanoi
A classic puzzle called the Towers of Hanoi is a game that consists of three
rods, and a number of disks of different sizes which can slide onto any rod.
The puzzle starts with n
disks in a neat stack in ascending order of size on
a start
rod, the smallest at the top, forming a conical shape.
The objective of the puzzle is to move the entire stack to an end
rod,
obeying the following rules:
- Only one disk may be moved at a time.
- Each move consists of taking the top (smallest) disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
- No disk may be placed on top of a smaller disk.
Complete the definition of move_stack
, which prints out the steps required to
move n
disks from the start
rod to the end
rod without violating the
rules.
def print_move(origin, destination):
"""Print instructions to move a disk."""
print("Move the top disk from rod", origin, "to rod", destination)
def move_stack(n, start, end):
"""Print the moves required to move n disks on the start pole to the end
pole without violating the rules of Towers of Hanoi.
n -- number of disks
start -- a pole position, either 1, 2, or 3
end -- a pole position, either 1, 2, or 3
There are exactly three poles, and start and end must be different. Assume
that the start pole has at least n disks of increasing size, and the end
pole is either empty or has a top disk larger than the top n start disks.
>>> move_stack(1, 1, 3)
Move the top disk from rod 1 to rod 3
>>> move_stack(2, 1, 3)
Move the top disk from rod 1 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 3
>>> move_stack(3, 1, 3)
Move the top disk from rod 1 to rod 3
Move the top disk from rod 1 to rod 2
Move the top disk from rod 3 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 1
Move the top disk from rod 2 to rod 3
Move the top disk from rod 1 to rod 3
"""
assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, "Bad start/end"
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q move_stack
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 4: Weights
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 label(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 5: Balanced
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
Question 6: Totals
Implement the with_totals
function, which takes a mobile
and returns a tree
representation of that same mobile in which the root label of each mobile tree
is the total weight of the mobile it represents (instead of None
).
Note: This function needs to assume that a mobile is represented as a tree.
def with_totals(m):
"""Return a mobile with total weights stored as the label of each mobile.
>>> t, _, v = examples()
>>> label(with_totals(t))
3
>>> print(label(t)) # t should not change
None
>>> label(with_totals(v))
9
>>> [label(end(s)) for s in sides(with_totals(v))]
[3, 6]
>>> [label(end(s)) for s in sides(v)] # v should not change
[None, None]
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q with_totals
Question 7: Intervals
Acknowledgements. This interval arithmetic example is adapted from a classic problem from Structure and Interpretation of Computer Programs, Section 2.1.4.
Introduction. Alyssa P. Hacker is designing a system to help people solve engineering problems. One feature she wants to provide in her system is the ability to manipulate inexact quantities (such as measured parameters of physical devices) with known precision, so that when computations are done with such approximate quantities the results will be numbers of known precision.
Alyssa's idea is to implement interval arithmetic as a set of arithmetic operations for combining "intervals" (objects that represent the range of possible values of an inexact quantity). The result of adding, subracting, multiplying, or dividing two intervals is itself an interval, representing the range of possible results when the operation is applied to one value selected from the first of the two interval operands and one value selected from the second.
Alyssa postulates the existence of an abstract object called an "interval" that has two endpoints: a lower bound and an upper bound. She intends to allow clients to construct intervals from their endpoints, print them, and perform arithmetic on them, as indicated in the following use cases:
class interval:
"""A range of floating-point values.
>>> a = interval(1, 4)
>>> a
interval(1, 4)
>>> print(a)
(1, 4)
>>> a.low()
1
>>> a.high()
4
>>> a.width()
3
>>> b = interval(2, -2) # Order doesn't matter
>>> print(b, b.low(), b.high())
(-2, 2) -2 2
>>> a + b
interval(-1, 6)
>>> a - b
interval(-1, 6)
>>> a * b
interval(-8, 8)
>>> b / a
interval(-2.0, 2.0)
>>> a / b
ValueError
>>> -a
interval(-4, -1)
>>> c = interval(2, 8)
>>> c + c
interval(4, 16)
>>> c - c
interval(-6, 6)
>>> c / c
interval(0.25, 4.0)
"""
# In all methods below, use the following method to create new intervals.
# For example, if a method must return interval(x, y), have it
# return self.makeinterval(x, y) instead.
def make_interval(self, low, high):
"""Returns an interval of the same type as SELF with bounds LOW
and HIGH. Thus, if SELF is an interval, returns interval(LOW, HIGH)."""
return interval(low, high)
"*** YOUR CODE HERE ***"
Implement an interval
class that has this behavior.
Use OK to test your code:
python3 ok -q interval
Question 8: Centered Interval
After debugging her program, Alyssa shows it to a potential user, who
complains that her program solves the wrong problem. He wants a program
that can deal with numbers represented as a center value and an
additive tolerance; for example, he wants to work with intervals such
as 3.5 +/- 0.15
rather than 3.35
to 3.65
. Alyssa returns to her
desk and fixes this problem by supplying a second interval class called
centered_interval
that inherits from interval
, has a different
constructor, different string representations, and two extra selectors:
class centered_interval(interval):
def __init__(self, c, tol = None):
"""Initialize SELF to C +- TOL. TOL is None, then C is assumed to be
an interval, and SELF will be set to have the same bounds.
>>> a = centered_interval(1, 2)
>>> a.low()
-1
>>> a.high()
3
>>> a.width()
4
>>> b = centered_interval(3, 1)
>>> a + b
centered_interval(4.0, 3.0)
>>> a * b
centered_interval(4.0, 8.0)
>>> -a
centered_interval(-1.0, 2.0)
"""
"*** YOUR CODE HERE ***"
def make_interval(self, low, high):
"""Returns a centered interval whose bounds are LOW and HIGH."""
"*** YOUR CODE HERE ***"
def center(self):
"""The center of SELF.
>>> centered_interval(5, 1).center()
5.0
>>> centered_interval(interval(4, 6)).center()
5.0
"""
"*** YOUR CODE HERE ***"
def tolerance(self):
"""The tolerance of SELF.
>>> centered_interval(5, 1).tolerance()
1.0
>>> centered_interval(interval(4, 6)).tolerance()
1.0
"""
"*** YOUR CODE HERE ***"
def __str__(self):
"""A string representation of SELF as center +/- tolerance.
>>> print(centered_interval(5, 1))
5.0 +/- 1.0
>>> print(centered_interval(interval(4, 6)))
5.0 +/- 1.0
"""
"*** YOUR CODE HERE ***"
def __repr__(self):
"""A string represention of a Python expression that will produce SELF.
>>> centered_interval(5, 1)
centered_interval(5.0, 1.0)
"""
"*** YOUR CODE HERE ***"
She does not override any of the __...__
methods of interval
other than __str__
,
__repr__
, and __init__
, so there is a slight problem, as these methods
were defined to construct intervals
rather than
centered_intervals
. You'll have to figure out how to use the method
make_interval
so that this all works properly.
Use OK to test your code:
python3 ok -q centered_interval.__init__
python3 ok -q centered_interval.center
python3 ok -q centered_interval.tolerance
python3 ok -q centered_interval.__str__
python3 ok -q centered_interval.__repr__
Extra questions
Extra questions are not worth extra credit and are entirely optional.
Question 9: Anonymous factorial
The recursive factorial function can be written as a single expression by using a conditional expression.
>>> fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1)))
>>> fact(5)
120
However, this implementation relies on the fact (no pun intended) that
fact
has a name, to which we refer in the body of fact
. To write a
recursive function, we have always given it a name using a def
or
assignment statement so that we can refer to the function within its
own body. In this question, your job is to define fact recursively
without giving it a name!
Write an expression that computes n
factorial using only call
expressions, conditional expressions, and lambda expressions (no
assignment or def statements). Note in particular that you are not
allowed to use make_anonymous_factorial
in your return expression.
The sub
and mul
functions from the operator
module are the only
built-in functions required to solve this problem:
from operator import sub, mul
def make_anonymous_factorial():
"""Return the value of an expression that computes factorial.
>>> make_anonymous_factorial()(5)
120
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'make_anonymous_factorial', ['Assign', 'AugAssign', 'FunctionDef', 'Recursion'])
True
"""
return 'YOUR_EXPRESSION_HERE'
Use OK to test your code:
python3 ok -q make_anonymous_factorial