Lab 3 Solutions
Solution Files
Submit
In order to facilitate studying for the exam, solutions to this lab are released with the lab. We encourage you to try out the problems first on your own before referencing the solutions as a guide.
Note: You do not need to submit to Gradescope to receive credit for this assignment.
All Questions Are Optional
The questions in this assignment are not graded, but they are highly recommended to help you prepare for the upcoming exam. You will receive credit for this lab even if you do not complete these questions.
Suggested Questions
Walkthrough Videos
These videos provide detailed walkthroughs of the problems presented in this lab.
To see these videos, you should be logged into your berkeley.edu email.
Control
Q1: Ordered Digits
Implement the function ordered_digits
, which takes as input a
positive integer and returns True
if its digits, read left to right,
are in non-decreasing order, and False
otherwise. For example, the
digits of 5, 11, 127, 1357 are ordered, but not those of 21 or 1375.
def ordered_digits(x):
"""Return True if the (base 10) digits of X>0 are in non-decreasing
order, and False otherwise.
>>> ordered_digits(5)
True
>>> ordered_digits(11)
True
>>> ordered_digits(127)
True
>>> ordered_digits(1357)
True
>>> ordered_digits(21)
False
>>> result = ordered_digits(1375) # Return, don't print
>>> result
False
>>> cases = [(1, True), (9, True), (10, False), (11, True), (32, False),
... (23, True), (99, True), (111, True), (122, True), (223, True),
... (232, False), (999, True),
... (13334566666889, True), (987654321, False)]
>>> [ordered_digits(s) == t for s, t in cases].count(False)
0
"""
last = x % 10
x = x // 10
while x > 0 and last >= x % 10:
last = x % 10
x = x // 10
return x == 0
Use Ok to test your code:
python3 ok -q ordered_digits
We split off each digit in turn from the right, comparing it to the previous digit we split off, which was the one immediately to its right. We stop when we run out of digits or we find an out-of-order digit.
Q2: K Runner
An increasing run of an integer is a sequence of consecutive digits in which each digit is larger than the last. For example, the number 123444345 has four increasing runs: 1234, 4, 4 and 345. Each run can be indexed from the end of the number, starting with index 0. In the example, the 0th run is 345, the first run is 4, the second run is 4 and the third run is 1234.
Implement get_k_run_starter
, which takes in integers n
and k
and returns
the 0th digit of the k
th increasing run within n
. The 0th digit is the
leftmost number in the run. You may assume that there are at least k+1
increasing runs in n
.
def get_k_run_starter(n, k):
"""Returns the 0th digit of the kth increasing run within n.
>>> get_k_run_starter(123444345, 0) # example from description
3
>>> get_k_run_starter(123444345, 1)
4
>>> get_k_run_starter(123444345, 2)
4
>>> get_k_run_starter(123444345, 3)
1
>>> get_k_run_starter(123412341234, 1)
1
>>> get_k_run_starter(1234234534564567, 0)
4
>>> get_k_run_starter(1234234534564567, 1)
3
>>> get_k_run_starter(1234234534564567, 2)
2
"""
i = 0
final = None
while i <= k: while n > 10 and (n % 10 > (n // 10) % 10): n = n // 10 final = n % 10 i = i + 1 n = n // 10 return final
Use Ok to test your code:
python3 ok -q get_k_run_starter
Video walkthrough:
Higher Order Functions
These are some utility function definitions you may see being used as part of the doctests for the following problems.
from operator import add, mul
square = lambda x: x * x
identity = lambda x: x
triple = lambda x: 3 * x
increment = lambda x: x + 1
Q3: Make Repeater
Implement the function make_repeater
so that make_repeater(func, n)(x)
returns func(func(...func(x)...))
, where func
is applied n
times. That
is, make_repeater(func, n)
returns another function that can then be applied
to another argument. For example, make_repeater(square, 3)(42)
evaluates to
square(square(square(42)))
.
def make_repeater(func, n):
"""Return the function that computes the nth application of func.
>>> add_three = make_repeater(increment, 3)
>>> add_three(5)
8
>>> make_repeater(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
243
>>> make_repeater(square, 2)(5) # square(square(5))
625
>>> make_repeater(square, 4)(5) # square(square(square(square(5))))
152587890625
>>> make_repeater(square, 0)(5) # Yes, it makes sense to apply the function zero times!
5
"""
g = identity
while n > 0:
g = composer(func, g)
n = n - 1
return g
# Alternative solutions
def make_repeater2(func, n):
def inner_func(x):
k = 0
while k < n:
x, k = func(x), k + 1
return x
return inner_func
def composer(func1, func2):
"""Return a function f, such that f(x) = func1(func2(x))."""
def f(x):
return func1(func2(x))
return f
Use Ok to test your code:
python3 ok -q make_repeater
Solution using composer
:
We create a new function in every iteration of the while
statement
by calling composer
.
Solution not using composer
:
We create a single inner function that contains the while
logic
needed to do calculations directly, as opposed to creating another
function for every while
loop iteration.
Q4: Apply Twice
Using make_repeater
define a function apply_twice
that takes a function of
one argument as an argument and returns a function that applies the
original function twice. For example, if inc
is a function that
returns 1
more than its argument, then apply_twice(inc)
should be a
function that returns two more:
def apply_twice(func):
""" Return a function that applies func twice.
func -- a function that takes one argument
>>> apply_twice(square)(2)
16
"""
return make_repeater(func, 2)
Use Ok to test your code:
python3 ok -q apply_twice
Using composer
from class, the body of apply_twice
can also be
written as return composer(func, func)
.
Q5: It's Always a Good Prime
Implement div_by_primes_under
, which takes in an integer n
and returns an
n-divisibility checker. An n-divisibility-checker is a function that takes
in an integer k and returns whether k
is divisible by any integers between 2
and n
, inclusive. Equivalently, it returns whether k
is divisible by any
primes less than or equal to n
.
Review the Disc 01 is_prime
problem for a reminder about prime numbers.
You can also choose to do the no lambda version, which is the same problem, just with defining functions with def instead of lambda.
Hint: If struggling, here is a partially filled out line for after the
if
statement:checker = (lambda f, i: lambda x: __________)(checker, i)
def div_by_primes_under(n):
"""
>>> div_by_primes_under(10)(11)
False
>>> div_by_primes_under(10)(121)
False
>>> div_by_primes_under(10)(12)
True
>>> div_by_primes_under(5)(1)
False
"""
checker = lambda x: False
i = 2 while i <= n: if not checker(i):
checker = (lambda f, i: lambda x: x % i == 0 or f(x))(checker, i) i = i + 1 return checker
def div_by_primes_under_no_lambda(n):
"""
>>> div_by_primes_under_no_lambda(10)(11)
False
>>> div_by_primes_under_no_lambda(10)(121)
False
>>> div_by_primes_under_no_lambda(10)(12)
True
>>> div_by_primes_under_no_lambda(5)(1)
False
"""
def checker(x):
return False
i = 2 while i <= n: if not checker(i):
def outer(f, i): def inner(x): return x % i == 0 or f(x) return inner checker = outer(checker, i) i = i + 1 return checker
Use Ok to test your code:
python3 ok -q div_by_primes_under
python3 ok -q div_by_primes_under_no_lambda
Environment Diagrams
Q6: Doge
Draw the environment diagram for the following code.
wow = 6
def much(wow):
if much == wow:
such = lambda wow: 5
def wow():
return such
return wow
such = lambda wow: 4
return wow()
wow = much(much(much))(wow)
You can check out what happens when you run the code block using Python Tutor. Please ignore the “ambiguous parent frame” message on step 18. The parent is in fact f1.
Q7: YY Diagram
Draw the environment diagram that results from executing the code below.
Tip: Using the
+
operator with two strings results in the second string being appended to the first. For example"C"
+"S"
concatenates the two strings into one string"CS"
.
y = "y"
h = y
def y(y):
h = "h"
if y == h:
return y + "i"
y = lambda y: y(h)
return lambda h: y(h)
y = y(y)(y)
You can check out what happens when you run the code block using Python Tutor.
Q8: Environment Diagrams - Challenge
These questions were originally developed by Albert Wu and are included here for extra practice. We recommend checking your work in PythonTutor after filling in the diagrams for the code below.
Challenge 1
Draw the environment diagram that results from executing the code below.
Guiding Notes: Pay special attention to the names of the frames!
Multiple assignments in a single line: We will first evaluate the expressions on the right of the assignment, and then assign those values to the expressions on the left of the assignment. For example, if we had
x, y = a, b
, the process of evaluating this would be to first evaluatea
andb
, and then assign the value ofa
tox
, and the value ofb
toy
.
def funny(joke):
hoax = joke + 1
return funny(hoax)
def sad(joke):
hoax = joke - 1
return hoax + hoax
funny, sad = sad, funny
result = funny(sad(1))
In the line funny, sad = sad, funny
, we will end up with the result that
the variable funny
now references the function whose intrinsic name
(the name with which it was defined) is sad
, and the variable sad
now
references the function whose intrinsic name is funny
.
Thus, when we call funny(sad(1))
in the last line, we will evaluate the
variable funny
to be the function called sad
(defined from
def sad(joke): ...
). The argument we want to pass into the function call
is sad(1)
, where the variable sad
references the function funny
(defined from def funny(joke): ...
).
Thus, our first function frame will be to evaluate funny(1)
where this
funny
represents the intrinsic name of the actual function we're calling.
Inside of funny
, we have the call funny(hoax)
, which will prompt us to
look up what funny
as a variable points to. No local variable in our
function frame is called funny
, so we go to the global frame, where the
variable funny
points to the function sad
. As a result we will
call sad
on the value hoax
.
The return value of this function call then gets passed into a function call
to sad
(where this sad
represents the intrinsic name of the function),
and finally the return value of this function call to sad
will be assigned
to result
in the global frame.
Video walkthrough:
Challenge 2
Draw the environment diagram that results from executing the code below.
def double(x):
return double(x + x)
first = double
def double(y):
return y + y
result = first(10)
Video walkthrough: