#!/usr/bin/python
#-*- coding: utf-8 -*-
import numpy as np
import time
import operator
import pandas as panda
''' ============ RULES =========== '''
NBHEAP = 4
def rules(arr): #for example there, you can take a token on only one heap
a = arr[0] #or a token on each heap
b = arr[1]
c = arr[2]
d = arr[3]
i = 1
tab1=tab2=tab3=tab4=tab5=[]
if i <= a:
tab1 = [[a-i,b,c,d]]
if i <= b:
tab2 = [[a,b-i,c,d]]
if i <= c:
tab3 = [[a,b,c-i,d]]
if i <= d:
tab4 =[[a,b,c,d-i]]
if i <= a and i <= b and i <= c and i <= d:
tab5 = [[a-i,b-i,c-i,d-i]]
return tab1 + tab2 + tab3 + tab4 + tab5
''' =========== CALCULS ========== '''
def mex(arr):#fonction Mex
arr = np.unique(arr)
for i in range(arr.size):
if arr[i]!=i:
return i
return arr.size
def losing(k):#returning an array of losing positions
t=time.time()
if k <= 0:
return None
iterateur = [0 for x in range(NBHEAP)]
arr = [str(iterateur)]
iterateur[-1] = 1
while iterateur[0] < k:
lose = True
for option in rules(iterateur):
if str(option) in arr:
lose = False
break
if lose:
arr.append(str(iterateur))
i = 1
while i <= NBHEAP:
if iterateur[-i] < k:
iterateur[-i] = iterateur[-i] + 1
break
else:
iterateur[-i] = 0
i = i + 1
print 'elapsed time : '+str(time.time() - t)
return arr
def Grundy(k):#returning nimbers for positions from 0 to k
t = time.time()
if k <= 0:
return None
iterateur = [0 for x in range(NBHEAP)]
dico = {str(iterateur):0}
iterateur[-1] = 1
while iterateur[0] < k:
tmp = [[dico[str(option)]] for option in rules(iterateur)]
dico[str(iterateur)] = mex(tmp)
i = 1
while i <= NBHEAP:
if iterateur[-i] < k:
iterateur[-i] = iterateur[-i] + 1
break
else:
iterateur[-i] = 0
i = i + 1
print str(time.time() - t)
return dico
def GrundyValeur(tab):#Return a nimber for a given position
temps = time.time()
if len(tab) != NBHEAP:
print 'mauvais nombre d\'arguments'
return None
for i in tab:
if i < 0:
print 'Tout doit etre positif'
return None
dico = {str([0 for x in range(NBHEAP)]):0}
if str(tab) in dico:
return dico[str(tab)]
stack = [tab]
stack.extend(rules(tab))
#Game initialisation
while str(tab) not in dico:
IN = True
if str(stack[-1]) in dico:
stack.pop()
else:
tmp = rules(stack[-1])
for option in tmp:
if str(option) not in dico:
IN = False
break
if IN: # if all the options are in dico
Nmin = mex([dico[str(option)] for option in tmp])
dico[str(stack[-1])] = Nmin
stack.pop()
else:
stack.extend(tmp)
print 'elapsed time : '+str(time.time() - temps)
return dico[str(tab)]
def sortGrundy(dico):#sort positions by nimber
maximum = max(dico.iteritems(), key=operator.itemgetter(1))[1]
sortie = [['nimber : ' +str(i)] for i in range(maximum+1)]
for i in dico:
sortie[dico[i]].append([i])
return sortie
''' =========== SAVE ========== '''
def saveGrundyCSV(tab,nom):#Save Grundy position
df = panda.DataFrame(tab)
df.to_csv(nom+".csv")
def saveLoseCSV(tab, nom):#Save losing position
tab2 = np.array([['']])
for text in tab:
text = text.replace("[",",")
text = text.replace("]","")
text = text.replace(" ",",")
tab2 = np.concatenate((tab2, [[text]]))
df = panda.DataFrame(tab2)
df.to_csv(nom+".csv", sep=" ")
if __name__=='__main__':
print ' 1 - Search for losing positions'
print ' 2 - Search for nimbers'
print ' 3 - Search a nimber for a given position'
x = input("Your choice : ")
if x!=3:
print ' 1 - Display results'
print ' 2 - Save results'
y = input("Your choice : ")
if x == 1:
taille = input("Upper bound?\n")
if y == 1:
print losing(int(taille))
elif y == 2:
nom = raw_input("How would you name the save file?\n")
saveLoseCSV(losing(int(taille)),nom)
elif x == 2:
taille = input("Upper bound?\n")
if y == 1:
print Grundy(int(taille))
elif y == 2:
nom = raw_input("How would you name the save file?\n")
saveGrundyCSV(Grundy(int(taille)),nom)
elif x == 3:
position=[]
for i in range(NBHEAP):
p = input("Position for the heap n°"+str(i+1)+" : ");
position.append(p);
print position
print GrundyValeur(position)
This application is able to find solution for every possible nim games. It can handle how many heaps you want, so you have to indicate the number of heap in the variable NBHEAP. Then you have to write rules as the following examples. It takes an array (a python list) as an input, and it returns a list of lists. You can use the application even for nim games with less than 3 heaps. But it's not recommended since both of previous algorithms are faster for such nim games.
#!/usr/bin/python
def rules(arr): #for example there, you can take a token on only one heap
a = arr[0] #or a token on each heap
b = arr[1]
c = arr[2]
d = arr[3]
i = 1
tab1=tab2=tab3=tab4=tab5=[]
if i <= a:
tab1 = [[a-i,b,c,d]]
if i <= b:
tab2 = [[a,b-i,c,d]]
if i <= c:
tab3 = [[a,b,c-i,d]]
if i <= d:
tab4 =[[a,b,c,d-i]]
if i <= a and i <= b and i <= c and i <= d:
tab5 = [[a-i,b-i,c-i,d-i]]
return tab1 + tab2 + tab3 + tab4 + tab5