Due by 11:59pm on Friday, February 17
Submission: When you are done, submit the assignment by uploading all code files you've edited to Gradescope. 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 Gradescope. See Lab 0 for more instructions on submitting assignments.
Using Ok: If you have any questions about using Ok, please refer to this guide.
Readings: You might find the following references useful:
Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus. This homework is out of 2 points.
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
returns the number of times the digit 8 appears in
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 """ "*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q num_eights
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:
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
pingpongusing assignment statements and a
whilestatement. 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 """ "*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q pingpong
Q3: Count Coins
Given a positive integer
change, a set of coins makes change for
the sum of the values of the coins is
Here we will use standard US Coin values: 1, 5, 10, 25.
For example, the following sets make change for
- 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_coinwill return the next larger coin denomination from the input, i.e.
next_smaller_coinwill return the next smaller coin denomination from the input, i.e.
- Either function will return
Noneif 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
Important: Use recursion; the tests will fail if you use loops.
Hint: Refer the implementation of
count_partitionsfor 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 """ "*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q count_coins
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.
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.
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!