Starter Files

Download lab07.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. See this article for more instructions on okpy and submitting assignments.

• Submit the lab07.py file to ok.

Questions

Question 1: Filter

Write the recursive version of the function filter which takes

• filter - a one-argument function that returns True if the argument passed in should be included in the list, and False otherwise.
• s - a sequence of values

def filter(f, seq):
    """Filter a sequence to only contain values allowed by filter.

    >>> def is_even(x):
    ...     return x % 2 == 0
    >>> def divisible_by5(x):
    ...     return x % 5 == 0
    >>> filter(is_even, [1,2,3,4])
    [2, 4]
    >>> filter(divisible_by5, [1, 4, 9, 16, 25, 100])
    [25, 100]
    """
    "*** YOUR CODE HERE ***"
    
    if seq == []:
        return seq
    if f(seq[0]):
        return [seq[0]] + filter(f, seq[1:])
    return filter(f, seq[1:])

Toggle Solution

Use OK to test your code:

python3 ok -q filter

Question 2: Sum Digit Differences

Write the recursive function sum_diffs which takes in n, a number, and returns the sum of the differences between adjacent digits in the number n.

def sum_diffs(n):
    """ Return the sum of the differences between adjacent digits in the number n.

    >>> sum_diffs(8)
    0
    >>> sum_diffs(154) # 4 + 1 = 5
    5
    >>> sum_diffs(12321) # 1 + 1 + 1 + 1
    4
    >>> sum_diffs(7351) # 4 + 2 + 4
    10
    """
    "*** YOUR CODE HERE ***"
    if n < 10:
        return 0
    else:
        dif = abs(n % 10 - (n // 10)% 10)
        return dif + sum_diffs(n // 10)

Toggle Solution

Use OK to test your code:

python3 ok -q sum_diffs

Question 3: Insect Combinatorics

Consider an insect in an M by N grid. The insect starts at the bottom left corner, (0, 0), and wants to end up at the top right corner, (M-1, N-1). The insect is only capable of moving right or up. Write a function paths that takes a grid length and width and returns the number of different paths the insect can take from the start to the goal. (There is a closed-form solution to this problem, but try to answer it procedurally using recursion.)

For example, the 2 by 2 grid has a total of two ways for the insect to move from the start to the goal. For the 3 by 3 grid, the insect has 6 diferent paths (only 3 are shown above).

def paths(m, n):
    """Return the number of paths from one corner of an
    M by N grid to the opposite corner.

    >>> paths(2, 2)
    2
    >>> paths(5, 7)
    210
    >>> paths(117, 1)
    1
    >>> paths(1, 157)
    1
    """
    "*** YOUR CODE HERE ***"
    if m == 1 or n == 1:
        return 1
    return paths(m - 1, n) + paths(m, n - 1)

Toggle Solution

Use OK to test your code:

python3 ok -q paths

Required Practice Problems Open in a new window

These questions are a mix of Parsons Problems, Code Tracing questions, and Code Writing questions.

You should answer the questions on the study tool, and once you are completed with the required problems on the tool for that week, you will receive an okpy secret key that you will need to submit to show completion of the practice problems on the tool. Copy paste that secret key into the lab07_practice_problems function at the bottom, along with your okpy email in the first line. Then, to test that you've correctly completed the problem, you can run the following command.

Use OK to test your code:

python3 ok -q practice_problems

These cover some similar material to lab, so can be helpful to further review or try to learn the material. Unlike lab and homework, after you've worked for long enough and tested your code enough times on any of these questions, you'll have the option to view an instructor solution. You'll unlock each question one at a time, either by correctly answering the previous question or by viewing an instructor solution.

---

Submit

Make sure to submit this assignment by running:

python3 ok --submit