Homework 3

Due by 11:59pm on Thursday, 9/22/2016

Instructions

Download hw03.zip. Inside the archive, you will find a file called hw03.py, along with a copy of the OK autograder. Upload the zip file to Jupyter to complete the assignment. See Lab 0 for instructions on using Jupyter to complete assignments.

Submission: When you are done, submit the assignment by uploading the .py file to okpy.org. You may submit more than once before the deadline; only the final submission will be scored. See Lab 0 for instructions on submitting assignments.

Readings: This homework relies on following references:

Required questions

Question 1: Skip Add

Write a function skip_add that takes a single argument n and computes the sum of every other integer between 0 and n starting from n. Assume n is non-negative.

def skip_add(n):
    """ Takes a number x and returns x + x-2 + x-4 + x-6 + ... + 0.

    >>> skip_add(5)  # 5 + 3 + 1 + 0
    9
    >>> skip_add(10) # 10 + 8 + 6 + 4 + 2 + 0
    30
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python ok -q skip_add --local

Question 2: Has Seven

Write a function has_seven that takes a positive integer n and returns whether n contains the digit 7. Do not use any assignment statements - use recursion instead:

def has_seven(k):
    """Returns True if at least one of the digits of k is a 7, False otherwise.

    >>> has_seven(3)
    False
    >>> has_seven(7)
    True
    >>> has_seven(2734)
    True
    >>> has_seven(2634)
    False
    >>> has_seven(734)
    True
    >>> has_seven(7777)
    True
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python ok -q has_seven --local

Question 3: Recursive Min Sort

In Data8 you will find sort to be instrumental to analysis of data. In CS88 you get to build it. There are many sorting algorithms; they have interesting differences and elegant implementations. In lecture we saw a tree recursive formulation of Quick Sort based on the following thinking:

  • Base: an empty list is sorted
  • Recursive leap: to sort a list of length n, assume quick sort works for all lists of length < n; remove the first element, use it to split the rest into two sets (all less-or-equal and all greater), sort both recursively, and put the three pieces back together.

Review the lecture slides if this is unfamiliar to you. In this question we will build another sort algorithm and compare the two using some of your Data8 skills. Here is another idea for sorting.

  • Base: an empty list is sorted
  • Recursive leap: to sort a list of length n > 0, assume that your function will correctly sort lists of length n-1, remove the minimum element in the sequence; sort the remaining list of length n - 1 recursively, put the min element in front of the the sorted remainder.

You have been given a function to find the minimum element (recursively) and a function to remove the first occurence of an element (recursively).
Now you can use those to sort a list (recursively). Complete rsort

# Recursive Min Sort

# Helper function
def first(s):
    """Return the first element in a sequence."""
    return s[0]

# Helper function
def rest(s):
    """Return all elements in a sequence after the first"""
    return s[1:]

# Helper function
def rmin(s):
    """Return the minimum value in a sequence."""
    if len(s) == 1:
        return first(s)
    else:
        return min(first(s), rmin(rest(s)))

# Helper function
def remove(to_remove, s):
    """Returns the sequence s with the first occurrence of to_remove taken out."""
    if s == []:
        return []
    if first(s) == to_remove:
        return rest(s)
    else:
        return [first(s)] + remove(to_remove, rest(s))

def rsort(s):
    """Sort sequence s in ascending order.

    >>> rsort([])
    []
    >>> rsort([1])
    [1]
    >>> rsort([1, 1, 1])
    [1, 1, 1]
    >>> rsort([1, 2, 3])
    [1, 2, 3]
    >>> rsort([3, 2, 1])
    [1, 2, 3]
    >>> rsort([1, 2, 1])
    [1, 1, 2]
    >>> rsort([1,2,3, 2, 1])
    [1, 1, 2, 2, 3]
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python ok -q rsort --local

Question 4: Count Change

A set of coins makes change for n if the sum of the values of the coins is n. For example, if you have 1-cent, 2-cent and 4-cent coins, the following sets make change for 7:

  • 7 1-cent coins
  • 5 1-cent, 1 2-cent coins
  • 3 1-cent, 2 2-cent coins
  • 3 1-cent, 1 4-cent coins
  • 1 1-cent, 3 2-cent coins
  • 1 1-cent, 1 2-cent, 1 4-cent coins

Thus, there are 6 ways to make change for 7. Write a function count_change that takes a positive integer n and a list of the coin denominations and returns the number of ways to make change for n using these coins (Hint: You will need to use tree recursion):

def count_change(amount, denominations):
    """Returns the number of ways to make change for amount.

    >>> denominations = [50, 25, 10, 5, 1]
    >>> count_change(7, denominations)
    2
    >>> count_change(100, denominations)
    292
    >>> denominations = [16, 8, 4, 2, 1]
    >>> count_change(7, denominations)
    6
    >>> count_change(10, denominations)
    14
    >>> count_change(20, denominations)
    60
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python ok -q count_change --local

Challenge question

Questions in this section are not required for submission. However, if you choose to do a challenge question, you can skip another question on the homework without losing points.

Question 5: Towers of Hanoi

A classic puzzle called the Towers of Hanoi is a game that consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with n disks in a neat stack in ascending order of size on a start rod, the smallest at the top, forming a conical shape.

Towers of Hanoi

The objective of the puzzle is to move the entire stack to an end rod, obeying the following rules:

  • Only one disk may be moved at a time.
  • Each move consists of taking the top (smallest) disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
  • No disk may be placed on top of a smaller disk.

Complete the definition of move_stack, which prints out the steps required to move n disks from the start rod to the end rod without violating the rules.

def print_move(origin, destination):
    """Print instructions to move a disk."""
    print("Move the top disk from rod", origin, "to rod", destination)

def move_stack(n, start, end):
    """Print the moves required to move n disks on the start pole to the end
    pole without violating the rules of Towers of Hanoi.

    n -- number of disks
    start -- a pole position, either 1, 2, or 3
    end -- a pole position, either 1, 2, or 3

    There are exactly three poles, and start and end must be different. Assume
    that the start pole has at least n disks of increasing size, and the end
    pole is either empty or has a top disk larger than the top n start disks.

    >>> move_stack(1, 1, 3)
    Move the top disk from rod 1 to rod 3
    >>> move_stack(2, 1, 3)
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 3
    >>> move_stack(3, 1, 3)
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 3 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 1
    Move the top disk from rod 2 to rod 3
    Move the top disk from rod 1 to rod 3
    """
    assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, "Bad start/end"
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python ok -q move_stack --local