*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

- This question has two parts:
- Write a function has_cycle that returns True if and only if its argument, an Rlist instance, contains a cycle.
- Write a function has_cycle_constant that has the same behavior as has_cycle but requires only a constant amount of space.

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 ***"