61A Homework 8

Note the special time: Due by 7pm on Wednesday, 3/20

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

Readings. Section 2.7 and Section 3.3 of the online lecture notes.

Q1. The following is our Rational implementation from lecture:

from fractions import gcd

class Rational(object):
    """A mutable fraction.

    >>> f = Rational(3, 5)
    >>> f
    Rational(3, 5)
    >>> print(f)
    3/5
    >>> f.float_value
    0.6
    >>> f.numerator = 4
    >>> f.float_value
    0.8
    >>> f.denominator -= 3
    >>> f.float_value
    2.0
    """

    def __init__(self, numer, denom):
        g = gcd(numer, denom)
        self.numerator = numer // g
        self.denominator = denom // g

    @property
    def float_value(self):
        return self.numerator / self.denominator

    def __repr__(self):
        return 'Rational({0}, {1})'.format(self.numerator,
                                           self.denominator)

    def __str__(self):
        return '{0}/{1}'.format(self.numerator, self.denominator)

    def __add__(self, num):
        return add_rational(self, num)

    def __mul__(self, num):
        return mul_rational(self, num)

    def __eq__(self, num):
        return eq_rational(self, num)

    def __bool__(self):
        return self.numerator != 0

def add_rational(r1, r2):
    denom = r1.denominator * r2.denominator
    numer1 = r1.numerator * r2.denominator
    numer2 = r1.denominator * r2.numerator
    return Rational(numer1 + numer2, denom)

def mul_rational(r1, r2):
    return Rational(r1.numerator * r2.numerator,
                    r1.denominator * r2.denominator)

def eq_rational(r1, r2):
        return (r1.numerator * r2.denominator ==
                r2.numerator * r1.denominator)

Alyssa P. Hacker is unhappy with this implementation: she believes that an instance of a rational number should be immutable, so that the user cannot change the number represented by a rational once it has been created. She writes the following subclass of Rational that she thinks is immutable. (You can find documentation on the __setattr__ special method here )

class ImmutableRational(Rational):
    """An immutable fraction.

    >>> f = ImmutableRational(3, 5)
    >>> f
    ImmutableRational(3, 5)
    >>> f.numerator = 4
    >>> f
    ImmutableRational(3, 5)
    >>> f.denominator -= 3
    >>> f
    ImmutableRational(3, 5)
    """

    def __init__(self, numer, denom):
        Rational.__init__(self, numer, denom)
        self.finalized = True

    def __setattr__(self, attr, value):
        if hasattr(self, 'finalized') and self.finalized:
            return
        object.__setattr__(self, attr, value)

    def __repr__(self):
        return 'ImmutableRational({0}, {1})'.format(self.numerator,
                                                    self.denominator)

Show that Alyssa has not completely solved the problem of mutability by completing the function below that mutates an ImmutableRational instance. (Do not use del or __delattr__.)

def mutate_rational(r):
    """Mutate a rational by adding one to its denominator.

    >>> f = ImmutableRational(3, 5)
    >>> f
    ImmutableRational(3, 5)
    >>> mutate_rational(f)
    >>> f
    ImmutableRational(3, 6)
    """
    "*** YOUR CODE HERE ***"

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

Q3. 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 type_tag(s):
    return type_tag.tags[type(s)]

type_tag.tags = {Square: 's', Rect: 'r'}

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

Q4. The following is the Rlist class from lecture, which implements the recursive list data type, and the map_rlist function that maps a given function over a given Rlist to produce a new Rlist:

class Rlist(object):
    """A recursive list consisting of a first element and the rest.

    >>> s = Rlist(1, Rlist(2, Rlist(3)))
    >>> len(s)
    3
    >>> s[0]
    1
    >>> s[1]
    2
    >>> s[2]
    3
    """
    class EmptyList(object):
        def __len__(self):
            return 0
    empty = EmptyList()

    def __init__(self, first, rest=empty):
        self.first = first
        self.rest = rest

    def __repr__(self):
        f = repr(self.first)
        if self.rest is Rlist.empty:
            return 'Rlist({0})'.format(f)
        else:
            return 'Rlist({0}, {1})'.format(f, repr(self.rest))

    def __len__(self):
        return 1 + len(self.rest)

    def __getitem__(self, i):
        if i == 0:
            return self.first
        return self.rest[i - 1]

def map_rlist(fn, s):
    """Return an Rlist resulting from mapping fn over the elements of s.

    >>> s = Rlist(1, Rlist(2, Rlist(3)))
    >>> map_rlist(lambda x: x * x, s)
    Rlist(1, Rlist(4, Rlist(9)))
    """
    if s is Rlist.empty:
        return s
    return Rlist(fn(s.first), map_rlist(fn, s.rest))

Write a new deep_map_rlist function that also maps a given function fn over an Rlist s to produce a new Rlist. However, if s contains an Rlist as an element, then deep_map_rlist should recursively apply fn to each of that Rlist's elements rather than to that Rlist itself.

Hint: You may find the built-in isinstance function useful.

def deep_map_rlist(fn, s):
    """Return an Rlist with the same structure as s but with fn mapped over
    its elements. An element that is an Rlist will have fn recursively mapped
    over its elements.

    >>> s = Rlist(1, Rlist(Rlist(2, Rlist(3)), Rlist(4)))
    >>> deep_map_rlist(lambda x: x * x, s)
    Rlist(1, Rlist(Rlist(4, Rlist(9)), Rlist(16)))
    """
    "*** YOUR CODE HERE ***"

Q5. (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 (~10 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, Rlist(4, Rlist(5)))))
    >>> s.rest.rest.rest.rest.rest = s.rest.rest
    >>> has_cycle(s)
    True
    >>> t = Rlist(1, Rlist(2, Rlist(3, Rlist(4, Rlist(5)))))
    >>> 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, Rlist(4, Rlist(5)))))
    >>> s.rest.rest.rest = s
    >>> has_cycle_constant(s)
    True
    >>> t = Rlist(1, Rlist(2, Rlist(3, Rlist(4, Rlist(5)))))
    >>> has_cycle_constant(t)
    False
    """
    "*** YOUR CODE HERE ***"