# Homework 5 Solutions

## Solution Files

You can find the solutions in hw05.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.

Coming soon!

### Q1: 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(HW_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`

.

## 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 Questions

These questions are optional. If you don't complete them, you will still receive credit for this assignment. They are great practice, so do them anyway!

### Q2: Count Dollars Upward

Write a **recursive** function `count_dollars_upward`

that is just like `count_dollars`

except it uses `next_larger_dollar`

, which returns the next larger dollar bill value from the
input (e.g. `next_larger_dollar(5)`

is `10`

).
*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.

```
def next_larger_dollar(bill):
"""Returns the next larger bill in order."""
if bill == 1:
return 5
elif bill == 5:
return 10
elif bill == 10:
return 20
elif bill == 20:
return 50
elif bill == 50:
return 100
def count_dollars_upward(total):
"""Return the number of ways to make change using bills.
>>> count_dollars_upward(15) # 15 $1 bills, 10 $1 & 1 $5 bills, ... 1 $5 & 1 $10 bills
6
>>> count_dollars_upward(10) # 10 $1 bills, 5 $1 & 1 $5 bills, 2 $5 bills, 10 $1 bills
4
>>> count_dollars_upward(20) # 20 $1 bills, 15 $1 & $5 bills, ... 1 $20 bill
10
>>> count_dollars_upward(45) # How many ways to make change for 45 dollars?
44
>>> count_dollars_upward(100) # How many ways to make change for 100 dollars?
344
>>> count_dollars_upward(200) # How many ways to make change for 200 dollars?
3274
>>> from construct_check import check
>>> # ban iteration
>>> check(HW_SOURCE_FILE, 'count_dollars_upward', ['While', 'For'])
True
"""
def constrained_count(total, smallest_bill):
if total == 0:
return 1
if total < 0:
return 0
if smallest_bill == None:
return 0
without_dollar_bill = constrained_count(total, next_larger_dollar(smallest_bill))
with_dollar_bill = constrained_count(total - smallest_bill, smallest_bill)
return without_dollar_bill + with_dollar_bill
return constrained_count(total, 1)
```

Use Ok to test your code:

`python3 ok -q count_dollars_upward`

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_larger_dollar`

.