Homework 5

Due by 9:00pm on Friday, 10/05/2018

Instructions

Download hw05.zip. Inside the archive, you will find starter files for the questions in this homework, along with a copy of the OK autograder.

Submission: When you are done, submit the homework by uploading the hw05.py file to okpy.org. You may submit more than once before the deadline; only the final submission will be scored.

Readings: This homework relies on following references:

Recursion: revisiting Map, Filter, and Reduce

In this next section you are going to implement the filter and reduce functions we learned in lab04 using recursion. Feel free to refer to lab04 for guidance and more examples Lab04.

We wrote the recursive version of the function map in lecture. Here it is again:

map takes

  • m - a one-argument function that you want to map onto each element in the list.
  • s - a sequence of values
def map(f, s):
    """
    Map a function f onto a sequence.

    >>> def double(x):
    ...     return x * 2
    >>> def square(x):
    ...     return x ** 2
    >>> def toLetter(x):
    ...     alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
    ...     return alpha[x%26]
    >>> map(double, [1,2,3,4])
    [2, 4, 6, 8]
    >>> map(square, [1, 2, 3, 4, 5, 10])
    [1, 4, 9, 16, 25, 100]
    >>> map(toLetter, [3, 0, 19, 0])
    ['d', 'a', 't', 'a']

    """
    if s == []:
        return s
    return [f(s[0])] + map(f, s[1:])

Question 1: Filter

Write the recursive version of the function filter which takes

  • filter - a one-argument function that returns True if the argument passed in should be included in the list, and False otherwise.
  • s - a sequence of values
def filter(f, s):
    """Filter a sequence to only contain values allowed by filter.

    >>> def is_even(x):
    ...     return x % 2 == 0
    >>> def divisible_by5(x):
    ...     return x % 5 == 0
    >>> filter(is_even, [1,2,3,4])
    [2, 4]
    >>> filter(divisible_by5, [1, 4, 9, 16, 25, 100])
    [25, 100]
    """
    "*** YOUR CODE HERE ***"
    return _____

Use OK to test your code:

python3 ok -q filter --local

Question 2: Reduce

Write the recursive version of the function reduce which takes

  • reducer - a two-argument function that reduces elements to a single value
  • s - a sequence of values
  • base - the starting value in the reduction. This is usually the identity of the reducer

If you're feeling stuck, think about the parameters of reduce.

from operator import add, mul

def reduce(reducer, s, base):
    """Reduce a sequence under a two-argument function starting from a base value.

    >>> def add(x, y):
    ...     return x + y
    >>> def mul(x, y):
    ...     return x*y
    >>> reduce(add, [1,2,3,4], 0)
    10
    >>> reduce(mul, [1,2,3,4], 0)
    0
    >>> reduce(mul, [1,2,3,4], 1)
    24
    """
    "*** YOUR CODE HERE ***"
    return _____

Use OK to test your code:

python3 ok -q reduce --local

Recursion: Let's do some Math

Question 3: Number representation

Whenever we think of numbers, we are actually thinking of them in relation to some base. Typically that base is 10. Each number can be decomposed as a combination of the powers of it's base.

134 = 1 * 10^2 + 3 * 10^1 + 4 * 10^0

Write a function that takes a number and returns a list of it's decimal representation.

def decimal(n):
    """Return a list representing the decimal representation of a number.

    >>> decimal(55055)
    [5, 5, 0, 5, 5]
    >>> decimal(-136)
    ['-', 1, 3, 6]
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q decimal --local

We can also represent numbers in different bases. Think of how you could represent the number 5 in base 2. Essentially, how can you break the number 5 into powers of 2. It contains one 4 and one 1. In base 2, your digit overflows after 1, so this representation of numbers only has 1 and 0.

5 = 1 * 2^2 + 0 * 2^1 + 1 * 2^0

Write a function that takes a number and returns a list of it's representation in base 2.

def binary(n):
    """Return a list representing the representation of a number in base 2.

    >>> binary(55055)
    [1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]
    >>> binary(-136)
    ['-', 1, 0, 0, 0, 1, 0, 0, 0]
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q binary --local

Question 4: Count Digit

Write a function that takes a positive integer n and returns the number of times the number digit appears. Do not use any assignment statements.

def count_digit(n, digit):
    """Return how many times digit appears in n.

    >>> count_digit(55055, 5)
    4
    >>> count_digit(1231421, 1)
    3
    >>> count_digit(12, 3)
    0
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q count_digit --local

Question 5: Ten-Pairs

Write a function that takes a positive integer n and returns the number of ten-pairs it contains. A ten-pair is a pairs of digits within n that sum to 10. Do not use any assignment statements.

The number 7,823,952 has 3 ten-pairs. The first and fourth digits sum to 7+3=10, the second and third digits sum to 8+2=10, and the second and last digit sum to 8+2=10:

Hint: What if you had a function that counted the times a certain digit appeared. 

def ten_pairs(n):
    """Return the number of ten-pairs within positive integer n.

    >>> ten_pairs(7823952)
    3
    >>> ten_pairs(55055)
    6
    >>> ten_pairs(9641469)
    6
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q ten_pairs --local

Challenge Questions

Questions in this section are not required for submission.

Question 6: 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:

python3 ok -q count_change --local

Question 7: Fibonacci Tail

Write a tail recursive function that returns the nth element of the fibonacci sequence.

As a reminder, Fibonacci is defined as a function where:

Fibonacci Tree

In your function signature, you can add default values for arguments.

For Example: def f(a = 1): defines a function named f that requires an argument a. If a is not specified a gets the value 1. f() is the same as typing f(1) in this case.

def fibonacci(n, nMinus2 = 0, nMinus1 = 1):
    """Return the nth fibonacci number.

    >>> fibonacci(11)
    89
    >>> fibonacci(5)
    5
    >>> fibonacci(0)
    0
    >>> fibonacci(1)
    1
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q fibonacci --local