Exam Prep 2: Higher-Order Functions, Self Reference
Students from past semesters wanted more content and structured time to prepare for exams. Exam Prep sections are a way to solidify your understanding of the week's materials. The problems are typically designed to be a bridge between discussion/lab/homework difficulty and exam difficulty.
Reminder: There is nothing to turn in and there is no credit given for attending Exam Prep Sections.
We try to make these problems exam level , so you are not expected to be able to solve them coming straight from lecture without additional practice. To get the most out of Exam Prep, we recommend you try these problems first on your own before coming to the Exam Prep section, where we will explain how to solve these problems while giving tips and advice for the exam. Do not worry if you struggle with these problems, it is okay to struggle while learning.
You can work with anyone you want, including sharing solutions. We just ask you don't spoil the problems for anyone else in the class. Thanks!
You may only put code where there are underscores for the codewriting questions.
You can test your functions on their doctests by running test(function_name)
in the python interpreter after clicking Run in 61A Code.
Passing the doctests is not necessarily enough to get the problem fully correct. You must fully solve the stated problem.
We recommending reading sections 1.1-1.6 from the textbook for these problems. We also recommend reviewing Hog project announce_lead_changes
and announce_highest
for question 2 and 3.
Test your work! For example, for match_k
, you can type test(match_k)
in the python interpreter you get once you click Run in 61A Code to verify if you pass the doctests or not.
Q1: Match Maker
Difficulty: ⭐
Implement match_k
, which takes in an integer k
and returns a function that takes in a variable x
and returns True if all the digits in x
that are k
apart are the same.
For example, match_k(2)
returns a one argument function that takes in x
and checks if digits that are 2 away in x
are the same.
match_k(2)(1010)
has the value of x = 1010
and digits 1, 0, 1, 0 going from left to right. 1 == 1
and 0 == 0
, so the match_k(2)(1010)
results in True
.
match_k(2)(2010)
has the value of x = 2010
and digits 2, 0, 1, 0 going from left to right. 2 != 1
and 0 == 0
, so the match_k(2)(2010)
results in False
.
RESTRICTION: You may not use strings or indexing for this problem.
IMPORTANT: You do not have to use all the lines, one staff solution does not use the line directly above the while loop.
HINT: Floor dividing by powers of 10 gets rid of the rightmost digits.
Your Answer Run in 61A Codedef 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
Q2: Natural Chainz
Difficulty: ⭐⭐
For this problem, a chain_function
is a higher order function that repeatedly accepts natural numbers (positive integers).
The first number that is passed into the function that chain_function
returns initializes a natural chain,
which we define as a consecutive sequence of increasing natural numbers (i.e., 1, 2, 3). A natural chain
breaks when the next input differs from the expected value of the sequence. For example, the sequence
(1, 2, 3, 5) is broken because it is missing a 4.
Implement the chain_function
so that it prints out the
value of the expected number at each chain break as well as the number of chain breaks seen so far,
including the current chain break. Each time the chain breaks, the chain restarts at the most recently input number.
For example, the sequence (1, 2, 3, 5, 6) would only print 4 and 1. We print 4 because there is a missing 4, and we print 1 because the 4 is the first number to break the chain. The 5 broke the chain and restarted the chain, so from here on out we expect to see numbers increasingly linearly from 5. See the doctests for more examples. You may assume that the higher-order function is never given numbers ≤ 0.
IMPORTANT: For this problem, the starter code template is just a suggestion. You are welcome to add/delete/modify the starter code template, or even write your own solution that doesn’t use the starter code at all.
Your Answer Run in 61A Codedef 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
Q3: CS61 - NAY
Difficulty: ⭐⭐⭐
Part A: Implement cs61nay
, which takes a two argument function combiner
and positive integer n
and returns a function.
The returned function then takes n
arguments, one at a time, and computes
combiner(...(combiner(combiner(arg1, arg2), arg3)...), arg_n)
. Notice combiner takes in two integers and returns one integer.
For example, the first doctest has the returned function f = cs61nay(lambda x, y: x * y, 3)
. Now when f
is applied to three arguments, like f(2)(3)(4)
, it multiplies them together, 2*3*4
to get 24.
IMPORTANT: For this problem, the starter code template is just a suggestion. You are welcome to add/delete/modify the starter code template, or even write your own solution that doesn’t use the starter code at all.
HINT: For the n = 1
case, the returned function doesn't use combiner
.
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))
Difficulty: ⭐⭐⭐
Part B: Somebody who writes very complicated code has given you a challenge! You would hopefully never see something so hard to comprehend in the real world.
Complete the expression below by writing one integer in each blank so that the whole expression evaluates to 2021. Assume cs61nay
is implemented correctly.
HINTS:
- You can fill the blanks and test your code with a python interpreter
- Try to understand what all the subparts and smaller calls do
- You can split this up into multiple lines to make it more readable
- You can add spaces/indentation to make it easier to read
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!
Difficulty: ⭐⭐
Part C: All those lines of code are unnecessary! Solve cs61NAY
but only using one line.
RESTRICTION: You may not use the python ternary operator (the one line if/else statment).
HINT: Use short circuiting and boolean operators to your advantage
Your Answer Run in 61A Codecs61NAY = 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
"""
Just for Fun
This is a challenge problem and not reflective of exam difficulty. We will not be going over this problem in examprep section, but we will be releasing solutions.Q4: Abusing the Call Stack
(a) Implement the following higher order functions so that we can simulate append
and get
behavior. As the
name suggests, the get
function should get the ith
element that was appended (the first element that
was appended is element 0). For example, if I append 2, append 30, and then append 4, then get(0)
is
2 (the first element appended), get(1)
is 30 (the second element appended), and get(2)
is 4 (the third
element appended). If I append more items, get(0)
through get(2)
should not be affected. Assume all get
calls ask for non-negative indices (i.e., you’d never do get(-1)
). If the argument to get would go out of
bounds otherwise, the call should return the string "Error: out of bounds!"
.
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
(b) Build on your solution to the previous question to implement insert
functionality! As the name suggests,
the insert
function inserts a value into an existing sequence of numbers. The function takes an insertion
index, the value to insert into that index, as well as two other arguments whose purpose is left for you
to determine. When the value is inserted into the provided index, all numbers from that index and to
the right are shifted one element right. For example, if my current sequence is 5, 9, 14, 3 and I specify
an insertion index of 1 with value 100, then my updated sequence should be 5, 100, 9, 14, 3. The 100 is
inserted at index 1, and all numbers from the original index 1 to the end are shifted to the right by one
position. You can always assume that the provided insertion index will be within bounds.
You don’t actually have to represent the sequence as a contiguous block of numbers that need to shift
around though. As long as the get(i)
call returns the correct value, that’ll do.
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