NIM(3)， python

han8809

false_table = dict()
true_table = dict()
def possible_next_moves(m,n):
for i in range(0,m):
yield(i,n)
for i in range(0,n):
if m<i:
yield(m,i)
else:
yield(i,m)
for i in range(0,m):
yield(i,n-m+i)
def can_reach(m,n,m1,n1):
if m==m1 and n==n1:
return False
if m==m1 or n==n1 or m-m1 == n-n1:
return True
else:
return False;
def quick_check(m,n,name):
for k,v in false_table.items():
if can_reach(m,n,v[1][0],v[1][1]):
true_table[name] = (True,v[1])
return (True,v[1])
return None
def nim(m,n):
if m>n:
m,n = n,m
name = str(m) + '+' +str(n)
if name in false_table:
return false_table[name]
if name in true_table:
return true_table[name]
#Used for Optimization, but optional
check = quick_check(m,n,name)
if check:
return check
for possible in possible_next_moves(m,n):
r=nim(possible[0],possible[1])
if r[0] == False:
true_table[name] = (True,possible)
return (True, possible)
#        elif can_reach(m, n, r[1][0], r[1][1]):
#            true_table[name] = (True,r[1])
#            return (True,r[1])
false_table[name] = (False,(m,n))
return (False,(m,n))
def assert_false(m,n):
size = 0
for possible in possible_next_moves(m,n):
size = size +1
r = nim (possible[0],possible[1])
if r[0] != True:
print('error!',m,n,'should be false but it has false sub move', possible)
return
print('all',size,'possible moves are checked!')

if __name__ == '__main__':
assert_false(6,8)

false_table
{'3+5': (False, (3, 5)), '1+2': (False, (1, 2)), '0+0': (False, (0, 0)),
'4+7': (False, (4, 7))}
true_table
{'2+4': (True, (1, 2)), '2+5': (True, (1, 2)), '2+7': (True, (1, 2)),
'0+5': (True, (0, 0)), '4+8': (True, (4, 7)), '0+2': (True, (0, 0)),
'0+3': (True, (0, 0)), '2+6': (True, (1, 2)), '0+1': (True, (0, 0)),
'0+6': (True, (0, 0)), '0+7': (True, (0, 0)), '0+4': (True, (0, 0)),
'2+3': (True, (1, 2)), '0+8': (True, (0, 0)), '2+8': (True, (1, 2)),
'4+6': (True, (3, 5)), '4+4': (True, (0, 0)), '1+8': (True, (1, 2)),
'1+3': (True, (1, 2)), '1+1': (True, (0, 0)), '1+7': (True, (1, 2)),
'1+6': (True, (1, 2)), '1+5': (True, (1, 2)), '1+4': (True, (1, 2)),
'3+4': (True, (1, 2)), '3+7': (True, (3, 5)), '3+6': (True, (3, 5)),
'3+3': (True, (0, 0)), '5+8': (True, (4, 7)), '5+6': (True, (1, 2)),
'3+8': (True, (3, 5)), '6+6': (True, (0, 0)), '6+7': (True, (1, 2)),
'4+5': (True, (3, 5))}