Homework 6 | C88C Spring 2023
Homework 6
Due at 11:59:59 pm on Thursday, 3/9/2023.
Instructions
Download hw06.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 with python3 ok –submit. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on okpy.org.
Readings: This homework relies on following references:
Section 1.7
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
seq – a sequence of values
start – 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, start):
“””Reduce a sequence under a two-argument function starting from a start value.
>>> def add(x, y):
… return x + y
>>> def mul(x, y):
… return x*y
>>> reduce(add, [1,2,3,4], 0)
>>> reduce(mul, [1,2,3,4], 0)
>>> reduce(mul, [1,2,3,4], 1)
“*** YOUR CODE HERE ***”
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 lst but with the last element in the sequence that is equal to x removed.
Hint: Remember that you can use negative indexing on lists! For example lst[-1] refers to the last element in a list lst, lst[-2] refers to the second to last element…
def remove_last(x, lst):
“””Create a new list that is identical to lst 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])
>>> remove_last(1,[2,1])
>>> remove_last(1,[3,1,2])
>>> remove_last(1,[3,1,2,1])
>>> remove_last(5, [3, 5, 2, 5, 11])
[3, 5, 2, 11]
“*** YOUR CODE HERE ***”
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: Map
Write the recursive version of the function map which 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, seq):
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’]
“*** YOUR CODE HERE ***”
Use OK to test your code:
python3 ok -q map
Question 4: Hailstone
For the hailstone function from previously, you pick a positive
integer n as the start. If n is even, divide it by 2. If n is
odd, multiply it by 3 and add 1. Repeat this process until n is 1.
Write a recursive version of hailstone that prints out the values of
the sequence and returns the number of steps.
def hailstone_iterative(n):
“””Print out the hailstone sequence starting at n, and return the
number of elements in the sequence.
>>> a = hailstone_iterative(10)
“*** YOUR CODE HERE ***”
def hailstone_recursive(n):
“””Print out the hailstone sequence starting at n, and return the
number of elements in the sequence.
>>> a = hailstone_recursive(10)
“*** YOUR CODE HERE ***”
Use OK to test your code:
python3 ok -q hailstone_iterative
python3 ok -q hailstone_recursive
Tree Recursion
Question 5: 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, coins, 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, coins):
“””Returns the number of ways to make change for amount.
>>> coins = [50, 25, 10, 5, 1]
>>> count_change(7, coins)
>>> count_change(100, coins)
>>> coins = [16, 8, 4, 2, 1]
>>> count_change(7, coins)
>>> count_change(10, coins)
>>> count_change(20, coins)
“*** YOUR CODE HERE ***”
Use OK to test your code:
python3 ok -q count_change
Make sure to submit this assignment by running:
python3 ok –submit
Question 1: Reduce
Question 2: Remove Last from Sequence
Question 3: Map
Question 4: Hailstone
Tree Recursion
Question 5: Count Change