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:])

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)

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.)

grid

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)

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