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]
"""

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

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
"""
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

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``