## Solution Files

You can find the solutions in the hw02.py and vitamin02.py files.

## 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
"""
total, k = 1, 1
while k <= n:
total, k = term(k) * total, k + 1
# 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
"""
return product(n, identity)``````

Use OK to test your code:

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

The `product` function has similar structure to `summation`, but starts accumulation with the value `total=1`. Factorial is a `product` with the identity function as `term`.

### 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.

9
3
"""
return lambda k: n + k``````

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
"""
total, k = base, 1
while k <= n:
total, k = combiner(total, term(k)), k + 1

# Recursive solution
# if n == 0:
#     return base
# else:
#     return combiner(term(n), accumulate(combiner, base, n-1, term))

# Recursive solution using base to keep track of total
# if n == 0:
#     return base
# else:
#     return accumulate(combiner, combiner(base, term(n)), n-1, term)
``````

`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
"""
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
"""
return accumulate(mul, 1, n, term)``````

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):
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(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.

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
"""
g = identity
while n > 0:
g = compose1(f, g)
n = n - 1
return g

# Alternatives

def repeated2(f, n):
def h(x):
k = 0
while k < n:
x, k = f(x), k + 1
return x
return h

def repeated3(f, n):
return accumulate(compose1, lambda x: x, n, lambda k: f)``````

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

There are many correct ways to implement `repeated`. The first solution above creates a new function in every iteration of the `while` statement (via `compose1`). The second solution shows that it is also possible to implement `repeated` by creating only a single new function. That function repeatedly applies `f`.

`repeated` can also be implemented compactly using `accumulate`, the third solution.

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

total1 = total2 = 0
prev1 = prev2 = None
while N > 0:
r1 = strategy1(prev2)
r2 = strategy2(prev1)
if r1 and r2:
total1 += 1
total2 += 1
elif not (r1 or r2):
total1 += 2
total2 += 2
elif r1:
total1 += 3
else:
total2 += 3
N -= 1
prev1, prev2 = r1, r2
nice = lambda x: True
rat = lambda x: False
tit_for_tat = lambda prev: True if prev is None else prev``````

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)
"""
total1 = total2 = 0
prev1 = prev2 = None
while N > 0:
r1, strategy1 = strategy1(prev2)
r2, strategy2 = strategy2(prev1)
if r1 and r2:
total1 += 1
total2 += 1
elif not (r1 or r2):
total1 += 2
total2 += 2
elif r1:
total1 += 3
else:
total2 += 3
N -= 1
prev1, prev2 = r1, r2
nice2 = lambda x: (True, nice2)
rat2 = lambda x: (False, rat2)
tit_for_tat2 = lambda prev: (True, tit_for_tat2) if prev is None else (prev, tit_for_tat2)``````

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."""
def strat(prev):
if i % K == 0:
return False, periodic(i + 1)
else:
return True, periodic(i + 1)
return strat    return periodic(1)``````

Use OK to test your code:

``python3 ok -q make_periodic_strategy``