Solves 538's riddler classic for 2/21/2020

538_coin_flip_game.py

def pWin(p, f, t, cache):
    if (f, t) in cache:
        return cache[(f, t)]
    if t > f:
        return 1.0
    if t < f * -2:
        return 0.0
    one = p   * pWin(p, f-1, t+1, cache) + (1-p) * pWin(p, f-1, t-1, cache)
    two = 0.5 * pWin(p, f-1, t+2, cache) + 0.5   * pWin(p, f-1, t-2, cache)
    x = max(one, two)
    cache[(f, t)] = x
    return x

p = 0.00
while p < 1.00:
    print '{}\t{}'.format(p, pWin(p, 100, 0, {}))
    p  = p + 0.01