Diagnostics are meant for you to check your understanding of the week's material. They are not worth any points and are not counted towards midterm recovery points; instead, diagnostics are solely for your benefit. If you find yourself struggling with the questions in this diagnostic, consider signing up for Tutoring.

Functions and expressions

Question 1

Try running the following code in Python:

x, y = 42, 0
def swap(a, b):
    """Reassigns variables x and y to b and a, respectively."""
    x, y = b, a

swap(x, y)
result = x / y

You should see an error occur on the last line:

ZeroDivisionError: division by zero

It seems like calling swap(x, y) didn't actually swap the variables! Why?

When swap is called, Python creates a new frame (let's call it f1). When Python executes the line x, y = b, a, it sees that f1 doesn't contain variables called x and y, so it creates local variables x and y in f1. It does not reassign variables in the global frame.

What happens if we change the definition of swap to

def swap(a, b):
    a, b = b, a

A ZeroDivisionError still occurs. Instead of creating two new local variables x and y in f1, now Python just reassigns the local variables a and b. The global variables x and y remain untouched.

Question 2

Suppose the following functions are entered into an interactive Python session:

def squirrel(facts):
    if facts >= 60:
        return facts
    else:
        print('Hungry')

def berkeley(facts, squirrel):
    print('acorn')
    status = squirrel(facts)
    if status:
        return 3
    else:
        print(4)

For each of the expressions in the table below, write all the lines that the interpreter would display.

  • The output may have multiple lines.
  • If it would display a function, write FUNCTION.
  • If it would cause an error, write ERROR.
  • You should include any lines displayed before an error.

The first row has been given to you as an example.

Remember from Lab 2 that None is a false-y value, and a non-empty string is a truth-y value.

Expression Evaluates to Displays in the interpreter:
print(42) None 42
berkeley(squirrel, 100)
berkeley(70, squirrel)
berkeley(50, squirrel)

Answers:

Expression Evaluates to Displays in the interpreter:
print(42) None 42
berkeley(squirrel, 100) ERROR
acorn
ERROR
berkeley(70, squirrel) 3
acorn
3
berkeley(50, squirrel) None
acorn
Hungry
4

Control structures

Question 3

Implement the function ordered_two_digits(n), where n is a non-negative integer (it can be 0). ordered_two_digits returns True if the tens digit of nis larger than the ones digit of n. For example,

  • Calling ordered_two_digits on these numbers will return True:

    • 52
    • 1342
  • Calling ordered_two_digits on these numbers will return False:

    • 25
    • 55
    • 1234
    • 9 (interpreted as 09)
    • 0 (interpreted as 00)

Hint: You can use the // and % operators to separate digits.

Note: Your solution should only fill in the blank — you do not need more than one line for this solution.

def ordered_two_digits(n):
    """Returns True if the tens digit of n is larger than the ones digit.

    >>> ordered_two_digits(52)
    True
    >>> ordered_two_digits(1342)
    True

    >>> ordered_two_digits(25)
    False
    >>> ordered_two_digits(55)
    False
    >>> ordered_two_digits(1234)
    False
    >>> ordered_two_digits(9)
    False
    >>> ordered_two_digits(0)
    False
    """
"*** YOUR CODE HERE ***" return ______
return (n // 10) % 10 > n % 10

The ones digit of a number can be calculated with n % 10. The tens digit of a number can be calculated with (n // 10) % 10 (remove the ones digit, then get the last digit of the new number).

Question 4: Two equal

Implement a function two_equal that takes three integer arguments and returns whether exactly two of the arguments are equal and the third is not.

def two_equal(a, b, c):
    """Return whether exactly two of the arguments are equal and the
    third is not.

    >>> two_equal(1, 2, 3)
    False
    >>> two_equal(1, 2, 1)
    True
    >>> two_equal(1, 1, 1)
    False
    >>> result = two_equal(5, -1, -1) # return, don't print
    >>> result
    True
    >>> two_equal(0, 0, -1)
    True
    >>> two_equal(0, 0, 0)
    False
    """
"*** YOUR CODE HERE ***"
if a == b: return a != c else: return a == c or b == c

Question 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of mor n below some number limit.

def sum_multiples(m, n, limit):
    """
    >>> sum_multiples(3, 5, 10)
    23
    >>> sum_multiples(3, 7, 1000)
    214216
    """
"*** YOUR CODE HERE ***"
count = 0 total = 0 while count < limit: if count % m == 0 or count % n == 0: total += count count += 1 return total

Question 6

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.

Hint: You can use // and % to separate a positive integer into its one's digit and the rest of its digits.

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
"""
"*** YOUR CODE HERE ***"
last = x % 10 val = x // 10 while x > 0 and last >= x % 10: last = x % 10 x = x // 10 return x == 0

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.

Higher order functions and Lambdas

Question 7: Intersect

Two functions intersect at an argument x if they return equal values. Implement intersects, which takes a one-argument functions f and a value x. It returns a function that takes another function g and returns whether f and g intersect at x.

def intersects(f, x):
    """Returns a function that returns whether f intersects g at x.

    >>> at_three = intersects(square, 3)
    >>> at_three(triple) # triple(3) == square(3)
    True
    >>> at_three(increment)
    False
    >>> at_one = intersects(identity, 1)
    >>> at_one(square)
    True
    >>> at_one(triple)
    False
    """
"*** YOUR CODE HERE ***"
def at_x(g): return f(x) == g(x) return at_x

Question 8: Smooth

The idea of smoothing a function is an important concept in signal processing. If f is a one-argument function and dx is some small number, then the smoothed version of f is the function whose value at a point x is the average of f(x - dx), f(x), and f(x + dx). Write a function smooth that takes as input a function f and a value to use for dx and returns a function that computes the smoothed version of f. Do not use any def statements inside of smooth; use lambda expressions instead.

def smooth(f, dx):
    """Returns the smoothed version of f, g where

    g(x) = (f(x - dx) + f(x) + f(x + dx)) / 3

    >>> square = lambda x: x ** 2
    >>> round(smooth(square, 1)(0), 3)
    0.667
    """
"*** YOUR CODE HERE ***"
return lambda x: (f(x - dx) + f(x) + f(x + dx)) / 3

Question 9

Draw the environment diagram for the following code:

x = 5
def compose1(f, g):
    def h(x):
        return f(g(x))
    return h
d = lambda y: y * x
x = 4
result = compose1(lambda z: z - 1, d)(3)

There are 5 frames total (including the Global frame). In addition, consider the following questions:

  1. In frame f1 (the frame for compose1), the parameter f points to a function object. What is the intrinsic name of that function object, and what frame is its parent?
  2. In frame f2, what name is the frame labeled with (h or λ)? Which frame is the parent of f2?
  3. In frame f3, what name is the frame labeled with (f, g, d, or λ)? Which frame is the parent of f3? In order to compute the return value y * x, in which frame does Python find x? What is that value of x?
  4. In frame f4, what name is the frame labeled with (f, g, d, or λ)? Which frame is the parent of f3?
  5. What value is the variable result bound to in the Global frame?

You can try out the environment diagram at tutor.cs61a.org.

  1. The intrinsic name of the function object that f points to is λ (specifically, the lambda whose parameter is z). The parent frame of this lambda is Global.
  2. f2 is labeled with the name h; the parent frame of f2 is f1, since that is where h is defined.
  3. f3 is labeled with the name λ (specifically, it is the λ that takes in a parameter y). The parent frame of f3 is Global, since that is where this lambda was defined (the line d = lambda y: y * x).
  4. f4 is labeled with the name λ (specifically, it is the λ that takes a parameter z). The parent frame of f4 is Global, since that is where the lambda is defined.

    You might think that the parent of f4 is f1, since lambda z: z - 1 is being passed into compose1. Remember, however, that operands are evaluated before the operator is applied (that is, before we create the frame f1). Since we are evaluating lambda z: z - 1 in the Global frame, its parent is Global.

  5. The variable result is bound to 11.