#!/usr/bin/env python3
#
# I can roll 4, 6, and 8-sided dice.
# I want to maximize my chance of rolling a total of 7
from collections import defaultdict

dice = [4,6,8]

optimal_strategy = {}
win_prob = { 0: 1.0 }

def optimal_strategy_for(spaces):
    if spaces not in optimal_strategy:
        # Try each die to find optimal strategy
        best_die = None
        best_chance_of_winning = 0
        for d in dice:
            p = chance_of_winning(spaces, d)
            if p > best_chance_of_winning:
                best_chance_of_winning = p
                best_die = d
        optimal_strategy[spaces] = best_die
    return optimal_strategy[spaces]

def chance_of_winning_with_optimal_strategy(spaces):
    if spaces < 0:
        return 0.0
    elif spaces not in win_prob:
        best_die = optimal_strategy_for(spaces)
        win_prob[spaces] = chance_of_winning(spaces, best_die)
    return win_prob[spaces]

def mean(ls):
    return sum(ls) / len(ls)

def chance_of_winning(spaces, d):
    s = mean([ chance_of_winning_with_optimal_strategy(spaces-i)
               for i in range(1, d+1)
    ])
    return s

if __name__ == '__main__':
    N = 20
    print("Dice:", dice)
    _ = chance_of_winning_with_optimal_strategy(N)
    
    for i in range(1, N+1):
        print(f"{i :3} {optimal_strategy[i] :2} {100 * win_prob[i] :5.2f}%")