Exam Prep 2: Higher-Order Functions, Self Reference

• examprep02.pdf

def match_k(k):
    """ Return a function that checks if digits k apart match

    >>> match_k(2)(1010)
    True
    >>> match_k(2)(2010)
    False
    >>> match_k(1)(1010)
    False
    >>> match_k(1)(1)
    True
    >>> match_k(1)(2111111111111111)
    False
    >>> match_k(3)(123123)
    True
    >>> match_k(2)(123123)
    False
    """
    def check(x):
        i = 0
        while 10 ** (i + k) < x:
            if (x // 10**i) % 10 != (x // 10 ** (i + k)) % 10:
                return False
            i = i + 1
        return True
    return check

# Alternate solution
def match_k_alt(k):
    """ Return a function that checks if digits k apart match

    >>> match_k_alt(2)(1010)
    True
    >>> match_k_alt(2)(2010)
    False
    >>> match_k_alt(1)(1010)
    False
    >>> match_k_alt(1)(1)
    True
    >>> match_k_alt(1)(2111111111111111)
    False
    >>> match_k_alt(3)(123123)
    True
    >>> match_k_alt(2)(123123)
    False
    """
    def check(x):
        while x // (10 ** k):
            if (x % 10) != (x // (10 ** k)) % 10:
                return False
            x //= 10
        return True
    return check

def chain_function():
    """
    >>> tester = chain_function()
    >>> x = tester(1)(2)(4)(5) # Expected 3 but got 4, so print 3. 1st chain break, so print 1 too.
    3 1
    >>> x = x(2) # 6 should've followed 5 from above, so print 6. 2nd chain break, so print 2
    6 2
    >>> x = x(8) # The chain restarted at 2 from the previous line, but we got 8. 3rd chain break.
    3 3
    >>> x = x(3)(4)(5) # Chain restarted at 8 in the previous line, but we got 3 instead. 4th break
    9 4
    >>> x = x(9) # Similar logic to the above line
    6 5
    >>> x = x(10) # Nothing is printed because 10 follows 9.
    >>> y = tester(4)(5)(8) # New chain, starting at 4, break at 6, first chain break
    6 1
    >>> y = y(2)(3)(10) # Chain expected 9 next, and 4 after 10. Break 2 and 3.
    9 2
    4 3
    """
    def g(x, y):
        def h(n):
            if x == 0 or n == x:
                return g(n + 1, y)
            else:
                # BEGIN SOLUTION ALT="return ____________________________" NO PROMPT
                return print(x, y + 1) or g(n + 1, y + 1)
        return h
    return g(0, 0)

To better understand this solution, let’s rename y to be count and x to be expected_num. Let n be observed_num. Then on each call to h, we first check whether observed_num == expected_num, which in our problem is a check for n == x. If this condition is satisfied, then we increment our expected_num by one and do not change our count. Hence, we have a call to g with an incremented x and an unchanged y, and we do not print anything. The only other case in which we enter this suite is when (x, y) == (0, 0), which is when we pass in the very first number of the chain. We are told in the problem statement that we can assume there will never be a non-positive input to the chain. Hence, passing in (0, 0) as arguments to g is a sure indicator to h that we are currently on the first number of a chain, and we should not print anything (otherwise, when else would you see a 0 passed in as x?).

The second case is trickier. First, we need to print a number if our expected number differs from the observed number, but we also need to update expected_num and count since the chain is going to restart when the chain breaks. To do this in one line, we appeal to lab01, in which we learned that the return value of print is None, which is false-y, and that or operators short-circuit only if a truth-y value is encountered before the last operand. We can print x which is our expected number along with the number of chain breaks y + 1. This whole procedure returns None, so if we stick it as the first operand of the or operator, we know that the or operator will not short-circuit. The program will then proceed to evaluate g(n + 1, y + 1), which returns h. Although not necessary for this problem, it may be helpful to know that a function is truth-y. In this case, it doesn’t matter because an or will return the last operand it is given if it doesn’t short-circuit, regardless of the truth-y-ness of the last operand. Hence, the last line of h prints the appropriate numbers, updates the expected_num (restarting the chain), updates the count, and returns h, which will accept the next natural number into the chain.Why does g return h? Watch the indentations of each line very closely. The only thing the g function does is define a function h and then return h. All that other stuff where we check for equality and return print etc is all inside the h function. Hence, that code is not executed until we call h.

As a side note, if you are stuck on a problem like this one on an exam, it may be helpful to ignore the skeleton and first implement the code assuming you have unlimited lines and freedom to name your variables whatever you want. When I was writing this question, I named all my functions something meaningful, and you bet that my variables were not x and y but expected_num and count. I also had a separate line for the print. However, once I got into making a template skeleton for an exam level problem, I thought "how do I obfuscate the code to force people to think harder?" The variable name changes were easy, and condensing the print into the same line as the return was just a trick I’ve seen from previous exams in this course. I think that coming up with the whole solution from scratch by following the template is immensely harder than first coming up with your own working solution and then massaging your solution into the constraints of our blank lines.

• Derek Wan, Fall 2020

def cs61nay(combiner, n):
    """ Return a function that takes n arguments,
    one at a time, and combines them using combiner.

    >>> f = cs61nay(lambda x, y: x * y, 3)
    >>> f(2)(3)(4) # 2 * 3 * 4
    24
    >>> f(-1)(2)(3) # -1 * 2 * 3
    -6
    >>> f = cs61nay(lambda x, y: x - y, 4)
    >>> f(1)(2)(-2)(-1) # 1 - 2 - -2 - -1
    2
    >>> f = cs61nay(lambda x, y: x + y, 1)
    >>> f(61)
    61
    >>> f(2021)
    2021
    """
    if n == 1:
        return lambda x: x
    else:
        return lambda a: lambda b: cs61nay(combiner, n-1)(combiner(a, b))

from operator import sub, add, mul

compose = lambda f, g: lambda x: f(g(x))


print(compose(cs61nay(sub, 2), compose(cs61nay(mul, 3)(2), 
      cs61nay(pow, 2)(10))(3))(1)(-21))

For this problem, it is important to understand how cs61nay works and how compose work, and use the starter code as a puzzle to piece away at the solution.

First let's understand what cs61nay(pow, 2)(10) returns. Based on the description, it returns a one argument function that takes in x and returns pow(10, x), so it takes 10 to the power of whatever is passed in.

Next let's understand what compose(cs61nay(mul, ____)(2),cs61nay(pow, 2)(10))(3) does. In the blank we want to put a number that matches with how many total parameters we will pass in one by one into our combined cs61nay functions. Based on how compose is defined, this becomes 2 * (10 ^ 3), or 2000. If we put 2 in the blank, it would just return 2000, but we want to put a higher number so it still accepts more function calls.

The outer compose will do f(g(x)), where g is the inner function that results from the second compose, and so since it is passed back into f, which is the result of the outer cs61nay, we want g(x) to return a number, so the second blank is a 3.

2000 is a handy number to get to 2021, so we can pass in 1 for the second blank to get back 200 from 2 * (10 ^ 3) * 1, and since there is only one more function application before we get a number, the first blank is 2, and the computation is 2000 - last blank, and to get 2021, we can put -21 as the last blank!

cs61NAY = lambda combiner, n: (n == 1 and (lambda x: x)) or (lambda a: lambda b: cs61NAY(combiner, n-1)(combiner(a, b)))
# This syntax adds a doctest to a lambda, which can be run using `test(cs61NAY)`
# after clicking Run in 61A Code or `python3 -m doctest -v examprep02.py`
# if you save the questions to a .py file
cs61NAY.__name__ = "cs61NAY"
cs61NAY.__doc__ = """ Return a function that takes n arguments,
    one at a time, and combines them using combiner.

    >>> f = cs61NAY(lambda x, y: x * y, 3)
    >>> f(2)(3)(4) # 2 * 3 * 4
    24
    >>> f(-1)(2)(3) # -1 * 2 * 3
    -6
    >>> f = cs61NAY(lambda x, y: x - y, 4)
    >>> f(1)(2)(-2)(-1) # 1 - 2 - -2 - -1
    2
    >>> f = cs61NAY(lambda x, y: x + y, 1)
    >>> f(61)
    61
    >>> f(2021)
    2021
    """

def stacklist():
    """
    >>> append, get = stacklist()
    >>> get, y = append(2)
    >>> get, y = append(3, get, y)
    >>> get, y = append(4, get, y)
    >>> get(0)
    2
    >>> get(1)
    3
    >>> get(2)
    4
    >>> get, y = append(8, get, y)
    >>> get(1)
    3
    >>> get(3)
    8
    """
    g = lambda i: "Error: out of bounds!"
    def f(value, g=g, y=0):
        f = g
        def g(i):
            if i == y:
                return value
            return f(i)
        return g, y + 1
    return f, g

def stacklisted():
    """
    >>> append, get, insert = stacklisted()
    >>> get, idx = append(2)
    >>> get, idx = append(13, get, idx)
    >>> get, idx = append(4, get, idx)
    >>> get, idx = insert(1, 19, get, idx)
    >>> get(0)
    2
    >>> get(1)
    19
    >>> get(2)
    13
    >>> get(3)
    4
    """
    # Assume f and g are defined correctly from the previous question
    g = lambda i: "Error: out of bounds!"
    def f(value, g=g, y=0):
        f = g
        def g(i):
            if i == y:
                return value
            return f(i)
        return g, y + 1
    def h(y, value, g, n):
        e = g
        def g(i):
            if i == y:
                return value
            return e(i)
        k = y
        while k < n:
            g, ret = f(e(k), g, k + 1)
            k += 1
        return g, ret
    return f, g, h