Due by 11:59pm on Tuesday, July 7.

Starter Files

Download lab03.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on okpy.org.

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.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

def fib(n):
    if n == 0 or n == 1:
        return n
    return fib(n - 1) + fib(n - 2)

Required Questions

What Would Python Display?

Q1: WWPD: Recursion

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

python3 ok -q recursion-wwpd -u

For all WWPD questions, type Function if you believe the answer is <function...>, Error if it errors, Infinite if there is an infinite loop or infinite recursion, and Nothing if nothing is displayed.

>>> def f(a, b):
...     if a > b:
...     	return f(a - 3, 2 * b)
...     elif a < b:
...		return f(b // 2, a)
...     else:
...     	return b
>>> f(2, 2)
______
2
>>> f(7, 4)
______
4
>>> f(2, 28)
______
8
>>> f(-1, -3)
______
Infinite

Q2: WWPD: Journey to the Center of the Earth

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

python3 ok -q sr-wwpd -u

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

>>> def crust():
...     print("70km")
...     def mantle():
...          print("2900km")
...          def core():
...               print("5300km")
...               return mantle()
...          return core
...     return mantle
>>> drill = crust
>>> drill = drill()
______
70km
>>> drill = drill()
______
2900km
>>> drill = drill()
______
5300km
2900km
>>> drill()
______
5300km
2900km
Function

Coding Practice

Q3: Pascal's Triangle

Here's a part of the Pascal's trangle:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

Every number in Pascal's triangle is defined as the sum of the item above it and the item that is directly to the upper left of it. Use 0 if the entry is empty. Define the procedure pascal(row, column) which takes a row and a column, and finds the value at that position in the triangle. Rows and columns are zero-indexed; that is, the first row is row 0 instead of 1.

def pascal(row, column):
    """Returns a number corresponding to the value at that location
    in Pascal's Triangle.
    >>> pascal(0, 0)
    1
    >>> pascal(0, 5)	# Empty entry; outside of Pascal's Triangle
    0
    >>> pascal(3, 2)	# Row 4 (1 3 3 1), 3rd entry
    3
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q pascal

Q4: Repeated, repeated

In Homework 2 you encountered the repeated function, which takes arguments f and n and returns a function equivalent to the nth repeated application of f. This time, we want to write repeated recursively. You'll want to use compose1, given below for your convenience:

def compose1(f, g):
    """"Return a function h, such that h(x) = f(g(x))."""
    def h(x):
        return f(g(x))
    return h

def repeated(f, n):
    """Return the function that computes the nth application of func (recursively!).

    >>> add_three = repeated(lambda x: x + 1, 3)
    >>> add_three(5)
    8
    >>> square = lambda x: x ** 2
    >>> repeated(square, 2)(5) # square(square(5))
    625
    >>> repeated(square, 4)(5) # square(square(square(square(5))))
    152587890625
    >>> repeated(square, 0)(5)
    5
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(HW_SOURCE_FILE, 'repeated',
    ...       ['For', 'While'])
    True
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q repeated

Q5: Num eights

Write a recursive function num_eights that takes a positive integer x and returns the number of times the digit 8 appears in x. Use recursion - the tests will fail if you use any assignment statements.

def num_eights(x):
    """Returns the number of times 8 appears as a digit of x.

    >>> num_eights(3)
    0
    >>> num_eights(8)
    1
    >>> num_eights(88888888)
    8
    >>> num_eights(2638)
    1
    >>> num_eights(86380)
    2
    >>> num_eights(12345)
    0
    >>> from construct_check import check
    >>> # ban all assignment statements
    >>> check(HW_SOURCE_FILE, 'num_eights',
    ...       ['Assign', 'AugAssign'])
    True
    """
    "*** YOUR CODE HERE ***"

Watch the hints video below for somewhere to start:

Use Ok to test your code:

python3 ok -q num_eights

Q6: Ping-pong

The ping-pong sequence counts up starting from 1 and is always either counting up or counting down. At element k, the direction switches if k is a multiple of 8 or contains the digit 8. The first 30 elements of the ping-pong sequence are listed below, with direction swaps marked using brackets at the 8th, 16th, 18th, 24th, and 28th elements:

Implement a function pingpong that returns the nth element of the ping-pong sequence without using any assignment statements.

You may use the function num_eights, which you defined in the previous question.

Use recursion - the tests will fail if you use any assignment statements.

Hint: If you're stuck, first try implementing pingpong using assignment statements and a while statement. Then, to convert this into a recursive solution, write a helper function that has a parameter for each variable that changes values in the body of the while loop.

def pingpong(n):
    """Return the nth element of the ping-pong sequence.

    >>> pingpong(8)
    8
    >>> pingpong(10)
    6
    >>> pingpong(15)
    1
    >>> pingpong(21)
    -1
    >>> pingpong(22)
    -2
    >>> pingpong(30)
    -2
    >>> pingpong(68)
    0
    >>> pingpong(69)
    -1
    >>> pingpong(80)
    0
    >>> pingpong(81)
    1
    >>> pingpong(82)
    0
    >>> pingpong(100)
    -6
    >>> from construct_check import check
    >>> # ban assignment statements
    >>> check(HW_SOURCE_FILE, 'pingpong', ['Assign', 'AugAssign'])
    True
    """
    "*** YOUR CODE HERE ***"

Watch the hints video below for somewhere to start:

Use Ok to test your code:

python3 ok -q pingpong