Homework 7 Solutions

Solutions: You can find the file with solutions for all questions here.

Question 1: 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, seq, 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
    """
    if seq == []:
        return base
    next_base = reducer(base, seq[0])
    return reduce(reducer, seq[1:], next_base)

Use OK to test your code:

python3 ok -q reduce

Question 2: Remove Last from Sequence

Complete the recursive function remove_last which creates a new list identical to the input list s but with the last element in the sequence that is equal to x removed.

def remove_last(x, s):
    """Create a new list that is identical to s but with the last
    element from the list that is equal to x removed.

    >>> remove_last(1,[])
    []
    >>> remove_last(1,[1])
    []
    >>> remove_last(1,[1,1])
    [1]
    >>> remove_last(1,[2,1])
    [2]
    >>> remove_last(1,[3,1,2])
    [3, 2]
    >>> remove_last(1,[3,1,2,1])
    [3, 1, 2]
    >>> remove_last(5, [3, 5, 2, 5, 11])
    [3, 5, 2, 11]
    """
    if not s:
        return []
    elif s[-1] == x:
        return s[0:-1]
    else:
        return remove_last(x, s[0:-1]) + [s[-1]]

Illustrated here is a more complete doctest that shows good testing methodology. It is a little cumbersome as documentation, but you'll want to think about it for your projects. Test every condition that might come up. Then you won't be surprised when it does.

Use OK to test your code:

python3 ok -q remove_last

Question 3: Create Number from Lists

Write a recursive function create_num_from_lsts that creates a number with the elements from lst1 and lst2 as digits in that order.

def create_num_from_lsts(lst1, lst2):
    """ Create a number with the elements from lst1 and lst2 as digits in that order.

    >>> create_num_from_lsts([1, 2, 3], [4, 5, 6])
    123456
    >>> create_num_from_lsts([5, 4, 2, 4], [1, 7])
    542417
    >>> create_num_from_lsts([3], [9, 8])
    398
    """
    if not lst1 and not lst2:
        return 0
    elif not lst2:
        return create_num_from_lsts(lst2, lst1)
    else:
        return lst2[-1] + 10 * create_num_from_lsts(lst1, lst2[:-1])

Use OK to test your code:

python3 ok -q create_num_from_lsts

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
    """
    if amount < 0 or denominations == []:
        return 0
    elif amount == 0:
        return 1
    using_coin = count_change(amount - denominations[0], denominations)
    not_using_coin = count_change(amount, denominations[1:])
    return using_coin + not_using_coin

Use OK to test your code:

python3 ok -q count_change

Submit

Make sure to submit this assignment by running:

python3 ok --submit