# Homework 3: hw03.zip

Due by 11:59pm on Thursday 9/13

## Instructions

Download hw03.zip. Inside the archive, you will find a file called hw03.py, along with a copy of the `ok` autograder.

Submission: When you are done, submit with ```python3 ok --submit```. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on okpy.org. See Lab 0 for more instructions on submitting assignments.

Using Ok: If you have any questions about using Ok, please refer to this guide.

Readings: You might find the following references useful:

Grading: Homework is graded based on effort, not correctness. However, there is no partial credit; you must show substantial effort on every problem to receive any points.

## Required questions

### Q1: Has Seven

Write a recursive function `has_seven` that takes a positive integer `n` and returns whether `n` contains the digit `7`. Use recursion - the tests will fail if you use any assignment statements.

``````def has_seven(k):
"""Returns True if at least one of the digits of k is a 7, False otherwise.

>>> has_seven(3)
False
>>> has_seven(7)
True
>>> has_seven(2734)
True
>>> has_seven(2634)
False
>>> has_seven(734)
True
>>> has_seven(7777)
True
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'has_seven',
...       ['Assign', 'AugAssign'])
True
"""
"*** YOUR CODE HERE ***"
``````

Use Ok to test your code:

``python3 ok -q has_seven``

### Q2: 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 7 or contains the digit 7. The first 30 elements of the ping-pong sequence are listed below, with direction swaps marked using brackets at the 7th, 14th, 17th, 21st, 27th, and 28th elements:

``1 2 3 4 5 6  6 5 4 3 2 1  1 2  2 1 0 [-1] 0 1 2 3 4   5 6``

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

You may use the function `has_seven` from the previous problem.

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(7)
7
>>> pingpong(8)
6
>>> pingpong(15)
1
>>> pingpong(21)
-1
>>> pingpong(22)
0
>>> pingpong(30)
6
>>> pingpong(68)
2
>>> pingpong(69)
1
>>> pingpong(70)
0
>>> pingpong(71)
1
>>> pingpong(72)
0
>>> pingpong(100)
2
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'pingpong', ['Assign', 'AugAssign'])
True
"""
"*** YOUR CODE HERE ***"
``````

Use Ok to test your code:

``python3 ok -q pingpong``
Several doctests refer to these functions:
``````from operator import add, mul, sub

square = lambda x: x * x

identity = lambda x: x

triple = lambda x: 3 * x

increment = lambda x: x + 1``````

### Q3: Filtered Accumulate

Extend the `accumulate` function from homework 2 to allow for filtering the results produced by its `term` argument by filling in the implementation for the `filtered_accumulate` function:

``````def filtered_accumulate(combiner, base, pred, n, term):
"""Return the result of combining the terms in a sequence of N terms
that satisfy the predicate pred. combiner is a two-argument function.
If v1, v2, ..., vk are the values in term(1), term(2), ..., term(N)
that satisfy pred, then the result is
base combiner v1 combiner v2 ... combiner vk
(treating combiner as if it were a binary operator, like +). The
implementation uses accumulate.

>>> filtered_accumulate(add, 0, lambda x: True, 5, identity)  # 0 + 1 + 2 + 3 + 4 + 5
15
>>> filtered_accumulate(add, 11, lambda x: False, 5, identity) # 11
11
>>> filtered_accumulate(add, 0, odd, 5, identity)   # 0 + 1 + 3 + 5
9
>>> filtered_accumulate(mul, 1, greater_than_5, 5, square)  # 1 * 9 * 16 * 25
3600
>>> # Do not use while/for loops or recursion
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'filtered_accumulate',
...       ['While', 'For', 'Recursion'])
True
"""
def combine_if(x, y):
"*** YOUR CODE HERE ***"
return accumulate(combine_if, base, n, term)

def odd(x):
return x % 2 == 1

def greater_than_5(x):
return x > 5``````

`filtered_accumulate` has the following parameters:

• `combiner`, `base`, `term` and `n`: the same arguments as `accumulate`.
• `pred`: a one-argument predicate function applied to the values of `term(k)` for each `k` from 1 to `n`. Only values for which `pred` returns a true value are included in the accumulated total. If no values satisfy `pred`, then `base` is returned.

For example, the result of ```filtered_accumulate(add, 0, is_prime, 11, identity)``` is

``0 + 2 + 3 + 5 + 7 + 11``

for a valid definition of `is_prime`.

Implement `filtered_accumulate` by defining the `combine_if` function. Exactly what this function does is something for you to discover. Do not use any loops or make any recursive calls to `filtered_accumulate`.

Hint: The order in which you pass the arguments to `combiner` in your solution to `accumulate` matters here.

Use Ok to test your code:

``python3 ok -q filtered_accumulate``