# Homework 2

*Due by 11:59pm on Monday, 2/6*

## Instructions

Download hw02.zip.
The homework problems can be found in the `problems`

directory and
the quiz problems can be found in the `vitamin`

directory. You must run
`python3 ok --submit`

twice: once inside the `problems`

directory, and once
inside the `vitamin`

directory.

**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:

## Vitamins

Vitamins are straightforward questions that are directly related to lecture
examples.
For these, run `ok`

from within the `vitamin`

directory.
Watch lecture, and you should be able to solve them.
**Vitamins should be completed alone.**

Several doctests refer to these one-argument functions:

```
def square(x):
return x * x
def triple(x):
return 3 * x
def identity(x):
return x
def increment(x):
return x + 1
```

### Question 1: Product

The `summation(term, n)`

function below adds up `term(1) + ... + term(n)`

Write a similar `product(n, term)`

function that returns ```
term(1) * ... *
term(n)
```

. Show how to define the
factorial function in terms of
`product`

. *Hint*: try using the `identity`

function for `factorial`

.

```
def product(n, term):
"""Return the product of the first n terms in a sequence.
n -- a positive integer
term -- a function that takes one argument
>>> product(3, identity) # 1 * 2 * 3
6
>>> product(5, identity) # 1 * 2 * 3 * 4 * 5
120
>>> product(3, square) # 1^2 * 2^2 * 3^2
36
>>> product(5, square) # 1^2 * 2^2 * 3^2 * 4^2 * 5^2
14400
"""
"*** YOUR CODE HERE ***"
# The identity function, defined using a lambda expression!
identity = lambda k: k
def factorial(n):
"""Return n factorial for n >= 0 by calling product.
>>> factorial(4)
24
>>> factorial(6)
720
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'factorial', ['Recursion', 'For', 'While'])
True
"""
"*** YOUR CODE HERE ***"
return _______
```

Use OK to test your code:

```
python3 ok -q product
python3 ok -q factorial
```

### Question 2: Make Adder with a Lambda

Implement the `make_adder`

function below using a single `return`

statement that returns the value of a `lambda`

expression.

```
def make_adder(n):
"""Return a function that takes an argument K and returns N + K.
>>> add_three = make_adder(3)
>>> add_three(1) + add_three(2)
9
>>> make_adder(1)(2)
3
"""
"*** YOUR CODE HERE ***"
return lambda ________________
```

Use OK to test your code:

`python3 ok -q make_adder`

## Required questions

For this set of problems, you must run `ok`

from within the `problems`

directory.
You may choose to work with a partner on these
questions.

### Question 3: Accumulate

Show that both `summation`

and `product`

are instances of a more
general function, called `accumulate`

:

```
from operator import add, mul
def accumulate(combiner, base, n, term):
"""Return the result of combining the first n terms in a sequence and base.
The terms to be combined are term(1), term(2), ..., term(n). combiner is a
two-argument commutative function.
>>> accumulate(add, 0, 5, identity) # 0 + 1 + 2 + 3 + 4 + 5
15
>>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
26
>>> accumulate(add, 11, 0, identity) # 11
11
>>> accumulate(add, 11, 3, square) # 11 + 1^2 + 2^2 + 3^2
25
>>> accumulate(mul, 2, 3, square) # 2 * 1^2 * 2^2 * 3^2
72
"""
"*** YOUR CODE HERE ***"
```

`accumulate(combiner, base, n, term)`

takes the following arguments:

`term`

and`n`

: the same arguments as in`summation`

and`product`

`combiner`

: a two-argument function that specifies how the current term combined with the previously accumulated terms. You may assume that`combiner`

is commutative, i.e.,`combiner(a, b) = combiner(b, a)`

.`base`

: value that specifies what value to use to start the accumulation.

For example, `accumulate(add, 11, 3, square)`

is

`11 + square(1) + square(2) + square(3)`

Implement `accumulate`

and show how `summation`

and `product`

can both be
defined as simple calls to `accumulate`

:

```
def summation_using_accumulate(n, term):
"""Returns the sum of term(1) + ... + term(n). The implementation
uses accumulate.
>>> summation_using_accumulate(5, square)
55
>>> summation_using_accumulate(5, triple)
45
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'summation_using_accumulate',
... ['Recursion', 'For', 'While'])
True
"""
"*** YOUR CODE HERE ***"
return _______
def product_using_accumulate(n, term):
"""An implementation of product using accumulate.
>>> product_using_accumulate(4, square)
576
>>> product_using_accumulate(6, triple)
524880
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'product_using_accumulate',
... ['Recursion', 'For', 'While'])
True
"""
"*** YOUR CODE HERE ***"
return _______
```

Use OK to test your code:

```
python3 ok -q accumulate
python3 ok -q summation_using_accumulate
python3 ok -q product_using_accumulate
```

### Question 4: Filtered Accumulate

Show how to extend the `accumulate`

function to allow for *filtering* the
results produced by its `term`

argument, by implementing the
`filtered_accumulate`

function in terms of `accumulate`

:

```
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(combiner, base, pred, n, term)`

takes
the following arguments:

`combiner`

,`base`

,`term`

and`n`

: the same arguments as`accumulate`

.`pred`

: a one-argument predicate function applied to the values of`term(k)`

,`k`

from 1 to`n`

. Only values for which`pred`

returns a true value are combined to form the result. If no values satisfy`pred`

, then`base`

is returned.

For example, `filtered_accumulate(add, 0, is_prime, 11, identity)`

would be

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

for a suitable 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 write any
loops or recursive calls to `filtered_accumulate`

.

Use OK to test your code:

`python3 ok -q filtered_accumulate`

### Question 5: Repeated

Implement a function `repeated`

so that
`repeated(f, n)(x)`

returns `f(f(...f(x)...))`

, where `f`

is applied
`n`

times. That is, `repeated(f, n)`

returns another function that can then be
applied to another argument. For example,
`repeated(square, 3)(42)`

evaluates to `square(square(square(42)))`

. Yes, it
makes sense to apply the function zero times! See if you can figure out a
reasonable function to return for that case.

```
def repeated(f, n):
"""Return the function that computes the nth application of f.
>>> add_three = repeated(increment, 3)
>>> add_three(5)
8
>>> repeated(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
243
>>> repeated(square, 2)(5) # square(square(5))
625
>>> repeated(square, 4)(5) # square(square(square(square(5))))
152587890625
>>> repeated(square, 0)(5)
5
"""
"*** YOUR CODE HERE ***"
```

For an extra challenge, try defining

`repeated`

using`compose1`

and your`accumulate`

function in a single one-line return statement.

```
def compose1(f, g):
"""Return a function h, such that h(x) = f(g(x))."""
def h(x):
return f(g(x))
return h
```

Use OK to test your code:

`python3 ok -q repeated`

## Extra questions

Extra questions are not worth extra credit and are entirely optional. They are designed to challenge you to think creatively!

## The Prisoner's Dilemma

The Prisoner's Dilemma is a famous game
(in the sense of game theory) originally posed by Merrill Flood and
Melvin Dresher and recast in its current form by Albert Tucker. Two
accused criminals are both given the following offer: you can either
*defect*, meaning that you witness against your partner in crime,
or you can *cooperate*, meaning that you refuse to witness
against him. If both of you cooperate, you both get a year in prison.
If you both defect, you both get two years in prison. But if only one
of you defects, the defector is set free and the cooperator gets three
years in prison. The accused are not allowed to confer and don't know
which decision the other makes until after both have decided.

If the game is played between two people only once, or if it is played a fixed number of times known in advance, the best playing strategy (for either player) turns out to be always to defect, so that both get two years. This despite the fact that if only both were to cooperate, they'd both get only one year. The problem, of course, is that if I cooperate, you can get off scot-free by defecting.

If, on the other hand, the game is to be played between two players
indefinitely---the *Iterated Prisoner's Dilemma*---so that each player
can take into account the previous behavior of the other and respond
to previous bad behavior, there is no fixed strategy that is optimal.

We'll define a *strategy* to be a function that takes a single argument
representing the other player's response in the last round (it is `None`

in the first round) and returns either `True`

(the player chooses to cooperate) or `False`

(the player chooses to defect).

### Question 6: Testing Strategies

Fill in the `simple_prisoner_tournament`

function below to run `N`

rounds of
the Prisoner's Dilemma using `strategy1`

and `strategy2`

as the
strategies for the two respective players. The value returned is a pair of
numbers: the total of all sentences for the first player and the
total for the second.

To return a pair of values in Python, say

`A`

and`B`

, write`return (A, B)`

Actually, you can write

`return A, B`

in the context of

`return`

, but in general, you'll want to surround tuples in parentheses, since comma has low precedence: (`1, 2 + 3, 4`

gives`(1, 5, 4)`

, while`(1, 2) + (3, 4)`

gives`(1, 2, 3, 4)`

.)

Also fill in the assignments defining the strategies `nice`

, `rat`

,
`tit_for_tat`

. `nice`

always cooperates; `rat`

always defects, and
`tit_for_tat`

cooperates initially and whenever the other player cooperates on
the previous round, and defects if the other player defects on the previous
round.

```
def simple_prisoner_tournament(N, strategy1, strategy2):
"""Run N rounds of the Prisoner's Dilemma where STRATEGY1 and STRATEGY2
are simple strategies used respectively by the two players. Return
a tuple (total1, total2) giving the cumulative sentences for the
players using STRATEGY1 and STRATEGY2, respectively.
>>> simple_prisoner_tournament(4, nice, nice)
(4, 4)
>>> simple_prisoner_tournament(5, rat, rat)
(10, 10)
>>> simple_prisoner_tournament(6, nice, rat)
(18, 0)
>>> simple_prisoner_tournament(2, rat, nice)
(0, 6)
>>> simple_prisoner_tournament(7, rat, tit_for_tat)
(12, 15)
>>> simple_prisoner_tournament(7, tit_for_tat, tit_for_tat)
(7, 7)
"""
"*** YOUR CODE HERE ***"
"*** YOUR CODE HERE ***"
nice = None # Replace
"*** YOUR CODE HERE ***"
rat = None # Replace
"*** YOUR CODE HERE ***"
tit_for_tat = None # Replace
```

Use OK to test your code:

`python3 ok -q simple_prisoner_tournament`

### Question 7: Enabling Fancy Strategies

Suppose that we'd like a strategy that takes into account more than just the other player's last response. Since only that last response gets passed to a player's strategy in any round, we have to arrange to keep track of previous reponses by some other means. Here we consider one technique.

Let's make strategies a bit fancier. Instead of returning just a boolean
value (`True`

or `False`

), these fancy strategies will return a pair
containing a boolean value *and* the strategy to be used for that player in
the next round.
Fill in the `fancy_prisoner_tournament`

function below
so that it takes two of these
fancy strategies while producing the same output as
`simple_prisoner_tournament`

.
[Since fancy strategies return two values, you'll need to split them out.
If `E`

is an expression that evaluates to a tuple of two values, then

`A, B = E`

assigns the first value of the tuple to `A`

and the second to `B`

.
For example `E`

could be
a function call to one of your fancy strategies.
]

Also, fill in the definitions of `nice2`

, `rat2`

, and `tit_for_tat2`

to
be fancy strategies corresponding to the simple strategies `nice`

, `rat`

, and
`tit_for_tat`

.

```
def fancy_prisoner_tournament(N, strategy1, strategy2):
"""Run N rounds of the Prisoner's Dilemma where STRATEGY1 and STRATEGY2
are fancy strategies used respectively by the two players. Return
a tuple (total1, total2) giving the cumulative sentences for the
players using STRATEGY1 and STRATEGY2, respectively.
>>> fancy_prisoner_tournament(4, nice2, nice2)
(4, 4)
>>> fancy_prisoner_tournament(5, rat2, rat2)
(10, 10)
>>> fancy_prisoner_tournament(6, nice2, rat2)
(18, 0)
>>> fancy_prisoner_tournament(2, rat2, nice2)
(0, 6)
>>> fancy_prisoner_tournament(7, rat2, tit_for_tat2)
(12, 15)
>>> fancy_prisoner_tournament(7, tit_for_tat2, tit_for_tat2)
(7, 7)
"""
"*** YOUR CODE HERE ***"
"*** YOUR CODE HERE ***"
nice2 = None # Replace
"*** YOUR CODE HERE ***"
rat2 = None # Replace
"*** YOUR CODE HERE ***"
tit_for_tat2 = None # Replace
```

Use OK to test your code:

`python3 ok -q fancy_prisoner_tournament`

### Question 8: Periodic Strategy

Fill in the definition of `make_periodic_strategy`

so that when called, it
returns a fancy strategy
that defects on rounds `K`

, `2K`

, `3K`

, etc. (numbering rounds
from 1) and otherwise cooperates. (`make_periodic_strategy`

, that is, is
*not* a strategy; it *creates* strategies.)

Keep all functions pure. Do *not* use the **global** or **nonlocal**
constructs in Python
or create lists or other data structures
that you modify (even if you know how). Figure out how to
do this problem so that `make_periodic_strategy`

and the strategies it
returns are all pure functions.

```
def make_periodic_strategy(K):
"""Returns a fancy strategy that defects every K times it is called,
and otherwise cooperates.
>>> s = make_periodic_strategy(4)
>>> fancy_prisoner_tournament(8, nice2, s)
(12, 6)
>>> fancy_prisoner_tournament(9, nice2, s)
(13, 7)
>>> fancy_prisoner_tournament(11, nice2, s)
(15, 9)
>>> fancy_prisoner_tournament(11, nice2, s) # No side-effects
(15, 9)
>>> fancy_prisoner_tournament(12, s, make_periodic_strategy(3))
(17, 14)
"""
def periodic(i):
"""Returns a fancy strategy that defects every K times it is called,
treating the first call as if it were the Ith call. Thus, if K is
3, then periodic(2) is a fancy strategy that first cooperates,
then defects, then cooperates twice, then defects, cooperates twice,
defects, etc."""
"*** YOUR CODE HERE ***"
return periodic(1)
```

Use OK to test your code:

`python3 ok -q make_periodic_strategy`