#!/usr/bin/python3
"""Usage: mariosolver.py [-h|--help] [-o|--noobstacles] [-c|--nocoins] [-n <# of coins>|--startnumcoins=<# of coins>] [-q <square>|--startingsquare=<square>]
  -h|--help: Print usage statement
  -o|--noobstacles: Ignore obstacles
  -c|--nocoins: Ignore coins
  -n <# of coins>|--startnumcoins=<# of coins>: Start with a specified number of coins
  -q <square>|--startingsquare=<square>: Start on a different numbered square (away from the Princess)
"""

import getopt, sys

decisions = {}

class memoized(object):
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """
    def __init__(self, func):
        self.func = func
        self.cache = {}
    def __call__(self, *args):
        # The last entry of args only affects the memoization if
        # it contains this number.
        memoArgs = args[:-1] + (args[0] in args[-1],)
        try:
           return self.cache[memoArgs]
        except KeyError:
           self.cache[memoArgs] = value = self.func(*args)
           return value
        except TypeError:
           # uncachable -- for instance, passing a list as an argument.
           # Better to not cache than to blow up entirely.
           # In general, maybe, but here we want to know!
           print("uh-oh - uncacheable call!")
           sys.exit(2)
           #return self.func(*args)
    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__


def gcd(a, b):
    while a:
        a, b = b%a, a
    return b

def reduce(a, b):
    d = gcd(a, b)
    return (a/d, b/d)

def add(f1, f2):
    (n1, d1) = f1
    (n2, d2) = f2
    return reduce(n1*d2+n2*d1, d1*d2)

def addList(fracList):
    t = (0,1)
    for frac in fracList:
        t = add(t, frac)
    return t

def mul(f1, f2):
    (n1, d1) = f1
    (n2, d2) = f2
    return reduce(n1*n2, d1*d2)

def fracMax(f1, f2):
    (n1, d1) = f1
    (n2, d2) = f2
    if (n1*d2 > n2*d1):
        return (n1, d1)
    else:
        return (n2, d2)

squareInfo = {}
def setupSpaces():
    # Warp squares
    squareInfo[23] = ('warp', 22) 
    squareInfo[24] = ('warp', 22)
    squareInfo[47] = ('warp', 46)
    squareInfo[48] = ('warp', 46)
    squareInfo[71] = ('warp', 70)
    squareInfo[72] = ('warp', 70)

    # Obstacle squares
    for square in [1, 6, 12, 15, 20, 56, 58, 66]:
        squareInfo[square] = ('obstacle',)
    
    # Coin squares
    for square in [43, 45, 59, 61, 63, 64, 91, 93]:
        squareInfo[square] = ('coins', 1)
    for square in [32, 41, 50, 73, 80, 86]:
        squareInfo[square] = ('coins', 2)
    for square in [35, 53, 78, 83, 89]:
        squareInfo[square] = ('coins', 4)

# This returns (numerator, denominator)
@memoized
def getProbabilityOfSuccess(spacesAway, numCoins, options, coinsGotten):
    #print "non cached: (%d, %d, %s)" % (spacesAway, numCoins, coinsGotten)
    obstacles = options[0]
    coins = options[1]
    internalCoinsGotten = coinsGotten
    if spacesAway <= 0:
        # We're done!
        return (1, 1)
    # Otherwise, if we have negative coins then we lose no matter what.
    if numCoins < 0:
        return (0, 1)
    # See if we're on a "special" square.
    if spacesAway in squareInfo:
        info = squareInfo[spacesAway]
        if (info[0] == 'warp'):
            # Just move straight to the square
            return getProbabilityOfSuccess(info[1], numCoins, options, internalCoinsGotten)
        elif (info[0] == 'obstacle' and obstacles):
            # Stay in this space, lose 4 coins to get an extra life
            #return getProbabilityOfSuccess(spacesAway, numCoins - 4, options, internalCoinsGotten)
            numCoins -= 4;
        elif (info[0] == 'coins' and coins):
            # We just get extra coins! Yay!
            # (as long as we haven't gotten the coins from this space before)
            if (spacesAway not in internalCoinsGotten):
                numCoins += info[1]
                internalCoinsGotten = internalCoinsGotten.union(set([spacesAway]))
    if numCoins < 0:
        return (0, 1)
    # Assume no obstacles (or picking up coins) for now 
    if (spacesAway == 1):
        # Special case - 1/2 chance of succeeding, 1/2 chance of not.
        if (not obstacles):
            # If there are no obstacles, we need to adjust numCoins here.
            return add((1,2),
                    mul((1,2), getProbabilityOfSuccess(spacesAway, numCoins - 4, options, internalCoinsGotten)))
        else:
            return add((1,2),
                    mul((1,2), getProbabilityOfSuccess(spacesAway, numCoins, options, internalCoinsGotten)))
    # 1/3 chance of moving 1 space, 1/3 chance of moving 2 spaces
    # 1/6 chance of choosing, 1/6 chance of losing a turn.
    moveOneChance = getProbabilityOfSuccess(spacesAway - 1, numCoins, options, internalCoinsGotten)
    moveTwoChance = getProbabilityOfSuccess(spacesAway - 2, numCoins, options, internalCoinsGotten)
    choiceChance = fracMax(moveOneChance, moveTwoChance)
    # Cache the decision, just for fun
    if (spacesAway, numCoins) not in decisions:
        if (moveOneChance == moveTwoChance):
            decisions[(spacesAway, numCoins)] = "either"
        elif (choiceChance == moveOneChance):
            decisions[(spacesAway, numCoins)] = "one"
        elif (choiceChance == moveTwoChance):
            decisions[(spacesAway, numCoins)] = "two"
        else:
            assert(False)
    dieChance = getProbabilityOfSuccess(spacesAway, numCoins - 4, options, internalCoinsGotten)
    #print numCoins
    return addList((mul((1,3), moveOneChance),
                    mul((1,3), moveTwoChance),
                    mul((1,6), choiceChance),
                    mul((1,6), dieChance)))

def getProbabilityOfSuccessDynamic(spacesAway, numCoins):
    # Calculate this dynamic style to avoid stack overflows
    # (didn't end up needing this)
    # First, see how many coins there are available
    totalCoins = 0
    for key in squareInfo:
        if (squareInfo[key][0] == 'coins'):
            totalCoins += squareInfo[key][1]

    for s in range(spacesAway):
        for nc in range(totalCoins):
            print((s, nc))
            getProbabilityOfSuccess(s, nc, frozenset())
    return getProbabilityOfSuccess(spacesAway, numCoins, frozenset())

def usage():
    print(__doc__)

def main():
    setupSpaces()
    obstacles = True
    coins = True
    numCoins = 0
    startingSquare = 94
    try:
        opts, args = getopt.getopt(sys.argv[1:], 'hocn:q:', ['help', 'noobstacles', 'nocoins', 'startnumcoins=', 'startingsquare='])
    except getopt.GetoptError:
        usage()
        sys.exit(2)
    for o, a in opts:
        if o in ('-h', '--help'):
            usage()
            sys.exit(2)
        elif o in ('-o', '--noobstacles'):
            obstacles = False
        elif o in ('-c', '--nocoins'):
            coins = False
        elif o in ('-n', '--startnumcoins'):
            numCoins = int(a)
        elif o in ('-q', '--startingsquare'):
            startingSquare = int(a)
    print("Obstacles: %s Coins: %s Starting coins: %d Starting square: %d (default 94)" % (obstacles, coins, numCoins, startingSquare))
    (n, d) = getProbabilityOfSuccess(startingSquare, numCoins, (obstacles, coins), frozenset())
    print((n, d))
    n = float(n)
    #print(n/d)
    if (n != 0):
        print("%.10f (1 in %f)" % (n/d, d/n))
    else:
        print("%.10f" % (n/d))
    #decKeys = decisions.keys()
    #decKeys.sort()
    # Look for keys that go one space instead of two
    #for key in decKeys:
        #dec = decisions[key]
        #twoSpace = key[0] - 2
        #if (dec == "one" and ((twoSpace not in squareInfo) or squareInfo[twoSpace][0] != 'obstacle')):
            #print "%s: %s  " % (key, decisions[key]), 

if (__name__ == '__main__'):
    assert (gcd(4,6) == 2)
    assert (gcd(1,1) == 1)
    assert (gcd(0,1) == 1)
    assert (reduce(12, 18) == (2,3))
    main()