# Hog roll dice

def six_sided(outcome):
    """ The probability of getting outcome from a 6-sided dice"
    """
    if 1 <= outcome <= 6:
        return 1/6
    else:
        return 0

dice = six_sided

def roll_dice(total, n):
    """ The probability of scoring total from rolling n dice"""
    if total == 1:
        return roll_a_one(n)
    else:
        return roll_no_ones(total, n)

def roll_a_one(n):
    """ Probability of rolling a one from rolling n dice
    >>> roll_a_one(0)
    0
    >>> roll_a_one(1)
    1/6
    dice(1)
    >>> roll_a_one(2)
    dice(1) + (first dice is not 1)* (second dice is 1)
    dice(1) + (1 - dice(1)) * roll_a_one(1)
    >>> roll_a_one(3)
    dice(1) + (1 - dice(1))* (roll_a_one(2))
    """
    if n == 0:
        return 0
    else:
        return dice(1) + (1-dice(1))*roll_a_one(n-1)

def roll_no_ones(total, n):
    """ Probability of getting total by rolling n dice, excluding cases where we roll ones"""
    if total == 0 and n == 0:
        return 1
    elif n == 0:
        return 0
    else:
        probability = 0
        first_outcome = 2
        while first_outcome <= 6:
            # increment the probability with the chance of getting total-first_outcome from the other dice
            probability += dice(first_outcome) * roll_no_ones(total - first_outcome, n - 1) 
            first_outcome += 1  
        return probability


# Hog end game

def roll_at_least(k, n):
    """ the probability of getting at least k points from rolling n dice"""
    score = k
    max_score = 6*n
    chance_at_least_k = 0
    while score <= max_score:
        chance_at_least_k += roll_dice(score, n)
        score += 1
    return chance_at_least_k

# Twenty-one

goal = 21

def play(strategy0, strategy1):
    """ Play twenty-one and return the index of the winner. """
    n = 0
    who = 0
    while n < goal:
        current_strategy = strategy1 if who else strategy0
        n += current_strategy(n)
        who = 1 - who
    return who

def constant(k):
    return lambda n: k

def winner(n, strat, other):
    """ Return the index of the winner starting at score n. """
    if n >= goal:
        return 0
    else:
        return 1 - winner(n + strat(n), other, strat)

def optimal(n, other_strategy):
    """ Return the optimal twenty-one strategy against other_strategy"""
    future_optimal = lambda future_n: optimal(future_n, other_strategy)

    choice = 1
    while choice <= 3:
        if winner(n + choice, other_strategy, future_optimal) == 1:
            return choice
        choice = choice + 1
    # Nothing worked so give up
    return 1  

def print_perfect():
    n = 0
    perfect = lambda n: optimal(n, perfect)
    while n < goal:
        if winner(n, perfect, perfect) == 0:
            print("Perfect play starting at", n, "wins with choice", perfect(n))
        else:
            print("Perfect play starting at", n, "cannot win.")
        n = n + 1