n-m-nim.py

#!/usr/bin/python

# n-m nim
if True:
    M, N = 3, 10
else:
    M, N = 2, 2

def mex(S):
    i = 0
    while i in S:
        i += 1
    return i

def memoize(f):
    cache= {}
    def memf(*x):
        if x not in cache:
            cache[x] = f(*x)
        return cache[x]
    return memf

@memoize
def grundy(n):
    if n < M:      # lost, P-game
        return 0

    options = []
    for t in range(M, N+1):
        if t <= n:
            options.append(grundy(n-t))

    return mex(options)

G = [grundy(i) for i in range(1000)]

for i in range(25):
    print i, G[i]