*Due by 11:59pm on Tuesday, 11/5*

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

**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.** Write a data-directed apply function that computes the area or
perimeter of either a square or a rectangle. 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.** Complete the implementation from lecture of sets represented as sorted
recursive lists. Both `adjoin_set2` and `union_set2` should take Θ(n) time,
where n is the size of the input set(s):

def empty(s): return len(s) == 0 def set_contains2(s, v): """Return true if set s contains value v as an element. >>> s = Rlist(1, Rlist(2, Rlist(3))) >>> set_contains2(s, 2) True >>> set_contains2(s, 5) False """ if empty(s) or s.first > v: return False elif s.first == v: return True else: return set_contains2(s.rest, v) def intersect_set2(set1, set2): """Return a set containing all elements common to set1 and set2. >>> s = Rlist(1, Rlist(2, Rlist(3))) >>> t = Rlist(2, Rlist(3, Rlist(4))) >>> intersect_set2(s, t) Rlist(2, Rlist(3)) """ if empty(set1) or empty(set2): return Rlist.empty else: e1, e2 = set1.first, set2.first if e1 == e2: return Rlist(e1, intersect_set2(set1.rest, set2.rest)) elif e1 < e2: return intersect_set2(set1.rest, set2) elif e2 < e1: return intersect_set2(set1, set2.rest) def adjoin_set2(s, v): """Return a set containing all elements of s and element v. Assume that s is an Rlist with elements sorted from least to greatest. >>> s = Rlist(1, Rlist(2, Rlist(3))) >>> adjoin_set2(s, 2.5) Rlist(1, Rlist(2, Rlist(2.5, Rlist(3)))) >>> adjoin_set2(s, 0.5) Rlist(0.5, Rlist(1, Rlist(2, Rlist(3)))) >>> adjoin_set2(s, 3) Rlist(1, Rlist(2, Rlist(3))) """ "*** YOUR CODE HERE ***" def union_set2(set1, set2): """Return a set containing all elements either in set1 or set2. Assume that set1 and set2 are both Rlists with elements sorted from least to greatest. >>> s = Rlist(1, Rlist(2, Rlist(3))) >>> t = Rlist(1, Rlist(3, Rlist(5))) >>> union_set2(s, t) Rlist(1, Rlist(2, Rlist(3, Rlist(5)))) >>> union_set2(s.rest, t) Rlist(1, Rlist(2, Rlist(3, Rlist(5)))) >>> union_set2(Rlist.empty, intersect_set2(s.rest, t)) Rlist(3) """ "*** YOUR CODE HERE ***"

**Q4.** Complete the implementation from lecture of sets represented as binary
search trees. The entry of a binary search tree is larger than all entries in
its left branch and smaller than all entries in its right branch. Moreover,
non-empty branches of a binary search tree must also be binary search trees.
Intersection and union are performed by coercing a tree set to and from an
ordered recursive list:

class Tree(object): """A tree with internal values.""" def __init__(self, entry, left=None, right=None): self.entry = entry self.left = left self.right = right def __repr__(self): args = repr(self.entry) if self.left or self.right: args += ', {0}, {1}'.format(repr(self.left), repr(self.right)) return 'Tree({0})'.format(args) def big_tree(left, right): """Return a tree set of unique elements between left and right. This function creates binary search trees for testing. >>> big_tree(0, 12) Tree(6, Tree(2, Tree(0), Tree(4)), Tree(10, Tree(8), Tree(12))) """ if left > right: return None split = left + (right - left)//2 return Tree(split, big_tree(left, split-2), big_tree(split+2, right)) def set_contains3(s, v): """Return true if set s contains value v as an element. >>> t = Tree(2, Tree(1), Tree(3)) >>> set_contains3(t, 3) True >>> set_contains3(t, 0) False >>> set_contains3(big_tree(20, 60), 34) True """ if s is None: return False elif s.entry == v: return True elif s.entry < v: return set_contains3(s.right, v) elif s.entry > v: return set_contains3(s.left, v) def adjoin_set3(s, v): """Return a set containing all elements of s and element v. >>> b = big_tree(0, 9) >>> b Tree(4, Tree(1), Tree(7, None, Tree(9))) >>> adjoin_set3(b, 5) Tree(4, Tree(1), Tree(7, Tree(5), Tree(9))) """ if s is None: return Tree(v) elif s.entry == v: return s elif s.entry < v: return Tree(s.entry, s.left, adjoin_set3(s.right, v)) elif s.entry > v: return Tree(s.entry, adjoin_set3(s.left, v), s.right) def intersect_set3(set1, set2): """Return a set containing all elements common to set1 and set2. >>> s, t = big_tree(0, 12), big_tree(6, 18) >>> intersect_set3(s, t) Tree(8, Tree(6), Tree(10, None, Tree(12))) """ s1, s2 = map(tree_to_ordered_sequence, (set1, set2)) return ordered_sequence_to_tree(intersect_set2(s1, s2)) def union_set3(set1, set2): """Return a set containing all elements either in set1 or set2. >>> s, t = big_tree(6, 12), big_tree(10, 16) >>> union_set3(s, t) Tree(10, Tree(6, None, Tree(9)), Tree(13, Tree(11), Tree(15))) """ s1, s2 = map(tree_to_ordered_sequence, (set1, set2)) return ordered_sequence_to_tree(union_set2(s1, s2))

First, implement `tree_to_ordered_sequence`, which coerces a set represented
as a `Tree` into a set represented as an ordered `Rlist`. If you can,
implement this function so that it executes in Θ(n) time, where n is the
number of elements in the tree:

def tree_to_ordered_sequence(s): """Return an ordered sequence containing the elements of tree set s. Assume that s is a well-formed binary search tree. >>> b = big_tree(0, 9) >>> tree_to_ordered_sequence(b) Rlist(1, Rlist(4, Rlist(7, Rlist(9)))) """ "*** YOUR CODE HERE ***"

Second, in order to complete the coercion from an ordered sequence set to a tree
set, implement `partial_tree`. 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 branch out of the first left_size elements of s; Then, the next element is
used as the entry of the returned tree. Finally, the second recursive call
builds the right branch out of the next right_size elements. In total,
(left_size + 1 + right_size) = n, where 1 is for the entry:

def partial_tree(s, n): """Return a balanced tree of the first n elements of Rlist s, along with the rest 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: Tree(1, Tree(2, Tree(3)), None) # branch difference 2 - 0 = 2 Tree(1, Tree(2, Tree(3), None), Tree(4, Tree(5, Tree(6), None), None)) # Unbalanced right branch >>> s = Rlist(1, Rlist(2, Rlist(3, Rlist(4, Rlist(5))))) >>> partial_tree(s, 3) (Tree(2, Tree(1), Tree(3)), Rlist(4, Rlist(5))) >>> t = Rlist(-2, Rlist(-1, Rlist(0, s))) >>> partial_tree(t, 7)[0] Tree(1, Tree(-1, Tree(-2), Tree(0)), Tree(3, Tree(2), Tree(4))) >>> partial_tree(t, 7)[1] Rlist(5) """ if n == 0: return None, 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_tree above is not complete. >>> ordered_sequence_to_tree(Rlist(1, Rlist(2, Rlist(3)))) Tree(2, Tree(1), Tree(3)) >>> b = big_tree(0, 20) >>> elements = tree_to_ordered_sequence(b) >>> elements Rlist(1, Rlist(4, Rlist(7, Rlist(10, Rlist(13, Rlist(16, Rlist(19))))))) >>> ordered_sequence_to_tree(elements) Tree(10, Tree(4, Tree(1), Tree(7)), Tree(16, Tree(13), Tree(19))) """ return partial_tree(s, len(s))[0]

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

**Q6.** (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 ***" 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: return self.rest[index-1] def __len__(self): return 1 + len(self.rest) def __repr__(self): return rlist_expression(self) def rlist_expression(s): """Return a string that would evaluate to s.""" if s.rest is Rlist.empty: rest = '' else: rest = ', ' + rlist_expression(s.rest) return 'Rlist({0}{1})'.format(s.first, rest)