from functools import lru_cache
memoize = lru_cache(None)

goal = 21

def play(strategy0, strategy1):
    """ Return the index of the winner.
    >>> play(constant(1), constant(1))
    1
    >>> play(constant(1), constant(2))
    0
    >>> play(constant(2), constant(2))
    1
    """
    return winner(0, strategy0, strategy1)

@memoize
def winner(n, current_strat, other_strat):
    """Return the index of the winner, starting at n."""
    if n >= goal:
        return 0
    else:
        return 1- winner(n + current_strat(n), other_strat, current_strat)

@memoize
def optimal(n, other):
    choice = 2
    future = lambda n: optimal(n, other)
    while choice <= 4:
        if winner(n + choice, other, future) == 1:
            return choice
        choice += 1
    return 2 # Give up :(((((

def print_perfect():
    n = 0
    perfect = lambda n: optimal(n, perfect)
    while n < goal:
        if winner(n, perfect, perfect) == 0:
            print("Perfect play from", n, "wins with", perfect(n))
        else:
            print("Perfect play from", n, "loses!")
        n += 1


def constant(k):
    return lambda n: k


@memoize
def fib(n):
    if n==0 or n==1:
        return n
    else:
        return fib(n-1) + fib(n-2)

@memoize
def at_least(k, n):
    """Return chance of k points in n rolls."""
    if n==0 and k <= 0:
        return 1
    elif n == 0:
        return 0
    else:
        chance, outcome = 0, 2
        while outcome <= 6:
            chance += 1/6*at_least(k-outcome, n -1)
            outcome += 1
        return chance