61A Homework 7

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:
  1. Write a function has_cycle that returns True if and only if its argument, an Rlist instance, contains a cycle.
  2. 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)