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
andn
: the same arguments as insummation
andproduct
combiner
: a two-argument function that specifies how the current term combined with the previously accumulated terms. You may assume thatcombiner
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
andn
: the same arguments asaccumulate
.pred
: a one-argument predicate function applied to the values ofterm(k)
,k
from 1 ton
. Only values for whichpred
returns a true value are combined to form the result. If no values satisfypred
, thenbase
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
usingcompose1
and youraccumulate
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
andB
, writereturn (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