Diagnostic 5: Week 5 review | CS 61A Summer 2015

Diagnostics are meant for you to check your understanding of the week's material. They are not worth any points and are not counted towards midterm recovery points; instead, diagnostics are solely for your benefit. If you find yourself struggling with the questions in this diagnostic, consider signing up for Tutoring.

Mutable Linked Lists

Question 1: Slice

Implement a function slice_link that slices a given link. slice_link should slice the link starting at start and ending one element before end, as with a normal Python list.

def slice_link(link, start, end):
    """Slices a Link from start to end (as with a normal Python list).

    >>> link = Link(3, Link(1, Link(4, Link(1, Link(5, Link(9))))))
    >>> new = slice_link(link, 1, 4)
    >>> print_link(new)
    <1 4 1>
    """
    "*** YOUR CODE HERE ***"
    if end == 0:
        return Link.empty
    elif start == 0:
        return Link(link.first, slice_link(link.rest, 0, end-1))
    else:
        return slice_link(link.rest, start-1, end-1)

Note: This was an extra question in Lab 9.

Question 2: Add Links

Let's implement a method in order to add together items of link1 and link2. Do not assume that the links are the same length.

def add_links(link1, link2):
    """Adds two Links, returning a new Link

    >>> l1 = Link(1, Link(2))  
    >>> l2 = Link(3, Link(4, Link(5)))
    >>> new = add_links(l1,l2)
    >>> print_link(new)
    <1 2 3 4 5>
    """
    "*** YOUR CODE HERE ***"
    if link1 is not Link.empty:
        return Link(link1.first, add_links(link1.rest, link2))
    elif link2 is not Link.empty:
        return Link(link2.first, add_links(link1, link2.rest))
    else:
        return Link.empty

# Iterative version (using reverse)
def add_links(link1, link2):
    result = Link.empty
    while link1 is not Link.empty:
        result = Link(link1.first, result)
        link1 = link1.rest
    while link2 is not Link.empty:
        result = Link(link2.first, result)
        link2 = link2.rest
    return reverse(result)

Note: This was an extra question in Lab 9.

Implement mutate_reverse, a recursive mutating version of reverse. Have it mutate the original Link so that its elements are reversed.

def mutate_reverse(link):
    """Mutates the Link so that its elements are reversed.

    >>> link = Link(1)
    >>> mutate_reverse(link)
    >>> link
    Link(1)

    >>> link = Link(1, Link(2, Link(3)))
    >>> mutate_reverse(link)
    >>> link
    Link(3, Link(2, Link(1)))
    """
    "*** YOUR CODE HERE ***"
    if link is Link.empty or link.rest is Link.empty:
        return
    mutate_reverse(link.rest)
    while link.rest is not Link.empty:
        link.first, link.rest.first = link.rest.first, link.first
        link = link.rest

# O(n) solution
def mutate_reverse(link):
    """Mutates the Link so that its elements are reversed.

    >>> link = Link(1)
    >>> mutate_reverse(link)
    >>> link
    Link(1)

    >>> link = Link(1, Link(2, Link(3)))
    >>> mutate_reverse(link)
    >>> link
    Link(3, Link(2, Link(1)))
    """
    reverse_helper(link)

def reverse_helper(link):
    if link.rest is not Link.empty:
        second, last = link.rest, link
        link = reverse_helper(second)
        second.rest, last.rest = last, link.empty
    return link

Mutable Trees

Question 3: Cumulative sum

Write a function cumulative_sum that returns a new Tree, where each entry is the sum of all entries in the corresponding subtree of the old Tree.

def cumulative_sum(t):
    """Return a new Tree, where each entry is the sum of all entries in the
    corresponding subtree of t.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative = cumulative_sum(t)
    >>> t
    Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative
    Tree(16, [Tree(8, [Tree(5)]), Tree(7)])
    >>> cumulative_sum(Tree(1))
    Tree(1)
    """
    "*** YOUR CODE HERE ***"
    subtrees = [cumulative_sum(st) for st in t.subtrees]
    new_entry = sum(st.entry for st in subtrees) + t.entry
    return Tree(new_entry, subtrees)

Question 4: Leaves

Write a function leaves that returns a list of all the entries of the leaf nodes of a Tree.

def leaves(t):
    """Returns a list of all the entries of the leaf nodes of the Tree t.

    >>> leaves(Tree(1))
    [1]
    >>> leaves(Tree(1, [Tree(2, [Tree(3)]), Tree(4)]))
    [3, 4]
    """
    "*** YOUR CODE HERE ***"
    if t.is_leaf():
        return [t.entry]
    all_leaves = []
    for b in t.subtrees:
        all_leaves += leaves(b)
    return all_leaves

Binary Trees and Binary Search Trees

Question 5: Size

Define the function size which takes in a BinaryTree as an argument and returns the number of entries in the tree.

def size(b):
    r""" Return the number of entries in the binary tree b.

    >>> b = BinaryTree(4,
    ...         BinaryTree(2,
    ...             BinaryTree(1)),
    ...         BinaryTree(6,
    ...             BinaryTree(5)))
    >>> size(b)
    5
    """
    "*** YOUR CODE HERE ***"
    if b is BinaryTree.empty:
        return 0
    return 1 + size(tree.left) + size(tree.right)

Question 6: Max

Define the function bst_max which takes in a binary search tree and returns the max of all of the values of each node in the tree. Be sure to take advantage of the properties of the binary search tree to get an efficient solution.

You may assume the input is a non-empty BinaryTree.

def bst_max(b):
    r""" Returns the max of all the values of each node in b.

    Calling bst_max on the following tree should return 6:

            4
           / \
          2   6
         /   /
        1   5

    >>> b = BinaryTree(4,
    ...         BinaryTree(2,
    ...             BinaryTree(1)),
    ...         BinaryTree(6,
    ...             BinaryTree(5)))
    >>> bst_max(t)
    6
    """
    "*** YOUR CODE HERE ***"
    if b.right is BinaryTree.empty:
        return b.entry
    return bst_max(b.right)

Question 7: Min

Define the function bst_min which takes in a binary search tree and returns the min of all of the values of each node in the tree. Be sure to take advantage of the properties of the binary search tree to get an efficient solution.

You may assume the input is a non-empty BinaryTree.

def bst_min(b):
    r""" Returns the min of all the values of each node in b.

    Calling bst_min on the following tree should return 1:

            4
           / \
          2   6
         /   /
        1   5

    >>> b = BinaryTree(4,
    ...         BinaryTree(2,
    ...             BinaryTree(1)),
    ...         BinaryTree(6,
    ...             BinaryTree(5)))
    >>> bst_min(t)
    1
    """
    "*** YOUR CODE HERE ***"
    if b.left is BinaryTree.empty:
        return b.entry
    return bst_min(b.left)

Interfaces

For the following interface questions, you'll be implementing magic methods for the following Rational class, which represents a rational number. A rational number consists of a numerator and a denominator, both of which are integers.

from fractions import gcd

class Rational:
    def __init__(self, numer, denom):
        factor = gcd(numer, denom)
        self.numer = numer // factor
        self.denom = denom // factor

Question 8: Repr

Implement the __repr__ method for the Rational class. See the doctests for expected behavior.

def __repr__(self):
    """
    >>> r = Rational(4, 6)
    >>> r
    Rational(2, 3)
    >>> repr(r)
    'Rational(2, 3)'
    """
    "*** YOUR CODE HERE ***"
    return 'Rational({0}, {1})'.format(self.numer, self.denom)

Question 9: Str

Implement the __str__ method for the Rational class. See the doctests for expected behavior.

def __str__(self):
    """
    >>> r = Rational(4, 6)
    >>> print(r)
    2 / 3
    >>> str(r)
    '2 / 3'
    """
    "*** YOUR CODE HERE ***"
    return '{0} / {1}'.format(self.numer, self.denom)

Question 10: Add

Implement the __add__ method for the Rational class. See the doctests for expected behavior.

def __add__(self, other):
    """
    >>> r1 = Rational(2, 3)
    >>> r2 = Rational(4, 5)
    >>> r1 + r2
    Rational(22, 15)
    >>> r1 + 6
    Rational(20, 3)
    """
    "*** YOUR CODE HERE ***"
    if isinstance(other, Rational):
        return Rational(self.numer * other.denom + self.denom * other.numer,
                        self.denom * other.denom)
    elif isinstance(other, int):
        return Rational(self.numer + self.denom * other, self.denom)

Question 11: Neg

Implement the __neg__ method for the Rational class. See the doctests for expected behavior.

def __neg__(self):
    """
    >>> r = Rational(2, 3)
    >>> -r
    Rational(-2, 3)
    """
    "*** YOUR CODE HERE ***"
    return Rational(-self.numer, self.denom)

Question 12: Sub

Implement the __sub__ method for the Rational class. See the doctests for expected behavior.

def __sub__(self, other):
    """
    >>> r1 = Rational(2, 3)
    >>> r2 = Rational(4, 5)
    >>> r1 - r2
    Rational(-2, 15)
    >>> r1 - 1
    Rational(-1, 3)
    """
    "*** YOUR CODE HERE ***"
    return self + (-other)

Question 13: Mul

Implement the __mul__ method for the Rational class. See the doctests for expected behavior.

def __mul__(self, other):
    """
    >>> r1 = Rational(2, 3)
    >>> r2 = Rational(9, 5)
    >>> r1 * r2
    Rational(6, 5)
    >>> r1 * 5
    Rational(10, 3)
    """
    "*** YOUR CODE HERE ***"
    if isinstance(other, Rational):
        return Rational(self.numer * other.numer, self.denom * other.denom)
    elif isinstance(other, int):
        return Rational(self.numer * other, self.denom)

Iterators and Generators

Question 14: Does it work?

Consider the following iterators. Which ones work and which ones don't? Why?

class IteratorA:
    def __init__(self):
        self.start = 5

    def __next__(self):
        if self.start == 100:
            raise StopIteration
        self.start += 5
        return self.start

    def __iter__(self):
        return self

No problem, this is a beautiful iterator.

class IteratorB:
    def __init__(self):
        self.start = 5

    def __iter__(self):
        return self

Oh no! Where is __next__? This fails to implement the iterator interface because calling __iter__ doesn't return something that has a __next__ method.

class IteratorC:
    def __init__(self):
        self.start = 5

    def __next__(self):
        if self.start == 10:
            raise StopIteration
        self.start += 1
        return self.start

This also fails to implement the iterator interface. Without the __iter__ method, the for loop will error. The for loop needs to call __iter__ first because some objects might not implement the __next__ method themselves, but calling __iter__ will return an object that does.

class IteratorD:
    def __init__(self):
        self.start = 1

    def __next__(self):
        self.start += 1
        return self.start

    def __iter__(self):
        return self

This is technically an iterator, because it implements both __iter__ and __next__. Notice that it's an infinite sequence! Sequences like these are the reason iterators are useful. Because iterators delay computation, we can use a finite amount of memory to represent an infinitely long sequence.

Question 15: Str

Write an iterator that takes a string as input:

class Str:
    def __init__(self, str):
        self.str = str
    def __iter__(self):
        return self.str.__iter__()

That works (why?), but just kidding.

class Str:
    """
    >>> s = Str("hello")
    >>> for char in s:
    ...     print(char)
    ...
    h
    e
    l
    l
    o
    """
    def __init__(self, str):
        "*** YOUR CODE HERE ***"
        self.str = str
        self.i = -1
    def __iter__(self):
        "*** YOUR CODE HERE ***"
        return self

    def __next__(self):
        self.i += 1
        if self.i >= len(self.str):
            raise StopIteration
        return self.str[self.i]

Question 16: Countdown

Write a generator that counts down to 0.

Write it in both ways: using a generator function on its own, and within the __iter__ method of a class.

def countdown(n):
    """
    >>> for number in countdown(5):
    ...     print(number)
    ...
    5
    4
    3
    2
    1
    0
    """
    "*** YOUR CODE HERE ***"
    while n >= 0:
        yield n
        n = n - 1

class Countdown:
    """
    >>> for number in Countdown(5):
    ...     print(number)
    ...
    5
    4
    3
    2
    1
    0
    """
    "*** YOUR CODE HERE ***"
    def __init__(self, cur):
        self.cur = cur

    def __iter__(self):
        return self

    def __next__(self):
        result = self.cur
        if result < 0:
            raise StopIteration
        self.cur -= 1
        return result

# Alternate solution that makes __iter__ a generator function:
class Countdown:
    def __init__(self, cur):
        self.cur = cur

    def __iter__(self):
        while self.cur >= 0:
            yield self.cur
            self.cur -= 1

Question 17: Hailstone

Write a generator that outputs the hailstone sequence from homework 1.

def hailstone(n):
    """
    >>> for num in hailstone(10):
    ...     print(num)
    ...
    10
    5
    16
    8
    4
    2
    1
    """
    "*** YOUR CODE HERE ***"
    i = n
    while i > 1:
        yield i
        if i % 2 == 0:
            i //= 2
        else:
            i = i * 3 + 1
    yield i

Question 18: Pairs (generator)

Write a generator function pairs that takes a list and yields all the possible pairs of elements from that list.

Note that this means that you should be yielding a tuple.

def pairs(lst):
    """
    >>> type(pairs([3, 4, 5]))
    <class 'generator'>
    >>> for x, y in pairs([3, 4, 5]):
    ...     print(x, y)
    ...
    3 3
    3 4
    3 5
    4 3
    4 4
    4 5
    5 3
    5 4
    5 5
    """
    "*** YOUR CODE HERE ***"
    for i in lst:
        for j in lst:
            yield i, j

Question 19: Pairs (iterator)

Now write an iterator that does the same thing. You are only allowed to use a linear amount of space - so computing a list of all of the possible pairs is not a valid answer. Notice how much harder it is - this is why generators are useful.

class PairsIterator:
    """
    >>> for x, y in PairsIterator([3, 4, 5]):
    ...     print(x, y)
    ...
    3 3
    3 4
    3 5
    4 3
    4 4
    4 5
    5 3
    5 4
    5 5
    """
    def __init__(self, lst):
        "*** YOUR CODE HERE ***"
        self.lst = lst
        self.i = 0
        self.j = 0
    def __next__(self):
        "*** YOUR CODE HERE ***"
        if self.i == len(self.lst):
            raise StopIteration
        result = (self.lst[self.i], self.lst[self.j])
        if self.j == len(self.lst) - 1:
            self.i += 1
            self.j = 0
        else:
            self.j += 1
        return result
    def __iter__(self):
        "*** YOUR CODE HERE ***"
        return self