Homework 6 Solutions

hw06.zip

Solution Files

You can find the solutions in hw06.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: Max Product

Implement max_product, which takes a list of numbers and returns the maximum product that can be formed by multiplying together non-consecutive elements of the list. Assume that all numbers in the input list are greater than or equal to 1.

First try multiplying the first element by the max_product of everything after the first two elements (skipping the second element because it is consecutive with the first), then try skipping the first element and finding the max_product of the rest. To find which of these options is better, use max.

def max_product(s):
    """Return the maximum product of non-consecutive elements of s.

    >>> max_product([10, 3, 1, 9, 2])   # 10 * 9
    90
    >>> max_product([5, 10, 5, 10, 5])  # 5 * 5 * 5
    125
    >>> max_product([])                 # The product of no numbers is 1
    1
    """
    if s == []:
        return 1
    if len(s) == 1:
        return s[0]
    else:
        return max(s[0] * max_product(s[2:]), max_product(s[1:]))
        # OR
        return max(s[0] * max_product(s[2:]), s[1] * max_product(s[3:]))

Use Ok to test your code:

python3 ok -q max_product

This solution begins with the idea that we either include s[0] in the product or not:

If we include s[0], we cannot include s[1].
If we don't include s[0], we can include s[1].

The recursive case is that we choose the larger of:

multiplying s[0] by the max_product of s[2:] (skipping s[1]) OR
just the max_product of s[1:] (skipping s[0])

Here are some key ideas in translating this into code:

The built-in max function can find the larger of two numbers, which in this case come from two recursive calls.
In every case, max_product is called on a list of numbers and its return value is treated as a number.

An expression for this recursive case is:

max(s[0] * max_product(s[2:]), max_product(s[1:]))

Since this expression never refers to s[1], and s[2:] evaluates to the empty list even for a one-element list s, the second base case (len(s) == 1) can be omitted if this recursive case is used.

The recursive solution above explores some options that we know in advance will not be the maximum, such as skipping both s[0] and s[1]. Alternatively, the recursive case could be that we choose the larger of:

multiplying s[0] by the max_product of s[2:] (skipping s[1]) OR
multiplying s[1] by the max_product of s[3:] (skipping s[0] and s[2])

An expression for this recursive case is:

max(s[0] * max_product(s[2:]), s[1] * max_product(s[3:]))

Q2: Count Coins

Given a positive integer total, a set of coins makes change for total if the sum of the values of the coins is total. 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 total and returns the number of ways to make change for total 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) is 10.
next_smaller_coin will return the next smaller coin denomination from the input, i.e. next_smaller_coin(5) is 1.
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. It is up to you which one you want to use!

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_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(total):
    """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(SOURCE_FILE, 'count_coins', ['While', 'For'])
    True
    """
    def constrained_count(total, smallest_coin):
        if total == 0:
            return 1
        if total < 0:
            return 0
        if smallest_coin == None:
            return 0
        without_coin = constrained_count(total, next_larger_coin(smallest_coin))
        with_coin = constrained_count(total - smallest_coin, smallest_coin)
        return without_coin + with_coin
    return constrained_count(total, 1)

    # Alternate solution: using next_smaller_coin
    def constrained_count_small(total, largest_coin):
        if total == 0:
            return 1
        if total < 0:
            return 0
        if largest_coin == None:
            return 0
        without_coin = constrained_count_small(total, next_smaller_coin(largest_coin))
        with_coin = constrained_count_small(total - largest_coin, largest_coin)
        return without_coin + with_coin
    return constrained_count_small(total, 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), or next_smaller_coin if you are counting down.

Q3: Super Mario

Mario needs to jump over a sequence of Piranha plants called level. level is represented as a string of empty spaces (' '), indicating no plant, and P's ('P'), indicating the presence of a plant. Mario only moves forward and can either step (move forward one spot) or jump (move forward two spots) from each position. How many different ways can Mario traverse a level without stepping or jumping into a Piranha plant ('P')? Assume that every level begins with an empty space (' '), where Mario starts, and ends with an empty space (' '), where Mario must end up.

Hint: You can access the ith character in a string s by using s[i]. For example:
>>> s = 'abcdefg'
>>> s[0]
'a'
>>> s[2]
'c'
Hint: You can find the total number of characters in a string using the built-in len function:
>>> s = 'abcdefg'
>>> len(s)
7
>>> len('')
0

def mario_number(level):
    """Return the number of ways that Mario can perform a sequence of steps
    or jumps to reach the end of the level without ever landing in a Piranha
    plant. Assume that every level begins and ends with a space.

    >>> mario_number(' P P ')   # jump, jump
    1
    >>> mario_number(' P P  ')   # jump, jump, step
    1
    >>> mario_number('  P P ')  # step, jump, jump
    1
    >>> mario_number('   P P ') # step, step, jump, jump or jump, jump, jump
    2
    >>> mario_number(' P PP ')  # Mario cannot jump two plants
    0
    >>> mario_number('    ')    # step, jump ; jump, step ; step, step, step
    3
    >>> mario_number('    P    ')
    9
    >>> mario_number('   P    P P   P  P P    P     P ')
    180
    """
    def ways(n):
        if n == len(level)-1:
            return 1
        if n >= len(level) or level[n] == 'P':
            return 0
        return ways(n+1) + ways(n+2)
    return ways(0)

Use Ok to test your code:

python3 ok -q mario_number

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.