Homework 2 Solutions

Solution Files

You can find solutions for all questions in hw02.py.

Required Questions

Recursion

Q1: Num Eights

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

Important: Use recursion; the tests will fail if you use any assignment statements or loops. (You can define new functions, but don't put assignment statements there either.)

def num_eights(num: int) -> int:
    """Returns the number of times 8 appears as a digit of num.

    >>> 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(SOURCE_FILE, 'num_eights',
    ...       ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr', 'For', 'While'])
    True
    """

    if num % 10 == 8:
        return 1 + num_eights(num // 10)
    elif num < 10:
        return 0
    else:
        return num_eights(num // 10)

Use Ok to test your code:

python3 ok -q num_eights

The equivalent iterative version of this problem might look something like this:

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

The main idea is that we check each digit for a eight. The recursive solution is similar, except that you depend on the recursive call to count the occurences of eight in the rest of the number. Then, you add that to the number of eights you see in the current digit.

Q2: Digit Distance

For a given integer, the digit distance is the sum of the absolute differences between consecutive digits. For example:

  • The digit distance of 61 is 5, as the absolute value of 6 - 1 is 5.
  • The digit distance of 71253 is 12 (abs(7-1) + abs(1-2) + abs(2-5) + abs(5-3) = 6 + 1 + 3 + 2).
  • The digit distance of 6 is 0 because there are no pairs of consecutive digits.

Write a function that determines the digit distance of a positive integer. You must use recursion or the tests will fail.

def digit_distance(num: int) -> int:
    """Determines the digit distance of num.

    >>> digit_distance(3)
    0
    >>> digit_distance(777) # 0 + 0
    0
    >>> digit_distance(314) # 2 + 3
    5
    >>> digit_distance(31415926535) # 2 + 3 + 3 + 4 + ... + 2
    32
    >>> digit_distance(3464660003)  # 1 + 2 + 2 + 2 + ... + 3
    16
    >>> from construct_check import check
    >>> # ban all loops
    >>> check(SOURCE_FILE, 'digit_distance',
    ...       ['For', 'While'])
    True
    """

    if num < 10:
        return 0
    return abs(num % 10 - (num // 10) % 10) + digit_distance(num // 10)

# Alternate solution 1
def digit_distance_alt(num):
    def helper(prev, num):
        if num == 0:
            return 0
        dist = abs(prev - num % 10)
        return dist + helper(num % 10, num // 10)
    return helper(num % 10, num // 10)

# Alternate solution 2
def digit_distance_alt_2(num):
    def helper(dist, prev, num):
        if num == 0:
            return dist
        dist += abs(prev - num % 10)
        prev = num % 10
        num //= 10
        return helper(dist, prev, num)
    return helper(0, num % 10, num // 10)

Use Ok to test your code:

python3 ok -q digit_distance

Q3: Interleaved Sum

Write a function interleaved_sum, which takes in a number num and two one-argument functions: f_odd and f_even. It returns the sum of applying f_odd to every odd number and f_even to every even number from 1 to num inclusive.

For example, executing interleaved_sum(5, lambda x: x, lambda x: x * x) returns 1 + 2*2 + 3 + 4*4 + 5 = 29.

Important: Implement this function without using any loops or directly testing if a number is odd or even (no using %). Instead of directly checking whether a number is even or odd, start with 1, which you know is an odd number.

Hint: Introduce an inner helper function that takes an odd number k and computes an interleaved sum from k to num (including num). Alternatively, you can use mutual recursion.

def interleaved_sum(num: int, f_odd, f_even) -> int:
    """Compute the sum f_odd(1) + f_even(2) + f_odd(3) + ..., up
    to num.

    >>> identity = lambda x: x
    >>> square = lambda x: x * x
    >>> triple = lambda x: x * 3
    >>> interleaved_sum(5, identity, square) # 1   + 2*2 + 3   + 4*4 + 5
    29
    >>> interleaved_sum(5, square, identity) # 1*1 + 2   + 3*3 + 4   + 5*5
    41
    >>> interleaved_sum(4, triple, square)   # 1*3 + 2*2 + 3*3 + 4*4
    32
    >>> interleaved_sum(4, square, triple)   # 1*1 + 2*3 + 3*3 + 4*3
    28
    >>> from construct_check import check
    >>> check(SOURCE_FILE, 'interleaved_sum', ['While', 'For', 'Mod']) # ban loops and %
    True
    >>> check(SOURCE_FILE, 'interleaved_sum', ['BitAnd', 'BitOr', 'BitXor']) # ban bitwise operators, don't worry about these if you don't know what they are
    True
    """

    def sum_from(k):
        if k > num:
            return 0
        elif k == num:
            return f_odd(k)
        else:
            return f_odd(k) + f_even(k+1) + sum_from(k + 2)
    return sum_from(1)

Use Ok to test your code:

python3 ok -q interleaved_sum

Tree Recursion

Q4: Count Dollars

Given a positive integer sum_needed, a set of dollar bills makes change for sum_needed if the sum of the values of the dollar bills is sum_needed. 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 sum_needed and returns the number of ways to make change for sum_needed 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: int) -> int:
    """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(sum_needed: int) -> int:
    """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(SOURCE_FILE, 'count_dollars', ['While', 'For'])
    True
    """

    def constrained_count(sum_needed, largest_bill):
        if sum_needed == 0:
            return 1
        if sum_needed < 0:
            return 0
        if largest_bill == None:
            return 0
        without_dollar_bill = constrained_count(sum_needed, next_smaller_dollar(largest_bill))
        with_dollar_bill = constrained_count(sum_needed - largest_bill, largest_bill)
        return without_dollar_bill + with_dollar_bill
    return constrained_count(sum_needed, 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 sum needed and dollar bill value.
  • Partition size is not linear. To get the next partition you need to call next_smaller_dollar.

Sequences

Q5: Shuffle

Implement shuffle, which takes a sequence s (such as a list or range) with an even number of elements. It returns a new list that interleaves the elements of the first half of s with the elements of the second half. It does not modify s.

To interleave two sequences s0 and s1 is to create a new list containing the first element of s0, the first element of s1, the second element of s0, the second element of s1, and so on. For example, if s = [1, 2, 3, 4, 5, 6] then the first half is s0 = [1, 2, 3] and the second half is s1 = [4, 5, 6], and interleaving s0 and s1 would result in [1, 4, 2, 5, 3, 6].

def shuffle(s: list) -> list:
    """Return a shuffled list that interleaves the two halves of s.

    >>> shuffle(range(6))
    [0, 3, 1, 4, 2, 5]
    >>> letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
    >>> shuffle(letters)
    ['a', 'e', 'b', 'f', 'c', 'g', 'd', 'h']
    >>> shuffle(shuffle(letters))
    ['a', 'c', 'e', 'g', 'b', 'd', 'f', 'h']
    >>> letters  # Original list should not be modified
    ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
    """
    assert len(s) % 2 == 0, 'len(seq) must be even'

    half = len(s) // 2
    shuffled = []
    for i in range(half):
        shuffled.append(s[i])
        shuffled.append(s[half + i])
    return shuffled

Use Ok to test your code:

python3 ok -q shuffle

Q6: Deep Map

Definition: A nested list of numbers is a list that contains numbers and lists. It may contain only numbers, only lists, or a mixture of both. The lists must also be nested lists of numbers. For example: [1, [2, [3]], 4], [1, 2, 3], and [[1, 2], [3, 4]] are all nested lists of numbers.

Write a function deep_map that takes two arguments: a nested list of numbers s and a one-argument function f. It modifies s in place by replacing each number in s with the result of calling f on that number.

Important: deep_map returns None and should not create any new lists.

Hint: type(a) == list will evaluate to True if a is a list.

def deep_map(f, s: list) -> list:
    """Replace all non-list elements x with f(x) in the nested list s.

    >>> six = [1, 2, [3, [4], 5], 6]
    >>> deep_map(lambda x: x * x, six)
    >>> six
    [1, 4, [9, [16], 25], 36]
    >>> # Check that you're not making new lists
    >>> s = [3, [1, [4, [1]]]]
    >>> s1 = s[1]
    >>> s2 = s1[1]
    >>> s3 = s2[1]
    >>> deep_map(lambda x: x + 1, s)
    >>> s
    [4, [2, [5, [2]]]]
    >>> s1 is s[1]
    True
    >>> s2 is s1[1]
    True
    >>> s3 is s2[1]
    True
    """

    for i in range(len(s)):
        if type(s[i]) == list:
            deep_map(f, s[i])
        else:
            s[i] = f(s[i])

Use Ok to test your code:

python3 ok -q deep_map

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!

Q7: 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: int) -> int:
    """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(sum_needed: int) -> int:
    """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(SOURCE_FILE, 'count_dollars_upward', ['While', 'For'])
    True
    """

    def constrained_count(sum_needed, smallest_bill):
        if sum_needed == 0:
            return 1
        if sum_needed < 0:
            return 0
        if smallest_bill == None:
            return 0
        without_dollar_bill = constrained_count(sum_needed, next_larger_dollar(smallest_bill))
        with_dollar_bill = constrained_count(sum_needed - smallest_bill, smallest_bill)
        return without_dollar_bill + with_dollar_bill
    return constrained_count(sum_needed, 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 sum needed and dollar bill value.
  • Partition size is not linear. To get the next partition you need to call next_larger_dollar.

Exam Practice

Here are some related questions from past exams for you to try. These are optional. There is no way to submit them.

  1. Fall 2017 MT1 Q4a: Digital
  2. Fall 2019 Final Q6b: Palindromes