61A Homework 12

Due by 5pm on Friday, 11/30

Submission. See the online submission instructions. We have provided a starter file for the questions below.

Readings. Sections 4.2, 4.3, and 4.4 of the online lecture notes.

Q1. (Objects and recursion review) A mobile is a type of hanging sculpture. A simple binary mobile consists of two branches, left and right. Each branch is a rod of a certain length, from which hangs either a weight or another mobile.

Improve the classes for Branch, Weight, and Mobile below in the following ways:

When you are finished, all doctests below should pass:

class Mobile(object):
    """A simple binary mobile that has branches of weights or other mobiles.

    >>> Mobile(1, 2)
    Traceback (most recent call last):
        ...
    TypeError: 1 is not a Branch
    >>> m = Mobile(Branch(1, Weight(2)), Branch(2, Weight(1)))
    >>> m.weight
    3
    >>> m.isbalanced
    True
    >>> m.left.contents = Mobile(Branch(1, Weight(1)), Branch(2, Weight(1)))
    >>> m.weight
    3
    >>> m.left.contents.isbalanced
    False
    >>> m.isbalanced # All submobiles must be balanced for m to be balanced
    False
    >>> m.left.contents.right.contents.weight = 0.5
    >>> m.left.contents.isbalanced
    True
    >>> m.isbalanced
    False
    >>> m.right.length = 1.5
    >>> m.isbalanced
    True
    """

    def __init__(self, left, right):
        "*** YOUR CODE HERE ***"
        self.left = left
        self.right = right

    @property
    def weight(self):
        """The total weight of the mobile."""
        "*** YOUR CODE HERE ***"

    @property
    def isbalanced(self):
        """True if and only if the mobile is balanced."""
        "*** YOUR CODE HERE ***"

def check_positive(x):
    """Check that x is a positive number, and raise an exception otherwise.

    >>> check_positive('hello')
    Traceback (most recent call last):
    ...
    TypeError: hello is not a number
    >>> check_positive('1')
    Traceback (most recent call last):
    ...
    TypeError: 1 is not a number
    >>> check_positive(-2)
    Traceback (most recent call last):
    ...
    ValueError: -2 <= 0
    """
    "*** YOUR CODE HERE ***"


class Branch(object):
    """A branch of a simple binary mobile."""

    def __init__(self, length, contents):
        if type(contents) not in (Weight, Mobile):
            raise TypeError(str(contents) + ' is not a Weight or Mobile')
        check_positive(length)
        self.length = length
        self.contents = contents

    @property
    def torque(self):
        """The torque on the branch"""
        return self.length * self.contents.weight


class Weight(object):
    """A weight."""
    def __init__(self, weight):
        check_positive(weight)
        self.weight = weight
        self.isbalanced = True

Q2. (Python evaluation and recursion review) Your partner designed a beautiful balanced Mobile, but forgot to fill in the classes of each part, instead just writing T.

T(T(4,T(T(4,T(1)),T(1,T(4)))),T(2,T(10)))

The built-in Python funciton eval takes a string argument, evaluates it as a Python expression, and returns its value.

Complete the definition of interpret_mobile so that it returns a well-formed mobile by guessing the class for each T. The function should exhaustively test all possible combinations of types, then attempt to eval the resulting string when no T remains, handling TypeErrors until a correct series of types is found.

Warning: Interpreting a large mobile is quite slow (can you say why?). You will want to remove the doctest for the large mobile during development:

def interpret_mobile(s):
    """Return a Mobile described by string s by substituting one of the classes
    Branch, Weight, or Mobile for each occurrenct of the letter T.

    >>> simple = 'Mobile(T(2,T(1)), T(1,T(2)))'
    >>> interpret_mobile(simple).weight
    3
    >>> interpret_mobile(simple).isbalanced
    True
    >>> s = 'T(T(4,T(T(4,T(1)),T(1,T(4)))),T(2,T(10)))'
    >>> m = interpret_mobile(s)
    >>> m.weight
    15
    >>> m.isbalanced
    True
    """
    next_T = s.find('T')        # The index of the first 'T' in s.
    if next_T == -1:            # The string 'T' was not found in s
        try:
            return eval(s)      # Interpret s
        except TypeError as e:
            return None         # Return None if s is not a valid mobile
    for t in ('Branch', 'Weight', 'Mobile'):
        "*** YOUR CODE HERE ***"
    return None

Q3. The Stream class from lecture appears below, along with a function that returns an infinite stream of integers. To extend it, implement an __iter__ method using a yield statement that returns a generator over the elements of the stream. Also add a __getitem__ method to support item selection.

The zip function in the doctest for __iter__ combines the corresponding elements of two iterables into pairs until one iterator raises StopIteration:

class Stream(object):
    """A lazily computed recursive list."""

    class empty(object):
        def __repr__(self):
            return 'Stream.empty'

    empty = empty()

    def __init__(self, first, compute_rest=lambda: Stream.empty):
        assert callable(compute_rest), 'compute_rest must be callable.'
        self.first = first
        self._compute_rest = compute_rest
        self._rest = None

    @property
    def rest(self):
        """Return the rest of the stream, computing it if necessary."""
        if self._compute_rest is not None:
            self._rest = self._compute_rest()
            self._compute_rest = None
        return self._rest

    def __repr__(self):
        return 'Stream({0}, <...>)'.format(repr(self.first))

    def __iter__(self):
        """Return an iterator over the elements in the stream.

        >>> s = make_integer_stream(1) # [1, 2, 3, 4, 5, ...]
        >>> list(zip(range(6), s))
        [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6)]
        """
        "*** YOUR CODE HERE ***"

    def __getitem__(self, k):
        """Return the k-th element of the stream.

        >>> s = make_integer_stream(5)
        >>> s[0]
        5
        >>> s[1]
        6
        >>> [s[i] for i in range(7,10)]
        [12, 13, 14]
        """
        "*** YOUR CODE HERE ***"

def make_integer_stream(first=1):
    """Return an infinite stream of increasing integers."""
    def compute_rest():
        return make_integer_stream(first+1)
    return Stream(first, compute_rest)

Q4. Implement the function scale_stream that returns a stream over each element of an input stream, scaled by k:

def scale_stream(s, k):
    """Return a stream over the elements of s scaled by a number k.

    >>> s = scale_stream(make_integer_stream(3), 5)
    >>> s.first
    15
    >>> s.rest
    Stream(20, <...>)
    >>> scale_stream(s.rest, 10)[2]
    300
    """
    "*** YOUR CODE HERE ***"

Q5. A famous problem, first raised by R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, and 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement. As an alternative, we can build a stream of such numbers. Let us call the required stream of numbers s and notice the following facts about it.

Now all we have to do is combine elements from these sources. For this we define a procedure merge that combines two ordered streams into one ordered result stream, eliminating repetitions.

Fill in the definition of merge, then fill in the definition of make_s below:

def merge(s0, s1):
    """Return a stream over the elements of increasing s0 and s1, removing
    repeats.

    >>> ints = make_integer_stream(1)
    >>> twos = scale_stream(ints, 2)
    >>> threes = scale_stream(ints, 3)
    >>> m = merge(twos, threes)
    >>> [m[i] for i in range(10)]
    [2, 3, 4, 6, 8, 9, 10, 12, 14, 15]
    """
    if s0 is Stream.empty:
        return s1
    if s1 is Stream.empty:
        return s0
    e0, e1 = s0.first, s1.first
    if e0 < e1:
        return Stream(e0, lambda: merge(s0.rest, s1))
    elif e1 < e0:
        return Stream(e1, lambda: merge(s0, s1.rest))
    else:
        "*** YOUR CODE HERE ***"

def make_s():
    """Return a stream over all positive integers with only factors 2, 3, & 5.

    >>> s = make_s()
    >>> [s[i] for i in range(20)]
    [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36]
    """
    def rest():
        "*** YOUR CODE HERE ***"
    s = Stream(1, rest)
    return s

Q6. (Extra for Experts) An iterator can enumerate the items in a tree as well as a sequence. Implement values, which interleaves the values of the branches of a tree.

Implement values in terms of the helper function interleave, described below. Both of these functions, values and interleave, should return generators that yield values incrementally rather than constructing a sequence.

Hint: The itertools module provides functions and recipes that may be helpful:

class Tree:
    """An n-ary tree with internal values."""
    def __init__(self, value, branches=[]):
        self.value = value
        self.branches = branches

def values(t):
    """Yield values of a tree by interleaving iterators of the branches.

    >>> T = Tree
    >>> t = T(1, [T(2, [T(4), T(6, [T(8)])]), T(3, [T(5), T(7)])])
    >>> tuple(values(t))
    (1, 2, 3, 4, 5, 6, 7, 8)
    """
    "*** YOUR CODE HERE ***"

def interleave(*iterables):
    """Interleave elements of iterables.

    >>> tuple(interleave([1, 4], [2, 5, 7, 8], [3, 6]))
    (1, 2, 3, 4, 5, 6, 7, 8)
    """
    "*** YOUR CODE HERE ***"