Diagnostic 4: Week 4 review

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.

Trees

Question 1: Countdown

Define the function countdown_tree so that it returns the specific tree below. Make sure to use the tree constructor from the Data Abstraction!

    10
   / \
  /   \
 9     7
 |     |
 8     6
       |
       5

The doctest below shows the print_tree representation:

def countdown_tree():
    """Return a tree that has the following structure.

    >>> print_tree(countdown_tree())
    10
      9
        8
      7
        6
          5
    """

    "*** YOUR CODE HERE ***"

    return tree(10, [tree(9, [tree(8)]),
                    tree(7, [tree(6, [tree(5)])])])

Question 2

Define max_tree, which takes a tree and returns the largest entry in teh tree.

def max_tree(t):

    "*** YOUR CODE HERE ***"

    if is_leaf(t):
        return entry(t)
    return max(entry(t), max([max_tree(s) for s in subtrees(t)]))

Question 3: Size

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

def size_of_tree(t):
    """Return the number of entries in the tree.

    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    >>> size_of_tree(numbers)
    7
    """

    "*** YOUR CODE HERE ***"

    return 1 + sum([size_of_tree(t) for t in subtrees(t)])

# Alternate solution
def size_of_tree(t):
    subtrees_sum = 0
    for subtree in subtrees(t):
        subtrees_sum += size_of_tree(subtree)
    return 1 + subtrees_sum

Question 4: Same shape

Define a function same_shape that, given two trees, t1 and t2, returns True if the two trees have the same shape (but not necessarily the same data in each node) and False otherwise.

def same_shape(t1, t2):
    """Return True if t1 is indentical in shape to t2.

    >>> test_tree1 = tree(1, [tree(2), tree(3)])
    >>> test_tree2 = tree(4, [tree(5), tree(6)])
    >>> test_tree3 = tree(1,
    ...                   [tree(2,
    ...                         [tree(3)])])
    >>> test_tree4 = tree(4,
    ...                   [tree(5,
    ...                         [tree(6)])])
    >>> same_shape(test_tree1, test_tree2)
    True
    >>> same_shape(test_tree3, test_tree4)
    True
    >>> same_shape(test_tree2, test_tree4)
    False
    """

    "*** YOUR CODE HERE ***"

    s1, s2 = subtrees(t1), subtrees(t2)
    if len(s1) != len(s2):
        return False
    for index in range(len(s1)):
        if not same_shape(s1[index], s2[index]):
            return False
    return True

# Alternate solution
def same_shape(t1, t2):
    children_same = all(map(same_shape, subtrees(t1), subtrees(t2)))
    return len(subtrees(t1)) == len(subtrees(t2)) and children_same

Mutability

Question 5: Fibonacci

Write a function make_fib that returns a function that returns the next Fibonacci number each time it is called.

def make_fib():
    """Returns a function that returns the next Fibonacci number
    every time it is called.

    >>> fib = make_fib()
    >>> fib()
    0
    >>> fib()
    1
    >>> fib()
    1
    >>> fib()
    2
    >>> fib()
    3
    """

    "*** YOUR CODE HERE ***"

    cur, next = 0, 1
    def fib():
        nonlocal cur, next
        result = cur
        cur, next = next, cur + next
        return result
    return fib

Question 6

Define a function make_accumulator that returns an accumulator function, which takes one numerical argument and returns the sum of all arguments ever passed to accumulator. Use a list and not a nonlocal statement:

def make_accumulator():
    """Return an accumulator function that takes a single numeric argument and
    accumulates that argument into total, then returns total.

    >>> acc = make_accumulator()
    >>> acc(15)
    15
    >>> acc(10)
    25
    >>> acc2 = make_accumulator()
    >>> acc2(7)
    7
    >>> acc3 = acc2
    >>> acc3(6)
    13
    >>> acc2(5)
    18
    >>> acc(4)
    29
    """

    "*** YOUR CODE HERE ***"

    total = [0]
    def accumulator(amount):
        total[0] += amount
        return total[0]
    return accumulator

Question 7

Define a function make_accumulator_nonlocal that returns an accumulator function, which takes one numerical argument and returns the sum of all arguments ever passed to accumulator. Use a nonlocal statement, but no list or dict:

def make_accumulator_nonlocal():
    """Return an accumulator function that takes a single numeric argument and
    accumulates that argument into total, then returns total.

    >>> acc = make_accumulator_nonlocal()
    >>> acc(15)
    15
    >>> acc(10)
    25
    >>> acc2 = make_accumulator_nonlocal()
    >>> acc2(7)
    7
    >>> acc3 = acc2
    >>> acc3(6)
    13
    >>> acc2(5)
    18
    >>> acc(4)
    29
    """

    "*** YOUR CODE HERE ***"

    total = 0
    def accumulator(amount):
        nonlocal total
        total += amount
        return total
    return accumulator

Question 8: Filter

Write a function that filters a list, only keeping elements that satisfy the predicate. Be sure to mutate the original list.

This function should NOT return anything. This is to emphasize that this function should utilize mutability.

def filter(pred, lst):
    """Filters lst with pred using mutation.
    >>> original_list = [5, -1, 2, 0]
    >>> filter(lambda x: x % 2 == 0, original_list)
    >>> original_list
    [2, 0]
    """

    "*** YOUR CODE HERE ***"

    i = len(lst) - 1
    while i >= 0:
        if not pred(lst[i]):
            lst.pop(i)
        i -= 1

def filter(pred, lst):
    """Filters lst with pred using mutation.
    >>> original_list = [5, -1, 2, 0]
    >>> filter(lambda x: x % 2 == 0, original_list)
    >>> original_list
    [2, 0]
    """
    if lst: 
        temp = lst.pop(0)
        filter(pred, lst)
        if pred(temp):
            lst.insert(0, temp)

Question 9: Reverse

Write a function that reverses the given list. Be sure to mutate the original list.

This function should NOT return anything. This is to emphasize that this function should utilize mutability.

def reverse(lst):
    """Reverses lst using mutation.
    >>> original_list = [5, -1, 29, 0]
    >>> reverse(original_list)
    >>> original_list
    [0, 29, -1, 5]
    """

    "*** YOUR CODE HERE ***"

    # iterative solution
    midpoint = len(lst) // 2
    last = len(lst) - 1
    for i in range(midpoint):
        lst[i], lst[last - i] = lst[last - i], lst[i]

# Recursive solution
def reverse(lst):
    """Reverses lst using mutation.
    >>> original_list = [5, -1, 29, 0]
    >>> reverse(original_list)
    >>> original_list
    [0, 29, -1, 5]
    """
    if len(lst) > 1:
        temp = lst.pop()
        reverse(lst)
        lst.insert(0, temp)

# Alternative recursive solution
def reverse(lst):
    """Reverses lst using mutation.
    >>> original_list = [5, -1, 29, 0]
    >>> reverse(original_list)
    >>> original_list
    [0, 29, -1, 5]
    """
    midpoint = len(lst) // 2
    last = len(lst) - 1
    def helper(i):
        if i == midpoint:
            return
        lst[i], lst[last - i] = lst[last - i], lst[i]
        helper(i + 1)
    helper(0)

Object-Oriented Programming

Question 10: Person

Modify the following Person class to add a repeat method, which repeats the last thing said. See the doctests for an example of its use.

Hint: you will have to modify other methods as well, not just the repeat method.

class Person(object):
    """Person class.

    >>> steven = Person("Steven")
    >>> steven.repeat()       # starts at whatever value you'd like
    'I squirreled it away before it could catch on fire.'
    >>> steven.say("Hello")
    'Hello'
    >>> steven.repeat()
    'Hello'
    >>> steven.greet()
    'Hello, my name is Steven'
    >>> steven.repeat()
    'Hello, my name is Steven'
    >>> steven.ask("preserve abstraction barriers")
    'Would you please preserve abstraction barriers'
    >>> steven.repeat()
    'Would you please preserve abstraction barriers'
    """
    def __init__(self, name):
        self.name = name

        "*** YOUR CODE HERE ***"

        self.previous = "I squirreled it away before it could catch on fire."

    def say(self, stuff):

        "*** YOUR CODE HERE ***"

        self.previous = stuff
        return stuff

    def ask(self, stuff):
        return self.say("Would you please " + stuff)

    def greet(self):
        return self.say("Hello, my name is " + self.name)

    def repeat(self):

        "*** YOUR CODE HERE ***"

        return self.say(self.previous)

Question 11: DoubleTalker

Suppose now that we wanted to define a class called DoubleTalker to represent people who always say things twice:

>>> steven = DoubleTalker("Steven")
>>> steven.say("hello")
"hello hello"
>>> steven.say("the sky is falling")
"the sky is falling the sky is falling"

Consider the following three definitions for DoubleTalker that inherit from the Person class:

class DoubleTalker(Person):
    def __init__(self, name):
        Person.__init__(self, name)
    def say(self, stuff):
        return Person.say(self, stuff) + " " + self.repeat()

class DoubleTalker(Person):
    def __init__(self, name):
        Person.__init__(self, name)
    def say(self, stuff):
        return stuff + " " + stuff

class DoubleTalker(Person):
    def __init__(self, name):
        Person.__init__(self, name)
    def say(self, stuff):
        return Person.say(self, stuff + " " + stuff)

Determine which of these definitions work as intended. Also determine for which of the methods the three versions would respond differently. (Don't forget about the repeat method!)

The last one works as intended. For the first and second ones, calling repeat would fail.