Due by 11:59pm on Thursday, July 6

Instructions

Download hw02.zip. Inside the archive, you will find a file called hw02.py, along with a copy of the ok autograder.

Submission: When you are done, submit the assignment by uploading all code files you've edited to Gradescope. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on Gradescope. See Lab 0 for more instructions on submitting assignments.

Using Ok: If you have any questions about using Ok, please refer to this guide.

Readings: You might find the following references useful:

• Section 1.6

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus. This homework is out of 2 points.

Required questions

Several doctests refer to these functions:

from operator import add, mul

square = lambda x: x * x

identity = lambda x: x

triple = lambda x: 3 * x

increment = lambda x: x + 1

Higher Order Functions

Q1: Product

Write a function called product that returns term(1) * ... * term(n).

def product(n, term):
    """Return the product of the first n terms in a sequence.

    n: a positive integer
    term:  a function that takes one argument to produce the term

    >>> product(3, identity)  # 1 * 2 * 3
    6
    >>> product(5, identity)  # 1 * 2 * 3 * 4 * 5
    120
    >>> product(3, square)    # 1^2 * 2^2 * 3^2
    36
    >>> product(5, square)    # 1^2 * 2^2 * 3^2 * 4^2 * 5^2
    14400
    >>> product(3, increment) # (1+1) * (2+1) * (3+1)
    24
    >>> product(3, triple)    # 1*3 * 2*3 * 3*3
    162
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q product
Copy
✂️

Q2: Accumulate

Let's take a look at how product is an instance of a more general function called accumulate, which we would like to implement:

def accumulate(merger, start, n, term):
    """Return the result of merging the first n terms in a sequence and start.
    The terms to be merged are term(1), term(2), ..., term(n). merger is a
    two-argument commutative function.

    >>> accumulate(add, 0, 5, identity)  # 0 + 1 + 2 + 3 + 4 + 5
    15
    >>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
    26
    >>> accumulate(add, 11, 0, identity) # 11
    11
    >>> accumulate(add, 11, 3, square)   # 11 + 1^2 + 2^2 + 3^2
    25
    >>> accumulate(mul, 2, 3, square)    # 2 * 1^2 * 2^2 * 3^2
    72
    >>> # 2 + (1^2 + 1) + (2^2 + 1) + (3^2 + 1)
    >>> accumulate(lambda x, y: x + y + 1, 2, 3, square)
    19
    >>> # ((2 * 1^2 * 2) * 2^2 * 2) * 3^2 * 2
    >>> accumulate(lambda x, y: 2 * x * y, 2, 3, square)
    576
    >>> accumulate(lambda x, y: (x + y) % 17, 19, 20, square)
    16
    """
    "*** YOUR CODE HERE ***"

accumulate has the following parameters:

• term and n: the same parameters as in product
• merger: a two-argument function that specifies how the current term is merged with the previously accumulated terms.
• start: value at which to start the accumulation.

For example, the result of accumulate(add, 11, 3, square) is

11 + square(1) + square(2) + square(3) = 25

Note: You may assume that merger is commutative. That is, merger(a, b) == merger(b, a) for all a and b. However, you may not assume merger is chosen from a fixed function set and hard-code the solution.

After implementing accumulate, show how summation and product can both be defined as function calls to accumulate.

Important: You should have a single line of code (which should be a return statement) in each of your implementations for summation_using_accumulate and product_using_accumulate, which the syntax check will check for.

def summation_using_accumulate(n, term):
    """Returns the sum: term(1) + ... + term(n), using accumulate.

    >>> summation_using_accumulate(5, square)
    55
    >>> summation_using_accumulate(5, triple)
    45
    >>> # You aren't expected to understand the code of this test.
    >>> # Check that the bodies of the functions are just return statements.
    >>> # If this errors, make sure you have removed the "***YOUR CODE HERE***".
    >>> import inspect, ast
    >>> [type(x).__name__ for x in ast.parse(inspect.getsource(summation_using_accumulate)).body[0].body]
    ['Expr', 'Return']
    """
    "*** YOUR CODE HERE ***"

def product_using_accumulate(n, term):
    """Returns the product: term(1) * ... * term(n), using accumulate.

    >>> product_using_accumulate(4, square)
    576
    >>> product_using_accumulate(6, triple)
    524880
    >>> # You aren't expected to understand the code of this test.
    >>> # Check that the bodies of the functions are just return statements.
    >>> # If this errors, make sure you have removed the "***YOUR CODE HERE***".
    >>> import inspect, ast
    >>> [type(x).__name__ for x in ast.parse(inspect.getsource(product_using_accumulate)).body[0].body]
    ['Expr', 'Return']
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q accumulate
python3 ok -q summation_using_accumulate
python3 ok -q product_using_accumulate
Copy
✂️

Takeaway: Notice how quick it is now to create accumulator functions with different merger functions! This is because we abstracted away the logic of product and summation into the accumulate function. Without this abstraction, our code for a summation function would be just as long as our code for the product function from Question 1, and the logic would be highly redundant!

Q3: Funception

Write a function (funception) that takes in another function func1 and a number start and returns a function (func2) that will have one parameter to take in the stop value. func2 should take the following into consideration in order:

1. Takes in the stop value.
2. If the value of start is less than 0, exit the function by returning None.
3. If the value of start is greater than or equal to stop, apply func1 on start and return the result.
4. If not, apply func1 on all the numbers from start (inclusive) up to stop (exclusive) and return the product.

Note: While similar to accumulate, the function returned by funception merges terms over the range [start, stop] (rather than [1, n] alongside some arbitrary start term). funception also handles invalid start values.

def funception(func1, start):
    """ Takes in a function (function 1) and a start value.
    Returns a function (function 2) that will find the product of
    function 1 applied to the range of numbers from
    start (inclusive) to stop (exclusive)

    >>> def func1(num):
    ...     return num + 1
    >>> func2_1 = funception(func1, 0)
    >>> func2_1(3)    # func1(0) * func1(1) * func1(2) = 1 * 2 * 3 = 6
    6
    >>> func2_2 = funception(func1, 1)
    >>> func2_2(4)    # func1(1) * func1(2) * func1(3) = 2 * 3 * 4 = 24
    24
    >>> func2_3 = funception(func1, 3)
    >>> func2_3(2)    # Returns func1(3) since start >= stop
    4
    >>> func2_4 = funception(func1, 3)
    >>> func2_4(3)    # Returns func1(3) since start >= stop
    4
    >>> func2_5 = funception(func1, -2)
    >>> func2_5(-3)    # Returns None since start < 0
    >>> func2_6 = funception(func1, -1)
    >>> func2_6(4)    # Returns None since start < 0
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q funception
Copy
✂️

Recursion

Q4: Num Eights

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

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

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

Use Ok to test your code:

python3 ok -q num_eights
Copy
✂️

Q5: Waves

In a number, we define...

• a "crest" as a region where a series of consecutive digits transition from increasing to decreasing. This region may be a single digit, or a series of equal digits called a "plateau".
• a "trough" is a region where a series of consecutive digits transition from decreasing to increasing. This region is again either a single digit or a plateau.
• a "plateau" is a sequence where the digits remain constant.

Equivalently, if we plot the digits of a number on a vertical axis, the number of crests or troughs can be thought of as the number of times that the slope changes from positive to negative or positive to negative respectively.

Important: Due to plateaus, a region's 'slope' on the graph can go from positive->zero->negative or negative->zero->positive and still be considered a crest or trough.

• A number is balanced if it has as many crests as it does troughs.

For example, 12332023213 is balanced with two crests and two troughs: 12[33]202[3]213 (crests at [33] and [3], troughs at [0] and [1].)

On the other hand, 1223321 is not balanced with one crest and no troughs: 122[33]21 (crest at [33].) It also has two plateaus, but only [33] is a crest because it marks where the number transitions from increasing to decreasing.

Implement the function waves, which takes n and and returns True if the number n is balanced, or False otherwise. Use recursion, or else the tests will fail.

Hint: If you're stuck, first try implementing waves using assignment statements and a while statement. Then, to convert this into a recursive solution, think about how local variables used in our iterative solution might translate to parameters in our helper funciton. In this case, we'll likely need some mechanism for comparing consecutive triplets of digits.

Hint: As with solving any involved recursion problem, it's a good idea to break it down into what cases we will have to handle. Here are some important ones to think about!

1. What's our base case? When do we halt recursion and what's the desired output?
2. How do we detect a crest? What do we update if we find one?
3. How do we detect a trough? What do we update if we find one?
4. How do we know if we're on a plateau? What changes in this case?
5. What do we do if none of the other cases are met?

def waves(n):
    """Return whether n is balanced.

    >>> waves(1)
    True
    >>> waves(10001)
    False
    >>> waves(12233121)
    False
    >>> waves(1313)
    True
    >>> waves(12332023213)
    True
    >>> from construct_check import check
    >>> # ban all loops
    >>> check(HW_SOURCE_FILE, 'waves',
    ...       ['For', 'While'])
    True
    """
    def helper(n, count, prev):
        curr, next, rest = n % 10, (n // 10) % 10, n // 10
        "*** YOUR CODE HERE ***"
    return helper(n // 10, 0, n % 10)

Use Ok to test your code:

python3 ok -q waves
Copy
✂️

Q6: 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.

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(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(HW_SOURCE_FILE, 'count_coins', ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q count_coins
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

Make sure to submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. For a refresher on how to do this, refer to Lab 00.

Exam Practice

Homework assignments will also contain prior exam questions for you to try. These questions have no submission component; feel free to attempt them if you'd like some practice!

Note that exams from Spring 2020, Fall 2020, and Spring 2021 gave students access to an interpreter, so the question format may be different than other years. Regardless, the questions below are good problems to try without access to an interpreter.

1. Fall 2019 MT1 Q3: You Again [Higher Order Functions]
2. Spring 2021 MT1 Q4: Domain on the Range [Higher Order Functions]
3. Fall 2021 MT1 Q1b: tik [Functions and Expressions]