Homework 3 Solutions
Solution Files
You can find the solutions in hw03.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.
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 however use function definitions if you so wish.)
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(HW_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: Ping-pong
The ping-pong sequence counts up starting from 1 and is always either counting
up or counting down. At element k
, the direction switches if k
is a
multiple of 8 or contains the digit 8. The first 30 elements of the ping-pong
sequence are listed below, with direction swaps marked using brackets at the
8th, 16th, 18th, 24th, and 28th elements:
Index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | [8] | 9 | 10 | 11 | 12 | 13 | 14 | 15 | [16] | 17 | [18] | 19 | 20 | 21 | 22 | 23 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
PingPong Value | 1 | 2 | 3 | 4 | 5 | 6 | 7 | [8] | 7 | 6 | 5 | 4 | 3 | 2 | 1 | [0] | 1 | [2] | 1 | 0 | -1 | -2 | -3 |
Index (cont.) | [24] | 25 | 26 | 27 | [28] | 29 | 30 |
---|---|---|---|---|---|---|---|
PingPong Value | [-4] | -3 | -2 | -1 | [0] | -1 | -2 |
Implement a function pingpong
that returns the nth element of the ping-pong
sequence without using any assignment statements. (You are allowed to use function definitions.)
You may use the function num_eights
, which you defined in the previous question.
Important: Use recursion; the tests will fail if you use any assignment statements. (You can however use function definitions if you so wish.)
Hint: If you're stuck, first try implementing
pingpong
using assignment statements and awhile
statement. Then, to convert this into a recursive solution, write a helper function that has a parameter for each variable that changes values in the body of the while loop.Hint: There are a few pieces of information that we need to keep track of. One of these details is the direction that we're going (either increasing or decreasing). Building off of the hint above, think about how we can keep track of the direction throughout the calls to the helper function.
def pingpong(n):
"""Return the nth element of the ping-pong sequence.
>>> pingpong(8)
8
>>> pingpong(10)
6
>>> pingpong(15)
1
>>> pingpong(21)
-1
>>> pingpong(22)
-2
>>> pingpong(30)
-2
>>> pingpong(68)
0
>>> pingpong(69)
-1
>>> pingpong(80)
0
>>> pingpong(81)
1
>>> pingpong(82)
0
>>> pingpong(100)
-6
>>> from construct_check import check
>>> # ban assignment statements
>>> check(HW_SOURCE_FILE, 'pingpong',
... ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr'])
True
"""
def helper(result, i, step):
if i == n:
return result
elif i % 8 == 0 or num_eights(i) > 0:
return helper(result - step, i + 1, -step)
else:
return helper(result + step, i + 1, step)
return helper(1, 1, 1)
# Alternate solution 1
def pingpong_next(x, i, step):
if i == n:
return x
return pingpong_next(x + step, i + 1, next_dir(step, i+1))
def next_dir(step, i):
if i % 8 == 0 or num_eights(i) > 0:
return -step
return step
# Alternate solution 2
def pingpong_alt(n):
if n <= 8:
return n
return direction(n) + pingpong_alt(n-1)
def direction(n):
if n < 8:
return 1
if (n-1) % 8 == 0 or num_eights(n-1) > 0:
return -1 * direction(n-1)
return direction(n-1)
Use Ok to test your code:
python3 ok -q pingpong
This is a fairly involved recursion problem, which we will first solve through iteration and then convert to a recursive solution.
Note that at any given point in the sequence, we need to keep track of the current value of the sequence (this is the value that might be output) as well as the current index of the sequence (how many items we have seen so far, not actually output).
For example, 14th element has value 0, but it's the 14th index in
the sequence. We will refer to the value as x
and the index as i
. An
iterative solution may look something like this:
def pingpong(n):
i = 1
x = 1
while i < n:
x += 1
i += 1
return x
Hopefully, it is clear to you that this has a big problem. This doesn't
account for changes in directions at all! It will work for the first eight
values of the sequence, but then fail after that. To fix this, we can add
in a check for direction, and then also keep track of the current
direction to make our lives a bit easier (it's possible to compute the
direction from scratch at each step, see the direction
function in the
alternate solution).
def pingpong(n):
i = 1
x = 1
is_up = True
while i < n:
is_up = next_dir(...)
if is_up:
x += 1
else:
x -= 1
i += 1
return x
All that's left to do is to write the next_dir
function, which will take
in the current direction and index and then tell us what direction to
go in next (which could be the same direction):
def next_dir(is_up, i):
if i % 8 == 0 or num_eights(i) > 0:
return not is_up
return is_up
There's a tiny optimization we can make here. Instead of calculating an
increment based on the value of is_up
, we can make it directly store the
direction of change into the variable (next_dir
is also updated, see the
solution for the new version):
def pingpong(n):
i = 1
x = 1
step = 1
while i < n:
step = next_dir(step, i)
x += step
i += 1
return x
This will work, but it uses assignment. To convert it to an equivalent recursive version without assignment, make each local variable into a parameter of a new helper function, and then add an appropriate base case. Lastly, we seed the helper function with appropriate starting values by calling it with the values we had in the iterative version.
You should be able to convince yourself that the version of pingpong
in
the solutions has the same logic as the iterative version of pingpong
above.
Video walkthrough:
Q3: Count Coins
Given a positive integer change
, a set of coins makes change for change
if
the sum of the values of the coins is change
.
Here we will use standard US Coin values: 1, 5, 10, 25.
For example, the following sets make change for 15
:
- 15 1-cent coins
- 10 1-cent, 1 5-cent coins
- 5 1-cent, 2 5-cent coins
- 5 1-cent, 1 10-cent coins
- 3 5-cent coins
- 1 5-cent, 1 10-cent coin
Thus, there are 6 ways to make change for 15
. Write a recursive function
count_coins
that takes a positive integer change
and returns the number of
ways to make change for change
using coins.
You can use either of the functions given to you:
next_larger_coin
will return the next larger coin denomination from the input, i.e.next_larger_coin(5)
is10
.next_smaller_coin
will return the next smaller coin denomination from the input, i.e.next_smaller_coin(5)
is1
.- Either function will return
None
if the next coin value does not exist
There are two main ways in which you can approach this problem.
One way uses next_larger_coin
, and another uses next_smaller_coin
.
Important: Use recursion; the tests will fail if you use loops.
Hint: Refer 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_larger_coin(coin):
"""Returns the next larger coin in order.
>>> next_larger_coin(1)
5
>>> next_larger_coin(5)
10
>>> next_larger_coin(10)
25
>>> next_larger_coin(2) # Other values return None
"""
if coin == 1:
return 5
elif coin == 5:
return 10
elif coin == 10:
return 25
def next_smaller_coin(coin):
"""Returns the next smaller coin in order.
>>> next_smaller_coin(25)
10
>>> next_smaller_coin(10)
5
>>> next_smaller_coin(5)
1
>>> next_smaller_coin(2) # Other values return None
"""
if coin == 25:
return 10
elif coin == 10:
return 5
elif coin == 5:
return 1
def count_coins(change):
"""Return the number of ways to make change using coins of value of 1, 5, 10, 25.
>>> count_coins(15)
6
>>> count_coins(10)
4
>>> count_coins(20)
9
>>> count_coins(100) # How many ways to make change for a dollar?
242
>>> count_coins(200)
1463
>>> from construct_check import check
>>> # ban iteration
>>> check(HW_SOURCE_FILE, 'count_coins', ['While', 'For'])
True
"""
def constrained_count(change, smallest_coin):
if change == 0:
return 1
if change < 0:
return 0
if smallest_coin == None:
return 0
without_coin = constrained_count(change, next_larger_coin(smallest_coin))
with_coin = constrained_count(change - smallest_coin, smallest_coin)
return without_coin + with_coin
return constrained_count(change, 1)
# Alternate solution: using next_smaller_coin
def constrained_count_small(change, largest_coin):
if change == 0:
return 1
if change < 0:
return 0
if largest_coin == None:
return 0
without_coin = constrained_count_small(change, next_smaller_coin(largest_coin))
with_coin = constrained_count_small(change - largest_coin, largest_coin)
return without_coin + with_coin
return constrained_count_small(change, 25)
Use Ok to test your code:
python3 ok -q count_coins
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 and also create another helper function to find the max coin.
- Partition size is not linear. To get the next partition you need to call
next_larger_coin
if you are counting up (i.e. from the smallest coin to the largest coin), ornext_smaller_coin
if you are counting down.
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
Make sure to submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. For a refresher on how to do this, refer to Lab 00.
Exam Practice
Homework assignments will also contain prior exam-level questions for you to take a look at. These questions have no submission component; feel free to attempt them if you'd like a challenge!
- Fall 2017 MT1 Q4a: Digital
- Summer 2018 MT1 Q5a: Won't You Be My Neighbor?
- Fall 2019 Final Q6b: Palindromes