Code

#!/usr/bin/python
#-*- coding: utf-8 -*-

import numpy as np
import operator
import time
import pandas as panda

def mex(arr):#fonction Mex
    arr = np.unique(arr)
    for i in range(arr.size):
        if arr[i]!=i:
            return i
    return arr.size

#cut#side#all

def rights(chiffre):#function converting a digit in binary. Named right because of the
    return str(bin(chiffre)).replace("b","0")#UNIX right system

def option(rule, Game):# returning all the options for a given moment in the game
    gameState=Game[:]
    liste = [rights(i) for i in rule]
    options = []
    i=0
    for num in liste:
        if num[-3]=='1':
            for it in range(len(gameState)):
                if gameState[it] > i+1:
                    tmp = gameState[:]
                    gameState[it] -= i
                    bonus = gameState[it]/2 + gameState[it]%2
                    gameState[it]/=2
                    gameState.append(bonus)
                    options.append(gameState[:])
                    while gameState[it]>1:
                        gameState[it]-=1
                        gameState[-1]+=1
                        options.append(gameState[:])
                    gameState = tmp
        if num[-2]=='1':
            for it in range(len(gameState)):
                if gameState[it] > i:
                    gameState[it] -= i
                    options.append(gameState[:])
                    gameState[it] += i
        if num[-1]=='1':
            for it in range(len(gameState)):
                if gameState[it]==i:
                    gameState[it] -= i
                    options.append(gameState[:])
                    gameState[it] += i
        i+=1
    for o in options:
        o.sort()
    return options

def findG(tab, dico):#function returning the nimber of two heaps, using a xor
    if len(tab)==1:
       return dico[tab[0]]
    tmp = dico[tab[0]] ^ dico[tab[1]]
    if len(tab)>2:
        for i in range(len(tab)-2):
            tmp ^= dico[tab[i+2]]
    return tmp

def findGstr(tab, dico):#same function, but for str parameters values.
    if len(tab)<=1:
       return dico[str([tab[0]])]
    tmp = dico[str([tab[0]])] ^ dico[str([tab[1]])]
    if len(tab)>2:
        for i in range(len(tab)-2):
            tmp ^= dico[str([tab[i+2]])]
    return tmp


def Grundy(k, rule):#function returning the nimbers for positions between 0 and k
    if rule[0] != 4 and rule[0] != 0:
        print 'The first rule can only be 0 or 4'
        return
    t=time.time()
    dico={0:0}
    if k < 0:
        return None
    for i in range(k):
        dico[i] = mex([findG(tab,dico) for tab in option(rule,[i])])
    print "elapsed time in the grundy function : "+ str(time.time() - t)
    return dico

def GrundyValeur(tabValeur, rule):#function returning a nimber for a given position
    return findG(tabValeur, Grundy(max(tabValeur)+1, rule))

def GrundyComplet(taillePile, rule):#returning all the nimber, for all the possible
    temps = time.time()#positions (even redundant like [0, 3, 2] and [3, 2, 0] and
    dico = { str([x]) : y for x, y in Grundy(taillePile, rule).iteritems()}#[2, 0, 3])
    stack = [[taillePile]]
    while stack != []:
        if str(stack[-1]) in dico:
            stack.pop()
        else:
            IN = True
            tmp = [[x for x in y if x != 0] for y in option(rule, stack[-1])]
            for o in tmp:
                if str(o) not in dico:
                    IN = False
                    break
            if IN:
                dico[str(stack[-1])] = mex([findGstr(tab,dico) for tab in tmp])
                stack.pop()
            else:
                stack.extend(tmp)
    print "elapsed time in GrundyComplet : "+str(time.time() - temps)
    return dico

def save(dico):#save dictionnary in a file
    marx = max(dico.iteritems(), key=operator.itemgetter(1))[1]
    values = [['Val Grundy : '+str(nimber)] for nimber in range(marx)]
    for i in range(marx):
        values[i].extend(sorted([a for a in dico if dico[a] == i]))
    df = panda.DataFrame(values)
    df.to_csv("save.csv")

def findPeriod(qtt, rule): #e < n < 2(e + p) + t # check if it's periodic (for a sample)
    tabValues = Grundy(qtt,rule).values()
    t = rule[-1]
    temps = time.time()
    tab=[]
    possibilite = []
    current = []
    mini = 0
    actual = -1
    for decalage in range(1,len(tabValues)):
        for pos in (range(len(tabValues))):
            if decalage+pos < len(tabValues) and tabValues[pos] == tabValues[pos + decalage]:
                tab.append([pos,decalage])
                
    for x in range(len(tab)-1):
        if (2 *(tab[x][1]) + t) <= (len(tabValues)-mini) or actual != tab[x][1]:
            if tab[x][0] + 1 == tab[x+1][0] and tab[x][1] == tab[x+1][1]:
                current.append(tab[x])
            else:
                if tab[x][1] == tab[x+1][1] and tab[x][0] + 1 != tab[x+1][0]:
                    current = []
                    mini = tab[x][0]
                    actual = tab[x][1]        
        if tab[x][1] != tab[x+1][1]:
            possibilite.extend(current)
            
    debut = 0
    taille = 0
    valeur = 0
    period = [0,0,0]
    for p in possibilite:
        if valeur == p[1]:
            taille+=1
        else:
            if taille > period[0]:
                period = [taille, debut, valeur]
            debut = p[0]
            valeur = p[1]
            taille = 1
    print "elapsed time in findPeriod : " + str(time.time() - temps)
    if period[0] > (2 * (period[1] + period[2]) + t):
        print 'period size : '+str(period[2])
        print 'pre-period : '+ str(period[1])
    else:
        print "The sample doesn't allow us to clearly find a period"
        print "The longuest period we found until now : "
        print "[pre-period, period]"
        print "[",period[1],",",period[2],"]"
        print "This period is verified over a length of",period[0]
    
if __name__ == '__main__':

    print "Menu : "
    print " 1 - Search for nimbers"
    print " 2 - Search a nimber for a given position"
    print " 3 - Search periodicity in a nimber list"
    choice1 = input("Your choice : ")
    val = 0
    rule = []
    cpt = 2
    val = input("First rule (0 or 4) : ")
    if val == 4 or val == 0 :
        rule.append(val)
    else:
        exit()
    while val < 8 and val >= 0:
        val = input("Rule n°"+str(cpt)+" (to stop, input an integer out of 0-7) : ")
        if val <8 and val >=0:
            rule.append(val)
            cpt+=1
    if choice1 == 1:
        print "Menu 2 : "
        print " 1 - Search only for main positions"
        print " 2 - Search for all the possible positions (long)"
        choice2 = input("Your choice : ")
        print "Menu 3 : "
        print " 1 - Display results"
        print " 2 - Save results"
        choice3 = input("Your choice : ")
        bound = input("Upper bound : ")
        if choice2==1:
            resultat = Grundy(bound, rule)
        else:
            resultat = GrundyComplet(bound, rule)
        if choice3 == 1:
            print resultat
        else:
            save(resultat)
    if choice1 == 2:
        position = []
        cpt = 1
        val = 0
        while val < 10 and val >= 0:
        val = input("Position for heap n°"+str(cpt)+
	            " (to stop, input an integer out of 0-9) : ")
            if val <10 and val >=0:
                position.append(val)
                cpt+=1
        print GrundyValeur(position, rule)
    if choice1 == 3:
        bound = input("Upper bound for the list of values : ")
        findPeriod(bound, rule)