61A Homework 6

Due by 11:59pm on Monday, 7/15

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

Readings. Section 2.4 of the online lecture notes.

Q1. Read Albert's debugging guidelines. Then fix the problems with the following code. (Only fix the bugs; do not change the structure of the computation.).

def divide_by_fact(dividend, n):
    """Recursively divide dividend by the factorial of n.

    >>> divide_by_fact(120, 4)
    5.0
    """
    if n < 0:
      return dividend
     return divide_by_fact(dividend / n, n - 1)

Q2. Write a recursive function that divides an input sequence into a tuple of smaller sequences that each contain 4 or 5 elements from the original sequence. For example, an input sequence of 14 elements should be divided into sequences of 4, 5, and 5 elements. Use as few 5-element sequences as necessary in the result, and all 5-element sequences should be at the end. Finally, preserve the relative ordering of elements from the original sequence.

Hint: You may assume that the input sequence has length at least 12. Think carefully about how many base cases you need, and what they should be.

def group(seq):
    """Divide a sequence of at least 12 elements into groups of 4 or
    5. Groups of 5 will be at the end. Returns a tuple of sequences, each
    corresponding to a group.

    >>> group(range(14))
    (range(0, 4), range(4, 9), range(9, 14))
    >>> group(tuple(range(17)))
    ((0, 1, 2, 3), (4, 5, 6, 7), (8, 9, 10, 11), (12, 13, 14, 15, 16))
    """
    num = len(seq)
    assert num >= 12
    "*** YOUR CODE HERE ***"

Pizza Sort

Leonardo da Vinci is well know for his inventions, his paintings, and his numerous contributions to many other fields. It is less known that he only turned to art after failing miserably as an apprentice in a pizzeria. (Granted, modern pizza was invented centuries after his era, but its precursors have been around since Roman times.)

One day, little Leonardo was at the pizzeria, mindlessly flipping over partially cooked crusts with a spatula. At that moment, inspiration struck, and he realized that he could sort the crusts in a stack, so that the largest ended up at the bottom and the smallest at the top, with each crust smaller than the one below it. He named his procedure "pizza sort" and wrote it down in a journal.

Unfortunately, that journal was lost to time, so pizza sort, perhaps Leonardo's greatest invention, remained unknown. Until now. Last year, a previously unknown journal was found in the hands of a private collector, and it appears to be that elusive journal in which Leonardo recorded his pizza sort. Unfortunately, time has not been kind to the journal, so many details are missing. But archaeologists have managed to recover one key piece of the puzzle: the only allowed move in pizza sort is to place the spatula under a crust in the stack and flip the set of crusts above the spatula:

"""

   ====
    ==
========== <--- spatula underneath this crust
 ========

    ||
    ||
   \||/
    \/

========== }
    ==     } flipped
   ====    }
 ========

"""

Q3. Implement this flip operation in code, with the stack of crusts represented as a list starting from the bottom of the stack. Write a function partial_reverse to reverse the subset of a list starting from start until the end of the list. This reversal should be in-place, meaning that the original list is modified. Do not create a new list inside your function, even if you do not return it.

Note: As can be seen from the doctests, partial_reverse should return None. (Don't put in an explicit return None, however; either leave out any return statement or just use return with no expression.)

def partial_reverse(lst, start):
    """Reverse part of a list in-place, starting with start up to the end of
    the list.

    >>> a = [1, 2, 3, 4, 5, 6, 7]
    >>> partial_reverse(a, 2)
    >>> a
    [1, 2, 7, 6, 5, 4, 3]
    >>> partial_reverse(a, 5)
    >>> a
    [1, 2, 7, 6, 5, 3, 4]
    """
    "*** YOUR CODE HERE ***"

The archaeologists also found some indecipherable symbols along with the description of the above procedure. As they could make neither heads nor tails of it, they called it "the da Vinci code." Hoping to crack it, they asked Eva Lu Ator, a leading computer scientist, for help. Upon closer examination, she realized that the da Vinci code was actual code, in a rudimentary programming language that Leonardo had invented. This code would find the position of the largest crust in a stack of pizzas.

Q4. Help Eva to translate the da Vinci code into Python. Write a function that takes in a sequence and returns the index of the largest element in the sequence:

def index_largest(seq):
    """Return the index of the largest element in the sequence.

    >>> index_largest([8, 5, 7, 3 ,1])
    0
    >>> index_largest((4, 3, 7, 2, 1))
    2
    """
    assert len(seq) > 0
    "*** YOUR CODE HERE ***"

Q5. Finally, help the world learn the secret of the da Vinci code by writing the pizza_sort function. This function takes in a list and sorts its elements in descending order, using only the previous two functions and the built-in len function. It is well-known that Leonardo hated iteration, so make sure to use recursion instead. (You may define a helper function if you want.) Lastly, you may use slicing; we are talking about pizza, after all.

(Keep in mind, however, that slicing returns a new list, but you need to sort the existing list in place.)

def pizza_sort(lst):
    """Perform an in-place pizza sort on the given list, resulting in
    elements in descending order.

    >>> a = [8, 5, 7, 3, 1, 9, 2]
    >>> pizza_sort(a)
    >>> a
    [9, 8, 7, 5, 3, 2, 1]
    """
    "*** YOUR CODE HERE ***"

Marvel in the genius that was Leonardo da Vinci!

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

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

Q8. (Extra for Experts) Recall the count_change function from earlier in the semester. (Below, we have converted it to use a tuple rather than a function to represent a coin sequence, but it is otherwise the same.) It was quite slow on larger inputs, since it repeated the same computation many times. Instead, write a function make_count_change that produces a more efficient version of count_change. This more efficient version should only perform any computation if it is called with a new pair of arguments. If it is called with a pair of arguments previously seen, then it should just return the previously computed value. Once you are done, compare the two versions on a large number such as 500 to make sure that your code is faster than the original version.

# Old version
def count_change(a, coins=(50, 25, 10, 5, 1)):
    if a == 0:
        return 1
    elif a < 0 or len(coins) == 0:
        return 0
    return count_change(a, coins[1:]) + count_change(a - coins[0], coins)

# Version 2.0
def make_count_change():
    """Return a function to efficiently count the number of ways to make
    change.

    >>> cc = make_count_change()
    >>> cc(500, (50, 25, 10, 5, 1))
    59576
    """
    "*** YOUR CODE HERE ***"