Due by 11:59pm on Tuesday, July 2.

Starter Files

Download lab03.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.

Topics

Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

def virfib(n):
    if n == 0 or n == 1:
        return n
    return virfib(n - 1) + virfib(n - 2)

Required Questions

Recursion

Q1: Double Eights

Write a recursive function that takes in a positive integer n and determines if its digits contain two adjacent 8s (that is, two 8s right next to each other). Do not use for or while.

Hint: Start by coming up with a recursive plan: the digits of a number have double eights if either (think of something that is straightforward to check) or double eights appear in the rest of the digits.

def double_eights(n):
    """ Returns whether or not n has two digits in row that
    are the number 8. Assume n has at least two digits in it.

    >>> double_eights(1288)
    True
    >>> double_eights(880)
    True
    >>> double_eights(538835)
    True
    >>> double_eights(284682)
    False
    >>> double_eights(588138)
    True
    >>> double_eights(78)
    False
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(LAB_SOURCE_FILE, 'double_eights', ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q double_eights
Copy
✂️

Q2: Making Onions

Write a function make_onion that takes in two one-argument functions, f and g. It returns a function that takes in three arguments: x, y, and limit. The returned function returns True if it is possible to reach y from x using up to limit calls to f and g, and False otherwise.

For example, if f adds 1 and g doubles, then it is possible to reach 25 from 5 in four calls: f(g(g(f(5)))).

def make_onion(f, g):
    """Return a function can_reach(x, y, limit) that returns
    whether some call expression containing only f, g, and x with
    up to limit calls will give the result y.

    >>> up = lambda x: x + 1
    >>> double = lambda y: y * 2
    >>> can_reach = make_onion(up, double)
    >>> can_reach(5, 25, 4)      # 25 = up(double(double(up(5))))
    True
    >>> can_reach(5, 25, 3)      # Not possible
    False
    >>> can_reach(1, 1, 0)      # 1 = 1
    True
    >>> add_ing = lambda x: x + "ing"
    >>> add_end = lambda y: y + "end"
    >>> can_reach_string = make_onion(add_ing, add_end)
    >>> can_reach_string("cry", "crying", 1)      # "crying" = add_ing("cry")
    True
    >>> can_reach_string("un", "unending", 3)     # "unending" = add_ing(add_end("un"))
    True
    >>> can_reach_string("peach", "folding", 4)   # Not possible
    False
    """
    def can_reach(x, y, limit):
        if limit < 0:
            return ____
        elif x == y:
            return ____
        else:
            return can_reach(____, ____, limit - 1) or can_reach(____, ____, limit - 1)
    return can_reach

Use Ok to test your code:

python3 ok -q make_onion
Copy
✂️

Tree Recursion

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
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q mario_number
Copy
✂️

Q4: Maximum Subsequence

A subsequence of a number is a series of digits from the number (not necessarily contiguous). For example, 12345 has subsequences like 123, 234, 124, 245, etc. Your task is to find the largest subsequence that is under a specified length.

Hint: To add a digit (d) to an existing number (n), calculate: n * 10 + d. For instance, to add 8 to 15 to get 158, compute 15 * 10 + 8.

def max_subseq(n, t):
    """
    Return the maximum subsequence of length at most t that can be found in the given number n.
    For example, for n = 2012 and t = 2, we have that the subsequences are
        2
        0
        1
        2
        20
        21
        22
        01
        02
        12
    and of these, the maxumum number is 22, so our answer is 22.

    >>> max_subseq(2012, 2)
    22
    >>> max_subseq(20125, 3)
    225
    >>> max_subseq(20125, 5)
    20125
    >>> max_subseq(20125, 6) # note that 20125 == 020125
    20125
    >>> max_subseq(12345, 3)
    345
    >>> max_subseq(12345, 0) # 0 is of length 0
    0
    >>> max_subseq(12345, 1)
    5
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q max_subseq
Copy
✂️

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.

In addition, all students who are not in the mega lab must submit the attendance form for credit. Ask your section TA for the link! Submit this form for each section, whether you attended lab or missed it for a good reason. The attendance form is not required for mega section students.

Optional Questions

Q5: Recursive Prime

Below is the iterative version of is_prime, which returns True if positive integer n is a prime number and False otherwise:

def is_prime(n):
    if n == 1:
        return False
    k = 2
    while k < n:
        if n % k == 0:
            return False
        k += 1
    return True

Implement the recursive is_prime function. Do not use a while loop, use recursion. As a reminder, an integer is considered prime if it has exactly two unique factors: 1 and itself.

def is_prime(n):
    """
    >>> is_prime(7)
    True
    >>> is_prime(10)
    False
    >>> is_prime(1)
    False
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q is_prime
Copy
✂️