# Homework 3:

*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 [7] 6 5 4 3 2 1 [0] 1 2 [3] 2 1 0 [-1] 0 1 2 3 4 [5] [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`