Due by 11:59pm on Tuesday, June 30.

Starter Files

Download lab02.zip.

Attendance

You need to submit the lab problems in addition to attending to get credit for lab.

If you miss lab for a good reason (such as sickness or a scheduling conflict) or you don't get checked in for some reason, email cs61a@berkeley.edu within one week to receive attendance credit.

Topics

Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.

1 / 0

True or 1 / 0

def square(x):
    return x * x

def scale(f, x, k):
    """ Returns the result of f(x) scaled by k. """
    return k * f(x)

>>> scale(square, 3, 2) # Double square(3)
18
>>> scale(square, 2, 5) # 5 times 2 squared
20

>>> scale(lambda x: x + 10, 5, 2)
30

def multiply_by(m):
    def multiply(n):
        return n * m
    return multiply

>>> multiply_by(3)
<function multiply_by.<locals>.multiply at ...>
>>> multiply(4)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
NameError: name 'multiply' is not defined

>>> times_three = multiply_by(3) # Assign the result of the call expression to a name
>>> times_three(5) # Call the inner function with its new name
15
>>> multiply_by(3)(10) # Chain together two call expressions
30

lambda <parameters>: <return expression>

# A lambda expression by itself does not alter
# the environment
lambda x: x * x

# We can assign lambda functions to a name
# with an assignment statement
square = lambda x: x * x
square(3)

# Lambda expressions can be used as an operator
# or operand
negate = lambda f, x: -f(x)
negate(lambda x: x * x, 3)

def square(x):
    return x * x

# A function created by a def statement
# can be referred to by its intrinsic name
square(3)

Required Questions

What Would Python Display?

Important: For all WWPD questions, type Function if you believe the answer is <function...>, Error if it errors, and Nothing if nothing is displayed.

Q1: WWPD: The Truth Will Prevail

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q short-circuit -u
Copy
✂️

>>> True and 13
______
13
>>> False or 0
______
0
>>> not 10
______
False
>>> not None
______
True

>>> True and 1 / 0
______
Error (ZeroDivisionError)
>>> True or 1 / 0
______
True
>>> -1 and 1 > 0
______
True
>>> -1 or 5
______
-1
>>> (1 + 1) and 1
______
1
>>> print(3) or ""
______
3
''

>>> def f(x):
...     if x == 0:
...         return "zero"
...     elif x > 0:
...         return "positive"
...     else:
...         return ""
>>> 0 or f(1)
______
'positive'
>>> f(0) or f(-1)
______
'zero'
>>> f(0) and f(-1)
______
''

Q2: WWPD: Higher-Order Functions

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q hof-wwpd -u
Copy
✂️

>>> def cake():
...    print('beets')
...    def pie():
...        print('sweets')
...        return 'cake'
...    return pie
>>> chocolate = cake()
______
beets
>>> chocolate
______
Function
>>> chocolate()
______
sweets
'cake'
>>> more_chocolate, more_cake = chocolate(), cake
______
sweets
>>> more_chocolate
______
'cake'
>>> def snake(x, y):
...    if cake == more_cake:
...        return chocolate
...    else:
...        return x + y
>>> snake(10, 20)
______
Function
>>> snake(10, 20)()
______
sweets
'cake'
>>> cake = 'cake'
>>> snake(10, 20)
______
30

Q3: WWPD: Lambda

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q lambda -u
Copy
✂️

As a reminder, the following two lines of code will not display any output in the interactive Python interpreter when executed:

>>> x = None
>>> x
>>>

>>> lambda x: x  # A lambda expression with one parameter x
______
<function <lambda> at ...>
>>> a = lambda x: x  # Assigning the lambda function to the name a
>>> a(5)
______
5
>>> (lambda: 3)()  # Using a lambda expression as an operator in a call expression.
______
3
>>> b = lambda x, y: lambda: x + y  # Lambdas can return other lambdas!
>>> c = b(8, 4)
>>> c
______
<function <lambda> at ...
>>> c()
______
12
>>> d = lambda f: f(4)  # They can have functions as arguments as well.
>>> def square(x):
...     return x * x
>>> d(square)
______
16

>>> higher_order_lambda = lambda f: lambda x: f(x)
>>> g = lambda x: x * x
>>> higher_order_lambda(2)(g)  # Which argument belongs to which function call?
______
Error
>>> higher_order_lambda(g)(2)
______
4
>>> call_thrice = lambda f: lambda x: f(f(f(x)))
>>> call_thrice(lambda y: y + 1)(0)
______
3
>>> print_lambda = lambda z: print(z)  # When is the return expression of a lambda expression executed?
>>> print_lambda
______
Function
>>> one_thousand = print_lambda(1000)
______
1000
>>> one_thousand # What did the call to print_lambda return?
______
# print_lambda returned None, so nothing gets displayed

Coding Practice

Q4: Composite Identity Function

Write a function that takes in two single-argument functions, f and g, and returns another function that has a single parameter x. The returned function should return True if f(g(x)) is equal to g(f(x)) and False otherwise. You can assume the output of g(x) is a valid input for f and vice versa.

def composite_identity(f, g):
    """
    Return a function with one parameter x that returns True if f(g(x)) is
    equal to g(f(x)). You can assume the result of g(x) is a valid input for f
    and vice versa.

    >>> add_one = lambda x: x + 1        # adds one to x
    >>> square = lambda x: x**2          # squares x [returns x^2]
    >>> b1 = composite_identity(square, add_one)
    >>> b1(0)                            # (0 + 1) ** 2 == 0 ** 2 + 1
    True
    >>> b1(4)                            # (4 + 1) ** 2 != 4 ** 2 + 1
    False
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q composite_identity
Copy
✂️

Q5: Count Cond

Consider the following implementations of count_fives and count_primes which use the sum_digits and is_prime functions, which are implemented below:

def count_fives(n):
    """Return the number of values i from 1 to n (including n)
    where sum_digits(n * i) is 5.

    >>> count_fives(10)  # Among 10, 20, 30, ..., 100, only 50 (10 * 5) has digit sum 5
    1
    >>> count_fives(50)  # 50 (50 * 1), 500 (50 * 10), 1400 (50 * 28), 2300 (50 * 46)
    4
    """
    i = 1
    count = 0
    while i <= n:
        if sum_digits(n * i) == 5:
            count += 1
        i += 1
    return count

def count_primes(n):
    """Return the number of prime numbers up to and including n.

    >>> count_primes(6)   # 2, 3, 5
    3
    >>> count_primes(13)  # 2, 3, 5, 7, 11, 13
    6
    """
    i = 1
    count = 0
    while i <= n:
        if is_prime(i):
            count += 1
        i += 1
    return count

The implementations look quite similar! Generalize this logic by writing a function count_cond, which takes in a two-argument predicate function condition(n, i). count_cond returns a one-argument function that takes in n, which counts all the numbers from 1 to n that satisfy condition when called.

Note: When we say condition is a predicate function, we mean that it is a function that will return True or False.

def sum_digits(y):
    """Return the sum of the digits of non-negative integer y."""
    total = 0
    while y > 0:
        total, y = total + y % 10, y // 10
    return total

def is_prime(n):
    """Return whether positive integer n is prime."""
    if n == 1:
        return False
    k = 2
    while k < n:
        if n % k == 0:
            return False
        k += 1
    return True

def count_cond(condition):
    """Returns a function with one parameter N that counts all the numbers from
    1 to n that satisfy the two-argument predicate function Condition, where
    the first argument for condition is n and the second argument is the
    number from 1 to n.

    >>> count_fives = count_cond(lambda n, i: sum_digits(n * i) == 5)
    >>> count_fives(10)   # 50 (10 * 5)
    1
    >>> count_fives(50)   # 50 (50 * 1), 500 (50 * 10), 1400 (50 * 28), 2300 (50 * 46)
    4

    >>> is_i_prime = lambda n, i: is_prime(i) # need to pass 2-argument function into count_cond
    >>> count_primes = count_cond(is_i_prime)
    >>> count_primes(2)    # 2
    1
    >>> count_primes(3)    # 2, 3
    2
    >>> count_primes(4)    # 2, 3
    2
    >>> count_primes(5)    # 2, 3, 5
    3
    >>> count_primes(20)   # 2, 3, 5, 7, 11, 13, 17, 19
    8
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q count_cond
Copy
✂️

Q6: String Transformer

Using a lambda expression, complete the following function. Your function should only contain a return statement.

from operator import add, sub

def caesar_generator(num, op):
    """Returns a one-argument Caesar cipher function. The function should "rotate" a
    letter by an integer amount 'num' using an operation 'op' (either add or
    sub).

    You may use the provided `letter_to_num` and `num_to_letter` functions,
    which will map all lowercase letters a-z to 0-25 and all uppercase letters
    A-Z to 26-51.

    >>> letter_to_num('a')
    0
    >>> letter_to_num('c')
    2
    >>> num_to_letter(3)
    'd'

    >>> caesar2 = caesar_generator(2, add)
    >>> caesar2('a')
    'c'
    >>> brutus3 = caesar_generator(3, sub)
    >>> brutus3('d')
    'a'
    """
    "*** YOUR CODE HERE ***"
    return ______

Use Ok to test your code:

python3 ok -q caesar_generator
Copy
✂️

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.

Correctly completing all questions is worth one point. Please ensure your TA has taken your attendance before leaving.

Optional Questions

These questions are optional. If you don't complete them, you will still receive credit for this assignment. They are great practice, so do them anyway!

Q7: Palindrome

A number is considered a palindrome if it reads the same forwards and backwards. Fill in the blanks '_' to help determine if a number is a palindrome. In the spirit of exam style questions, please do not edit any parts of the function other than the blanks.

def is_palindrome(n):
    """
    Fill in the blanks '_____' to check if a number
    is a palindrome.

    >>> is_palindrome(12321)
    True
    >>> is_palindrome(42)
    False
    >>> is_palindrome(2015)
    False
    >>> is_palindrome(55)
    True
    """
    x, y = n, 0
    f = lambda: _____
    while x > 0:
        x, y = _____, f()
    return y == n

Use Ok to test your code:

python3 ok -q is_palindrome
Copy
✂️