Homework 2 Solutions

hw02.zip

Solution Files

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

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

Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

YouTube link

Parsons Problems

To work on these problems, open the Parsons editor:

python3 parsons

Q1: Count Until Larger

Implement the function count_until_larger. count_until_larger takes in a positive integer num. count_until_larger counts the distance between the rightmost digit of num and the nearest greater digit; to do so, the function counts digits from right to left. Once it encounters a digit larger than the rightmost digit, it returns that count. If no such digit exists, then the function returns -1.

For example, 8117 has a rightmost digit of 7 and returns a count of 3. 9118117 also returns a count of 3: for both, the count stops at 8.

0 should be treated as having no digits and returns a count of -1.

Consult the following doctests for specific behaviors of count_until_larger.

def count_until_larger(num):
    """
    Complete the function count_until_larger that takes in a positive integer num.
    count_until_larger examines the rightmost digit and counts digits from right to
    left until it encounters a digit larger than the rightmost digit, then returns that count.

    >>> count_until_larger(117) # .Case 1
    -1
    >>> count_until_larger(8117) # .Case 2
    3
    >>> count_until_larger(9118117) # .Case 3
    3
    >>> count_until_larger(8777)  # .Case 4
    3
    >>> count_until_larger(22) # .Case 5
    -1
    >>> count_until_larger(0) # .Case 6
    -1
    """
    rightmost = num % 10
    count = 0
    while num:
        if num % 10 > rightmost:
            return count
        num = num // 10
        count = count + 1
    return -1

Q2: Filter Sequence

Write a function filter_sequence which takes in two integers, start and stop, as well as a function cond, which takes in a single argument and outputs a boolean value. filter_sequence returns the sum of all digits from start to stop (inclusive) for which cond returns True.

def filter_sequence(cond, start, stop):
    """
    Returns the sum of numbers from start (inclusive) to stop (inclusive) that satisfy
    the one-argument function cond.

    >>> filter_sequence(lambda x: x % 2 == 0, 0, 10) # .Case 1
    30
    >>> filter_sequence(lambda x: x % 2 == 1, 0, 10) # .Case 2
    25
    """
    curr = start
    total = 0
    while curr <= stop:
        if cond(curr):
            total += curr
        curr += 1
    return total

Code Writing Questions

Q3: Hailstone

Douglas Hofstadter's Pulitzer-prize-winning book, Gödel, Escher, Bach, poses the following mathematical puzzle.

Pick a positive integer n as the start.
If n is even, divide it by 2.
If n is odd, multiply it by 3 and add 1.
Continue this process until n is 1.

The number n will travel up and down but eventually end at 1 (at least for all numbers that have ever been tried -- nobody has ever proved that the sequence will terminate). Analogously, a hailstone travels up and down in the atmosphere before eventually landing on earth.

This sequence of values of n is often called a Hailstone sequence. Write a function that takes a single argument with formal parameter name n, prints out the hailstone sequence starting at n, and returns the number of steps in the sequence:

def hailstone(n):
    """Print the hailstone sequence starting at n and return its
    length.

    >>> a = hailstone(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    >>> b = hailstone(1)
    1
    >>> b
    1
    """
    length = 1
    while n != 1:
        print(n)
        if n % 2 == 0:
            n = n // 2      # Integer division prevents "1.0" output
        else:
            n = 3 * n + 1
        length = length + 1
    print(n)                # n is now 1
    return length

Hailstone sequences can get quite long! Try 27. What's the longest you can find?

Note that if n == 1 initially, then the sequence is one step long.

Use Ok to test your code:

python3 ok -q hailstone

Curious about hailstones or hailstone sequences? Take a look at these articles:

Check out this article to learn more about how hailstones work!
In 2019, there was a major development in understanding how the hailstone conjecture works for most numbers!

We keep track of the current length of the hailstone sequence and the current value of the hailstone sequence. From there, we loop until we hit the end of the sequence, updating the length in each step.

Note: we need to do floor division // to remove decimals.

Q4: Product

The summation(n, term) function from the higher-order functions lecture adds up term(1) + ... + term(n). Write a similar 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
    """
    total, k = 1, 1
    while k <= n:
        total, k = term(k) * total, k + 1
    return total

Use Ok to test your code:

python3 ok -q product

The product function has similar structure to summation, but starts accumulation with the value total=1.

Q5: Accumulate

Let's take a look at how summation and product are instances 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
    """
    total, k = start, 1
    while k <= n:
        total, k = merger(total, term(k)), k + 1
    return total

# Alternative solution
def accumulate_reverse(merger, start, n, term):
    total, k = start, n
    while k >= 1:
        total, k = merger(total, term(k)), k - 1
    return total

# Recursive solution
def accumulate2(merger, start, n, term):
    if n == 0:
        return start
    return merger(term(n), accumulate2(merger, start, n-1, term))

# Alternative recursive solution using start to keep track of total
def accumulate3(merger, start, n, term):
    if n == 0:
        return start
    return accumulate3(merger, merger(start, term(n)), n-1, term)

accumulate has the following parameters:

term and n: the same parameters as in summation and 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, b, and c. 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.

Use Ok to test your code:

python3 ok -q accumulate
python3 ok -q summation_using_accumulate
python3 ok -q product_using_accumulate

We want to abstract the logic of product and summation into accumulate. The differences between product and summation are:

How to merge terms. For product, we merge via * (mul). For summation, we merge via + (add).
The starting value. For product, we want to start off with 1 since starting with 0 means that our result (via multiplying with the start) will always be 0. For summation, we want to start off with 0 so we're not adding any extra value what we are trying to sum.

We can then define the merge method as merger and the starting value as start inside our accumulate, with the remaining logic of going through the loop being similar to product and summation.

Once we've defined accumulate, we can now implement product_using_accumulate and summation_using_accumulate by passing in the appropriate parameters to accumulate.

Submit

Make sure to submit this assignment by running:

python3 ok --submit

Bonus Questions

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!

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 included remain good exam-level problems doable without access to an interpreter.

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