Solution Files

You can find the solutions in hw03.py.

Required Questions

Q1: Num eights

Write a recursive function num_eights that takes a positive integer pos and returns the number of times the digit 8 appears in pos.

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(pos):
    """Returns the number of times 8 appears as a digit of pos.

    >>> 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
    """
    if pos % 10 == 8:
        return 1 + num_eights(pos // 10)
    elif pos < 10:
        return 0
    else:
        return num_eights(pos // 10)

Use Ok to test your code:

python3 ok -q num_eights
Copy
✂️

total = 0
while pos > 0:
    if pos % 10 == 8:
        total = total + 1
    pos = pos // 10
return total

Q2: Ping-pong

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 pingpong using assignment statements and a while statement. 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
    """
    def helper(result, i, step):
        if i == n:
            return result
        elif i % 8 == 0 or num_eights(i) > 0:
            return helper(result - step, i + 1, -step)
        else:
            return helper(result + step, i + 1, step)
    return helper(1, 1, 1)

# Alternate solution 1
def pingpong_next(x, i, step):
    if i == n:
        return x
    return pingpong_next(x + step, i + 1, next_dir(step, i+1))

def next_dir(step, i):
    if i % 8 == 0 or num_eights(i) > 0:
        return -step
    return step

# Alternate solution 2
def pingpong_alt(n):
    if n <= 8:
        return n
    return direction(n) + pingpong_alt(n-1)

def direction(n):
    if n < 8:
        return 1
    if (n-1) % 8 == 0 or num_eights(n-1) > 0:
        return -1 * direction(n-1)
    return direction(n-1)

Use Ok to test your code:

python3 ok -q pingpong
Copy
✂️

def pingpong(n):
    i = 1
    x = 1
    while i < n:
        x += 1
        i += 1
    return x

def pingpong(n):
    i = 1
    x = 1
    is_up = True
    while i < n:
        is_up = next_dir(...)
        if is_up:
            x += 1
        else:
            x -= 1
        i += 1
    return x

def next_dir(is_up, i):
    if i % 8 == 0 or num_eights(i) > 0:
        return not is_up
    return is_up

def pingpong(n):
    i = 1
    x = 1
    step = 1
    while i < n:
        step = next_dir(step, i)
        x += step
        i += 1
    return x

Q3: Count coins

Given a positive integer change, a set of coins makes change for change if the sum of the values of the coins is change. 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 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_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.

Important: Use recursion; the tests will fail if you use loops.

Hint: Refer 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(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
    """
    def constrained_count(change, smallest_coin):
        if change == 0:
            return 1
        if change < 0:
            return 0
        if smallest_coin == None:
            return 0
        without_coin = constrained_count(change, next_larger_coin(smallest_coin))
        with_coin = constrained_count(change - smallest_coin, smallest_coin)
        return without_coin + with_coin
    return constrained_count(change, 1)

    # Alternate solution: using next_smaller_coin
    def constrained_count_small(change, largest_coin):
        if change == 0:
            return 1
        if change < 0:
            return 0
        if largest_coin == None:
            return 0
        without_coin = constrained_count_small(change, next_smaller_coin(largest_coin))
        with_coin = constrained_count_small(change - largest_coin, largest_coin)
        return without_coin + with_coin
    return constrained_count_small(change, 25)

Use Ok to test your code:

python3 ok -q count_coins
Copy
✂️

Submit

Make sure to submit this assignment by running:

python3 ok --submit

Optional Contest

The following question is not worth any credit and is not a recursion problem. Instead, it is an optional fun contest that requires only knowledge of Midterm 1 concepts.

Q4: Busy Beaver Contest

The A+ question on the midterm discussed the concept of a Busy Beaver function, which is a function of a given length that tries to output as much as possible. During this question, starter code was provided to write a Beaver that ran f 64 times. In this question, you'll be able to write your own Busy Beaver function, and compete for the best Busy Beaver in the Busy Beaver contest! The rules for this contest are as follows:

Write a function beaver(f) that takes in a function f, and runs it as many times as possible. f is a function that takes in 0 inputs, and outputs None.

• Your code must be exactly one line long, and less than 100 characters long (not including trailing or leading whitespace)
• You may not use any numbers or strings, or any argument that evaluates to a number/string. This includes things like int('1000'), as this evaluates to a number and contains a string.
• Your code must terminate (without crashing) in finite time.
• You may not import any functions, but may use built-in functions that do not need to be imported.
• You may not use semicolons.

There are two categories for this contest. For both categories, please adhere to the conditions outlined above.

• For the first category, your solution should call f at least 1000 times. The goal of this category is to have a minimal-length line of code. That means, as long as your solution calls f at least 1000 times, the only thing that matters is how short your solution is.

  • For this category, please write your code in hw03.py and run python3 ok --submit as usual to submit your solution. We will release rankings after all submissions have been processed.
  • If you would like to remain anonymous on the leaderboard, set the anonymous variable above the definition for beaver to True.
  • Run the syntax checker (python3 ok -q beaver_syntax_test) to make sure your solution is one line. Run python3 ok -q beaver_run_test to check that your solution runs at least 1000 times.

• For the second category, your solution should call f as many times as possible, as long as your solution stays below the 100 character limit. Submit your solution, along with how many times you expect your solution to call f, to this Google form.

  • For this category, you may assume that your code gets run on an ideal system with no memory or stack frame limits (so you may exceed the maximum recursion depth normally available in Python).

The deadline for the contest submission is the same as the rest of the homework, Thursday, September 22, 11:59pm.

anonymous = False # Change to True if you would like to remain anonymous on the final leaderboard.
def beaver(f):
    # Shortest solution (73 characters)
    (lambda g: g(g(g(g(g(g(g(f))))))))(lambda f: lambda: f() or f() or f())()

Use Ok to test your code:

python3 ok -q beaver_syntax_check
python3 ok -q beaver_run_test
Copy
✂️

Exam Practice

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!

1. Fall 2017 MT1 Q4a: Digital
2. Summer 2018 MT1 Q5a: Won't You Be My Neighbor?
3. Fall 2019 Final Q6b: Palindromes