# Homework 3 Solutions

## Solution Files

You can find solutions for all questions in hw03.py.

## 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
"""
if k % 10 == 7:
return True
elif k < 10:
return False
else:
return has_seven(k // 10)
```

Use Ok to test your code:

`python3 ok -q has_seven`

The equivalent iterative version of this problem might look something like this:

```
while n > 0:
if n % 10 == 7:
return True
n = n // 10
```

The main idea is that we check each digit for a seven. The recursive solution is similar, except that you depend on the recursive call to check the rest of the number for a seven. All that's left is to check the last digit in the current step.

### 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
"""
def helper(result, i, step):
if i == n:
return result
elif i % 7 == 0 or has_seven(i):
return helper(result - step, i + 1, -step)
else:
return helper(result + step, i + 1, step)
return helper(1, 1, 1)
# Alternate solution 1
def pingpong_next(x, i, step):
if i == n:
return x
return pingpong_next(x + step, i + 1, next_dir(step, i+1))
def next_dir(step, i):
if i % 7 == 0 or has_seven(i):
return -step
return step
return pingpong_next(1, 1, 1)
# Alternate solution 2
def pingpong(n):
if n <= 7:
return n
return direction(n) + pingpong(n-1)
def direction(n):
if n < 7:
return 1
if (n-1) % 7 == 0 or has_seven(n-1):
return -1 * direction(n-1)
return direction(n-1)
```

Use Ok to test your code:

`python3 ok -q pingpong`

This is a fairly involved recursion problem, which we will first solve through iteration and then convert to a recursive solution.

Note that at any given point in the sequence, we need to keep track of the
current *value* of the sequence (this is the value that might be output)
as well as the current *index* of the sequence (how many items we have
seen so far, not actually output).

For example, 14th element has *value* 0, but it's the 14th *index* in
the sequence. We will refer to the value as `x`

and the index as `i`

. An
iterative solution may look something like this:

```
def pingpong(n):
i = 1
x = 1
while i < n:
x += 1
i += 1
return x
```

Hopefully, it is clear to you that this has a big problem. This doesn't
account for changes in directions at all! It will work for the first seven
values of the sequence, but then fail after that. To fix this, we can add
in a check for direction, and then also keep track of the current
direction to make our lives a bit easier (it's possible to compute the
direction from scratch at each step, see the `direction`

function in the
alternate solution).

```
def pingpong(n):
i = 1
x = 1
is_up = True
while i < n:
is_up = next_dir(...)
if is_up:
x += 1
else:
x -= 1
i += 1
return x
```

All that's left to do is to write the `next_dir`

function, which will take
in the *current direction* and *index* and then tell us what direction to
go in next (which could be the same direction):

```
def next_dir(is_up, i):
if i % 7 == 0 or has_seven(i):
return not is_up
return is_up
```

There's a tiny optimization we can make here. Instead of calculating an
increment based on the value of `is_up`

, we can make it directly store the
direction of change into the variable (`next_dir`

is also updated, see the
solution for the new version):

```
def pingpong(n):
i = 1
x = 1
step = 1
while i < n:
step = next_dir(step, i)
x += step
i += 1
return x
```

This will work, but it uses assignment. To convert it to an equivalent recursive version without assignment, make each local variable into a parameter of a new helper function, and then add an appropriate base case. Lastly, we seed the helper function with appropriate starting values by calling it with the values we had in the iterative version.

You should be able to convince yourself that the version of `pingpong`

in
the solutions has the same logic as the iterative version of `pingpong`

above.

Video walkthrough: https://youtu.be/74gwPjgrN_k

```
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):
if pred(y):
return combiner(x, y)
else:
return x 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`

The implementation of `filtered_accumulate`

will depend on how you implemented
your `accumulate`

. This is because the `combine_if`

function we use will always
keep the first item (`x`

), and conditionally join with the second item (`y`

).

The idea behind this combiner goes something like this:

`x`

represents all the things we have successfully combined so far.- If we want to include
`y`

in our combinations, then we return`combiner(x, y)`

. - On the other hand, if we
*don't*want to include`y`

in our combinations, then we don't want to discard our progress so far, so we will just return`x`

as the "result" of combining`x`

and`y`

.