Due by 11:59pm on Tuesday, 4/8
Submission. See the online submission instructions. We have provided a hw7.py starter file for the questions below.
Readings. Section 2.7 and 2.8 of Composing Programs.
Introduction. This assignment is officially due in three weeks, because of the upcoming test and spring break. However, you may find some of the material useful in preparing for the test, so we suggest that you complete a week ahead of time. We will run the autograder accordingly.
Q1. Write a class Amount that represents a collection of nickels and pennies. Include a property method 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. You do not need to support direct assignment to value. (You are welcome to add that feature as well; see the relevant Python Property docs).
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:
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
4
>>> a.pennies
2
>>> a.value
22
"""
"*** YOUR CODE HERE ***"
Q2. Section 2.8.4 of the online textbook and slide 20 of Lecture 17 describe one way to get data-directed programming, in which the data "decide" how any particular method is to be handled.
Write a data-directed apply function that computes the area or perimeter of either a square or a rectangle. As suggested in the readings, use a dictionary to store the implementations of each function for each type:
class Square(object):
def __init__(self, side):
self.side = side
class Rect(object):
def __init__(self, width, height):
self.width = width
self.height = height
def apply(operator_name, shape):
"""Apply operator to shape.
>>> apply('area', Square(10))
100
>>> apply('perimeter', Square(5))
20
>>> apply('area', Rect(5, 10))
50
>>> apply('perimeter', Rect(2, 4))
12
"""
"*** YOUR CODE HERE ***"
Q3. In lecture, we talked about using binary search trees to implement sets of values, but one could also use various kinds of sequence to do the job, such as the rlist type from earlier in the semester, here recast as a class:
class Rlist:
"""A recursive list consisting of a first element and the rest.
>>> s = Rlist(1, Rlist(2, Rlist(3)))
>>> s.rest
Rlist(2, Rlist(3))
>>> len(s)
3
>>> s[1]
2
"""
class EmptyList:
def __len__(self):
return 0
def __repr__(self):
return "Rlist.empty"
empty = EmptyList()
def __init__(self, first, rest=empty):
assert type(rest) is Rlist or rest is Rlist.empty
self.first = first
self.rest = rest
def __getitem__(self, index):
if index == 0:
return self.first
else:
if self.rest is Rlist.empty:
raise IndexError("Rlist index out of bounds")
return self.rest[index-1]
def __len__(self):
return 1 + len(self.rest)
def __repr__(self):
"""Return a string that would evaluate to s."""
if self.rest is Rlist.empty:
rest = ''
else:
rest = ', ' + repr(self.rest)
return 'Rlist({0}{1})'.format(self.first, rest)
Complete the following partial implementation of sets represented as sorted recursive lists by filling in definitions for rlist_adjoin, drlist_adjoin, rlist_intersect and rlist_union. All of these functions should take Θ(n) time, where n is the size of the input list(s):
class rlist_set:
"""A set of arbitrary items that have an ordering (i.e., that
define <=, <, and other relational operations between them)."""
# Representation: rlist_sets are represented by Rlists of items
# maintained in sorted order.
def __init__(self, *initial_items):
"""A set that initially contains the values in
INITIAL_ITEMS, which can be any iterable."""
self._s = Rlist.empty
for v in initial_items:
self.add(v)
@staticmethod
def _make_set(r):
"""An internal method for creating rlist_sets out of rlists."""
result = rlist_set()
result._s = r
return result
def as_rlist(self):
"""An Rlist of my values in sorted order. This Rlist must not be modified."""
return self._s
def empty(self):
return self._s is Rlist.empty
def __contains__(self, v):
"""True iff I currently contain the value V.
>>> s = rlist_set(3, 8, 7, 1)
>>> s.__contains__(7)
True
>>> 7 in s # __contains__ defines 'in'
True
>>> 9 in s
False"""
if self.empty() or self._s.first > v:
return False
elif self._s.first == v:
return True
else:
return v in self._s.rest
def __repr__(self):
result = "{"
s = self._s
while s is not Rlist.empty:
if result != "{":
result += ", "
result += repr(s.first)
s = s.rest
return result + "}"
def intersection(self, other_set):
"""Return a set containing all elements common to rlist_sets
SELF and OTHER_SET.
>>> s = rlist_set(1, 2, 3)
>>> t = rlist_set(2, 3, 4)
>>> s.intersection(t)
{2, 3}
"""
return rlist_set._make_set(rlist_intersect(self._s, other_set._s))
def adjoin(self, v):
"""Return a set containing all elements of s and element v.
>>> s = rlist_set(1, 2, 3)
>>> s.adjoin(2.5)
{1, 2, 2.5, 3}
>>> s.adjoin(0.5)
{0.5, 1, 2, 3}
>>> s.adjoin(3)
{1, 2, 3}
"""
return rlist_set._make_set(rlist_adjoin(self._s, v))
def add(self, v):
"""Destructively changes me to the result of adjoining V, returning the modified
set."""
self._s = drlist_adjoin(self._s, v)
def union(self, other_set):
"""Return a set containing all elements either in myself or OTHER_SET.
>>> s0 = rlist_set(2, 3)
>>> s = s0.adjoin(1)
>>> t0 = rlist_set(3, 5)
>>> t = t0.adjoin(1)
>>> s.union(t)
{1, 2, 3, 5}
>>> s0.union(t)
{1, 2, 3, 5}
>>> rlist_set().union(s0.intersection(t))
{3}
"""
return rlist_set._make_set(rlist_union(self._s, other_set._s))
def rlist_adjoin(s, v):
"""Assuming S is an Rlist in sorted order, a new Rlist that contains all the original
values, plus V (if not already present) in sorted order."""
"*** YOUR CODE HERE ***"
def drlist_adjoin(s, v):
"""Destructively add V to the appropriate place in sorted Rlist S, if it is not already
present, returning the modified Rlist."""
"*** YOUR CODE HERE ***"
def rlist_intersect(s1, s2):
"""Assuming S1 and S2 are two Rlists in sorted order, return a new Rlist in
sorted order containing exactly the values both have in common, in sorted order."""
"*** YOUR CODE HERE ***"
def rlist_union(s1, s2):
"""Assuming S1 and S2 are two Rlists in sorted order, return a new Rlist in
sorted order containing the union of the values in both, in sorted order."""
"*** YOUR CODE HERE ***"
Q4. Complete the following, somewhat more direct version of the BinTree type from lecture by filling in the inorder_tree_iter class at the end:
class BinTree:
"""A binary tree."""
def __init__(self, label, left=None, right=None):
"""The binary tree node with given LABEL, whose left
and right children are BinTrees LEFT and RIGHT, which
default to the empty tree."""
self._label = label
self._left = left or BinTree.empty
self._right = right or BinTree.empty
@property
def is_empty(self):
"""This tree contains no labels or children."""
return self is BinTree.empty
@property
def label(self):
return self._label
@property
def left(self):
return self._left
@property
def right(self):
return self._right
def set_left(self, newval):
"""Assuming NEWVAL is a BinTree, sets SELF.left to NEWVAL."""
assert isinstance(newval, BinTree)
self._left = newval
def set_right(self, newval):
"""Assuming NEWVAL is a BinTree, sets SELF.right to NEWVAL."""
assert isinstance(newval, BinTree)
self._right = newval
def inorder_values(self):
"""An iterator over my labels in inorder (left tree labels, recursively,
then my label, then right tree labels).
>>> T = BinTree(10, BinTree(5, BinTree(2), BinTree(6)), BinTree(15))
>>> for v in T.inorder_values():
... print(v, end=" ")
2 5 6 10 15 """
return inorder_tree_iter(self)
# A placeholder, initialized right after the class.
empty = None
def __repr__(self):
if self.is_empty:
return "BinTree.empty"
else:
args = repr(self.label)
if not self.left.is_empty or not self.right.is_empty:
args += ', {0}, {1}'.format(repr(self.left), repr(self.right))
return 'BinTree({0})'.format(args)
class EmptyBinTree(BinTree):
"""Represents the empty tree. There should only be one of these."""
def __init__(self):
pass
@property
def is_empty(self): return True
@property
def label(self): raise NotImplemented
@property
def left(self): raise NotImplemented
@property
def right(self): raise NotImplemented
def set_left(self, newval): raise NotImplemented
def set_right(self, newval): raise NotImplemented
# Set the empty BinTree (we could only do this after defining EmptyBinTree
BinTree.empty = EmptyBinTree()
class inorder_tree_iter:
def __init__(self, the_tree):
self._work_queue = [ the_tree ]
def __next__(self):
while len(self._work_queue) > 0:
subtree_or_label = self._work_queue.pop()
"*** YOUR CODE HERE ***"
raise StopIteration
def __iter__(self): return self
Notes: (1) As is common practice, we add and remove items from the end of _work_queue rather than the beginning. (2) Since BinTrees can also be EmptyBinTrees, use the built-in isinstance function to test whether something is a BinTree. See, for example, the set_left method.
Q5. Here is an implementation of sets using BinTree from the preceding problem:
class bintree_set:
"""A set of arbitrary items that have an ordering (i.e., that
define <=, <, and other relational operations between them)."""
# Representation: bintree_sets are represented by BinTrees used as binary search trees.
def __init__(self, *initial_items):
"""A set that initially contains the values in
INITIAL_ITEMS, which can be any iterable."""
self._s = BinTree.empty
for v in initial_items:
self.add(v)
def __repr__(self):
return "{" + ", ".join(map(repr, self._s.inorder_values())) + "}"
def __contains__(self, v):
"""True iff I currently contain the value V.
>>> s = bintree_set(3, 8, 7, 1)
>>> s.__contains__(7)
True
>>> 7 in s # __contains__ defines 'in'
True
>>> 9 in s
False"""
s = self._s
while not s is BinTree.empty and s._label != v:
if v < s._label:
s = s.left
else:
s = s.right
return not s.is_empty
@staticmethod
def _make_set(b):
"""An internal method for creating a bintree_set out of bintree B."""
result = bintree_set()
result._s = b
return result
def adjoin(self, v):
"""Return a set containing all elements of s and element v."""
def tree_add(T, x):
if T.is_empty:
return BinTree(x)
elif x == T.label:
return T
elif x < T.label:
return BinTree(T.label, tree_add(T.left, x), T.right)
else:
return BinTree(T.label, T.left, tree_add(T.right, x))
return bintree_set._make_set(tree_add(self._s, v))
def add(self, v):
"""Destructively adjoin V to my values, returning modified set."""
def dtree_add(T, x):
if T.is_empty:
return BinTree(x)
elif x == T.label:
return T
elif x < T.label:
T.set_left(dtree_add(T.left, x))
return T
else:
T.set_right(dtree_add(T.right, x))
return T
self._s = dtree_add(self._s, v)
return self
def intersection(self, other_set):
"""Return a set containing all elements common to bintree_sets
SELF and OTHER_SET.
>>> s = bintree_set(1, 2, 3)
>>> t = bintree_set(2, 3, 4)
>>> s.intersection(t)
{2, 3}
"""
list1 = rlist_set(*self._s.inorder_values()).as_rlist()
list2 = rlist_set(*other_set._s.inorder_values()).as_rlist()
return bintree_set._make_set(ordered_sequence_to_tree(rlist_intersect(list1, list2)))
def union(self, other_set):
"""Return a set containing all elements either in myself or OTHER_SET.
>>> s0 = bintree_set(2, 3)
>>> s = s0.adjoin(1)
>>> t0 = bintree_set(3, 5)
>>> t = t0.adjoin(1)
>>> s.union(t)
{1, 2, 3, 5}
>>> s0.union(t)
{1, 2, 3, 5}
>>> bintree_set().union(s0.intersection(t))
{3}"""
list1 = rlist_set(*self._s.inorder_values()).as_rlist()
list2 = rlist_set(*other_set._s.inorder_values()).as_rlist()
return bintree_set._make_set(ordered_sequence_to_tree(rlist_union(list1, list2)))
Unlike the simple intersection done in lecture, we'd like the results of union and intersection to be "bushy". In order to complete the coercion from an ordered sequence set to a tree set, implement partial_sequence_to_tree below. If you can, implement the function to run in Θ(n) time in the length of the input list.
Hint: This function requires two recursive calls. The first call builds a left child out of the first left_size elements of s; Then, the next element is used as the label of the returned tree. Finally, the second recursive call builds the right child out of the next right_size elements. In total, (left_size + 1 + right_size) = n, where 1 is for the label:
def partial_sequence_to_tree(s, n):
"""Return a tuple (b, r), where b is a tree of the first N elements of Rlist S, and
r is the Rlist of the remaining elements of S. A tree is balanced if
(a) the number of entries in its left branch differs from the number
of entries in its right branch by at most 1, and
(b) its non-empty branches are also balanced trees.
Examples of balanced trees:
Tree(1) # branch difference 0 - 0 = 0
Tree(1, Tree(2), None) # branch difference 1 - 0 = 1
Tree(1, None, Tree(2)) # branch difference 0 - 1 = -1
Tree(1, Tree(2), Tree(3)) # branch difference 1 - 1 = 0
Examples of unbalanced trees:
BinTree(1, BinTree(2, BinTree(3)), None) # branch difference 2 - 0 = 2
BinTree(1, BinTree(2, BinTree(3), None),
BinTree(4, BinTree(5, BinTree(6), None), None)) # Unbalanced right branch
>>> s = Rlist(1, Rlist(2, Rlist(3, Rlist(4, Rlist(5)))))
>>> partial_sequence_to_tree(s, 3)
(BinTree(2, BinTree(1), BinTree(3)), Rlist(4, Rlist(5)))
>>> t = Rlist(-2, Rlist(-1, Rlist(0, s)))
>>> partial_sequence_to_tree(t, 7)[0]
BinTree(1, BinTree(-1, BinTree(-2), BinTree(0)), BinTree(3, BinTree(2), BinTree(4)))
>>> partial_sequence_to_tree(t, 7)[1]
Rlist(5)
"""
if n == 0:
return BinTree.empty, s
left_size = (n-1)//2
right_size = n - left_size - 1
"*** YOUR CODE HERE ***"
def ordered_sequence_to_tree(s):
"""Return a balanced tree containing the elements of ordered Rlist s.
Note: this implementation is complete, but the definition of partial_sequence_to_tree
above is not complete.
>>> ordered_sequence_to_tree(Rlist(1, Rlist(2, Rlist(3))))
BinTree(2, BinTree(1), BinTree(3))
>>> b = rlist_set(*range(1, 20, 3))
>>> elements = b.as_rlist()
>>> elements
Rlist(1, Rlist(4, Rlist(7, Rlist(10, Rlist(13, Rlist(16, Rlist(19)))))))
>>> ordered_sequence_to_tree(elements)
BinTree(10, BinTree(4, BinTree(1), BinTree(7)), BinTree(16, BinTree(13), BinTree(19)))
"""
return partial_sequence_to_tree(s, len(s))[0]
Q6. Mario needs to jump over a sequence of Piranha plants, represented as a string of spaces (no plant) and P's (plant!). He only moves forward, and he can either step (move forward one space) or jump (move forward two spaces) from each position. How many different ways can Mario traverse a level without stepping or jumping into a Piranha plant? Assume that every level begins with a space (where Mario starts) and ends with a space (where Mario must end up):
def mario_number(level):
"""Return the number of ways that Mario can perform a sequence of steps
or jumps to reach the end of the level without ever landing in a Piranha
plant. Assume that every level begins and ends with a space.
>>> mario_number(' P P ') # jump, jump
1
>>> mario_number(' P P ') # jump, jump, step
1
>>> mario_number(' P P ') # step, jump, jump
1
>>> mario_number(' P P ') # step, step, jump, jump or jump, jump, jump
2
>>> mario_number(' P PP ') # Mario cannot jump two plants
0
>>> mario_number(' ') # step, jump ; jump, step ; step, step, step
3
>>> mario_number(' P ')
9
>>> mario_number(' P P P P P P P P ')
180
"""
"*** YOUR CODE HERE ***"
Q7. (Extra for experts) The Rlist class can represent lists with cycles. That is, a list may contain itself as a sublist.
>>> s = Rlist(1, Rlist(2, Rlist(3))) >>> s.rest.rest.rest = s >>> s[20] 3
Hint: The solution to B is short (less than 20 lines of code), but requires a clever idea. Try to discover the solution yourself before asking around:
def has_cycle(s):
"""Return whether Rlist s contains a cycle.
>>> s = Rlist(1, Rlist(2, Rlist(3)))
>>> s.rest.rest.rest = s
>>> has_cycle(s)
True
>>> t = Rlist(1, Rlist(2, Rlist(3)))
>>> has_cycle(t)
False
"""
"*** YOUR CODE HERE ***"
def has_cycle_constant(s):
"""Return whether Rlist s contains a cycle.
>>> s = Rlist(1, Rlist(2, Rlist(3)))
>>> s.rest.rest.rest = s
>>> has_cycle_constant(s)
True
>>> t = Rlist(1, Rlist(2, Rlist(3)))
>>> has_cycle_constant(t)
False
"""
"*** YOUR CODE HERE ***"