Homework 2 | CS 61A Spring 2017

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:

Section 1.6

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