Homework 5 Solutions
Solution Files
You can find the solutions in hw05.py.
Required Questions
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.
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
s[0]
in the product
or not:
- If we include
s[0]
, we cannot includes[1]
. - If we don't include
s[0]
, we can includes[1]
.
The recursive case is that we choose the larger of:
- multiplying
s[0]
by themax_product
ofs[2:]
(skippings[1]
) OR - just the
max_product
ofs[1:]
(skippings[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 themax_product
ofs[2:]
(skippings[1]
) OR - multiplying
s[1]
by themax_product
ofs[3:]
(skippings[0]
ands[2]
)
An expression for this recursive case is:
max(s[0] * max_product(s[2:]), s[1] * max_product(s[3:]))
Q2: 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 usings[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.