Homework 2 Solutions
Solution Files
You can find solutions for all questions in hw02.py.
Required Questions
Getting Started Videos
These videos may provide some helpful direction for tackling the coding problems on this assignment.
To see these videos, you should be logged into your berkeley.edu email.
Recursion
Q1: Num Eights
Write a recursive function num_eights
that takes a positive integer n
and
returns the number of times the digit 8 appears in n
.
Important: Use recursion; the tests will fail if you use any assignment statements or loops. (You can define new functions, but don't put assignment statements there either.)
def num_eights(n):
"""Returns the number of times 8 appears as a digit of n.
>>> num_eights(3)
0
>>> num_eights(8)
1
>>> num_eights(88888888)
8
>>> num_eights(2638)
1
>>> num_eights(86380)
2
>>> num_eights(12345)
0
>>> num_eights(8782089)
3
>>> from construct_check import check
>>> # ban all assignment statements
>>> check(SOURCE_FILE, 'num_eights',
... ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr', 'For', 'While'])
True
"""
if n % 10 == 8:
return 1 + num_eights(n // 10)
elif n < 10:
return 0
else:
return num_eights(n // 10)
Use Ok to test your code:
python3 ok -q num_eights
The equivalent iterative version of this problem might look something like this:
total = 0
while n > 0:
if n % 10 == 8:
total = total + 1
n = n // 10
return total
The main idea is that we check each digit for a eight. The recursive solution is similar, except that you depend on the recursive call to count the occurences of eight in the rest of the number. Then, you add that to the number of eights you see in the current digit.
Q2: Interleaved Sum
Write a function interleaved_sum
, which takes in a number n
and
two one-argument functions: f_odd
and f_even
. It returns the sum of applying f_odd
to every odd number and f_even
to every even number from 1 to n
inclusive.
For example, executing interleaved_sum(5, lambda x: x, lambda x: x * x)
returns 1 + 2*2 + 3 + 4*4 + 5 = 29
.
Important: Implement this function without using any loops or directly testing if a number is odd or even (no using
%
). Instead of directly checking whether a number is even or odd, start with 1, which you know is an odd number.Hint: Introduce an inner helper function that takes an odd number
k
and computes an interleaved sum fromk
ton
(includingn
). Alternatively, you can use mutual recursion.
def interleaved_sum(n, f_odd, f_even):
"""Compute the sum f_odd(1) + f_even(2) + f_odd(3) + ..., up
to n.
>>> identity = lambda x: x
>>> square = lambda x: x * x
>>> triple = lambda x: x * 3
>>> interleaved_sum(5, identity, square) # 1 + 2*2 + 3 + 4*4 + 5
29
>>> interleaved_sum(5, square, identity) # 1*1 + 2 + 3*3 + 4 + 5*5
41
>>> interleaved_sum(4, triple, square) # 1*3 + 2*2 + 3*3 + 4*4
32
>>> interleaved_sum(4, square, triple) # 1*1 + 2*3 + 3*3 + 4*3
28
>>> from construct_check import check
>>> check(SOURCE_FILE, 'interleaved_sum', ['While', 'For', 'Mod']) # ban loops and %
True
>>> check(SOURCE_FILE, 'interleaved_sum', ['BitAnd', 'BitOr', 'BitXor']) # ban bitwise operators, don't worry about these if you don't know what they are
True
"""
def sum_from(k):
if k > n:
return 0
elif k == n:
return f_odd(k)
else:
return f_odd(k) + f_even(k+1) + sum_from(k + 2)
return sum_from(1)
Use Ok to test your code:
python3 ok -q interleaved_sum
Q3: Count Dollars
Given a positive integer total
, a set of dollar bills makes change for total
if
the sum of the values of the dollar bills is total
.
Here we will use standard US dollar bill values: 1, 5, 10, 20, 50, and 100.
For example, the following sets make change for 15
:
- 15 1-dollar bills
- 10 1-dollar, 1 5-dollar bills
- 5 1-dollar, 2 5-dollar bills
- 5 1-dollar, 1 10-dollar bills
- 3 5-dollar bills
- 1 5-dollar, 1 10-dollar bills
Thus, there are 6 ways to make change for 15
. Write a recursive function
count_dollars
that takes a positive integer total
and returns the number of
ways to make change for total
using 1, 5, 10, 20, 50, and 100 dollar bills.
Use next_smaller_dollar
in your solution:
next_smaller_dollar
will return the next smaller dollar bill value from the
input (e.g. next_smaller_dollar(5)
is 1
).
The function will return None
if the next dollar bill value does not exist.
Important: Use recursion; the tests will fail if you use loops.
Hint: Refer to the implementation of
count_partitions
for an example of how to count the ways to sum up to a final value with smaller parts. If you need to keep track of more than one value across recursive calls, consider writing a helper function.
def next_smaller_dollar(bill):
"""Returns the next smaller bill in order."""
if bill == 100:
return 50
if bill == 50:
return 20
if bill == 20:
return 10
elif bill == 10:
return 5
elif bill == 5:
return 1
def count_dollars(total):
"""Return the number of ways to make change.
>>> count_dollars(15) # 15 $1 bills, 10 $1 & 1 $5 bills, ... 1 $5 & 1 $10 bills
6
>>> count_dollars(10) # 10 $1 bills, 5 $1 & 1 $5 bills, 2 $5 bills, 10 $1 bills
4
>>> count_dollars(20) # 20 $1 bills, 15 $1 & $5 bills, ... 1 $20 bill
10
>>> count_dollars(45) # How many ways to make change for 45 dollars?
44
>>> count_dollars(100) # How many ways to make change for 100 dollars?
344
>>> count_dollars(200) # How many ways to make change for 200 dollars?
3274
>>> from construct_check import check
>>> # ban iteration
>>> check(SOURCE_FILE, 'count_dollars', ['While', 'For'])
True
"""
def constrained_count(total, largest_bill):
if total == 0:
return 1
if total < 0:
return 0
if largest_bill == None:
return 0
without_dollar_bill = constrained_count(total, next_smaller_dollar(largest_bill))
with_dollar_bill = constrained_count(total - largest_bill, largest_bill)
return without_dollar_bill + with_dollar_bill
return constrained_count(total, 100)
Use Ok to test your code:
python3 ok -q count_dollars
This is remarkably similar to the count_partitions
problem, with a
few minor differences:
- A maximum partition size is not given, so we need to create a helper function that takes in two arguments: current total and dollar bill value.
- Partition size is not linear. To get the next partition you need to call
next_smaller_dollar
.
Sequences and Python Lists
Q4: Shuffle
Implement shuffle
, which takes a sequence s
(such as a list or range) with
an even number of elements. It returns a new list that interleaves the
elements of the first half of s
with the elements of the second half.
To interleave two sequences s0
and s1
is to create a new list containing
the first element of s0
, the first element of s1
, the second element of
s0
, the second element of s1
, and so on. For example, if s = [1, 2, 3, 4, 5, 6]
then s0 = [1, 2, 3]
and s1 = [4, 5, 6]
, and interleaving s0
and s1
would result in
[1, 4, 2, 5, 3, 6]
.
Challenge: Try to implement
shuffle
in less lines using a list comprehension!
def shuffle(s):
"""Return a shuffled list that interleaves the two halves of s.
>>> shuffle(range(6))
[0, 3, 1, 4, 2, 5]
>>> letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
>>> shuffle(letters)
['a', 'e', 'b', 'f', 'c', 'g', 'd', 'h']
>>> shuffle(shuffle(letters))
['a', 'c', 'e', 'g', 'b', 'd', 'f', 'h']
>>> letters # Original list should not be modified
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
"""
assert len(s) % 2 == 0, 'len(seq) must be even'
half = len(s) // 2
shuffled = []
for i in range(half):
shuffled = shuffled + [s[i]]
shuffled = shuffled + [s[half + i]]
return shuffled
# Alternative List Comprehension Solution
half = len(s) // 2
return [x for i in range(half) for x in (s[i], s[half + i])]
Use Ok to test your code:
python3 ok -q shuffle
Q5: Merge
Implement merge
, which takes 2 sorted lists of numbers s
and t
in ascending order. It returns a new list that contains all the elements from both s
and t
in sorted order. Do not remove duplicates; the length of the returned list should be len(s) + len(t)
. Use only recursion; while
or for
loops are not allowed.
def merge(s, t):
"""Merges two sorted lists.
>>> s1 = [1, 3, 5]
>>> s2 = [2, 4, 6]
>>> merge(s1, s2)
[1, 2, 3, 4, 5, 6]
>>> s1
[1, 3, 5]
>>> s2
[2, 4, 6]
>>> merge([], [2, 4, 6])
[2, 4, 6]
>>> merge([1, 2, 3], [])
[1, 2, 3]
>>> merge([5, 7], [2, 4, 6])
[2, 4, 5, 6, 7]
>>> merge([2, 3, 4], [2, 4, 6])
[2, 2, 3, 4, 4, 6]
>>> from construct_check import check
>>> check(SOURCE_FILE, 'merge', ['While', 'For']) # ban iteration
True
"""
# Recursive Solution
if not s or not t:
return s + t
elif s[0] < t[0]:
return [s[0]] + merge(s[1:], t)
else:
return [t[0]] + merge(s, t[1:])
# Alternative Recursive Solution
if not s or not t:
return s + t
elif s[0] <= t[0]:
return [s[0]] + merge(s[1:], t)
else:
return merge(t, s)
# For the last line, instead of concatenating [t[0]] at the front like we did for the first solution,
# we instead call merge again with the arguments switched, so that in the next call to merge, s
# is now t, and t is s.
# Note that in order for this to work successfully, we have to modify the elif case to have <= rather
# than just <, otherwise we run into infinite recursion. (Try out the last doctest to see why)
Use Ok to test your code:
python3 ok -q merge
Check Your Score Locally
You can locally check your score on each question of this assignment by running
python3 ok --score
This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.
Submit Assignment
Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.
[Optional] Exam Practice
Here are some related questions from past exams for you to try. These are optional. There is no way to submit them.
- Fall 2021 MT2 Q2: Doctor Change [Recursion]
- Spring 2021 MT1 Q7: Measure Twice, Cup Once [Tree Recursion]