#*************************************************************************#
# Copyright (C) 2013 Edinah K. Gnang #
# #
# Distributed under the terms of the GNU General Public License (GPL) #
# #
# This code is distributed in the hope that it will be useful, #
# but WITHOUT ANY WARRANTY; without even the implied warranty of #
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU #
# General Public License for more details. #
# #
# The full text of the GPL is available at: #
# #
# http://www.gnu.org/licenses/ #
#*************************************************************************#
r"""
C3.sage: ExpMath class Jan. 31, 2013
Continuing non-partisan combinatorial games.
AUTHORS:
-- Edinah K. Gnang (Mon Jan 28 2013)
TODO:
-- Optimize the running time.
"""
def am(G):
"""
Expresses the adjacency matrix M corresponding to the graph G
M[i,j] = 1 (resp. 0) if j is ( is not )
in the list G[i]
sage:G = [[1],[2],[0]]
sage:am(G)
[0, 1, 0]
[0, 0, 1]
[1, 0, 0]
"""
M = Matrix(ZZ,len(G),len(G),[0 for k in range((len(G))^2)])
for i in range(len(G)):
for j in range(len(G)):
if j in Set(G[i]):
M[i,j] = 1
return M
def is_cyclic(G):
"""
Inputs a directed graph (descibed as an list of list) and outputs True (resp. False) if
it has a cycle (if it contains no cycle)
sage: is_cyclic([[1],[2],[0]])
True
"""
# Obtaining the adjacency matrix
M = am(G)
# Initializing the temporary matrix
M1 = M
for i in range(len(G)):
if M1.trace() > 0:
return True
else :
M1 = M1*M
return False
@cached_function
def fGi(G,i):
"""
Inputs a directed graph G and an integer i in range(len(G))
and outputs 0 (resp. 1) if the vertex i is a losing (winning)
position
Incase the graph contains a cycle the function outputs -1
"""
if is_cyclic(G):
print "The Graph contains a cycle"
return -1
else:
M = G[i]
if G[i] == []:
return 0
elif Set([fGi(G,m) for m in M]) == Set([1]):
return 0
else :
return 1
@cached_function
def wlist(G):
"""
Inputs a directed graph G representing a game and outputs a list of nops(G)
such that L[i] = 0 or 1 accorfing to whether position (vertex) i
is a loosing or a winning position
sage:G = [[1],[2],[0]]
sage:wlist(G)
"""
return [fGi(G,i) for i in range(len(G))]
def rand_game(n, k):
"""
Inputs pos. integers n and k and ouputs a random digraph that has the property that out
of vertex i all the labels are less to i, and having as number of outgoing edges a
number between 2 and k
"""
L = [ list(Set([randint(0,j) for i in range(1,randint(2,k))])) for j in range(n)]
L.insert(0,[])
return L
def w(G, i):
"""
inputs a directed graph representing a game and a pos. integer i between 1
and nops(G) (representing a position) and outputs 0(1) according to whether it
is a losing [P position] (winning [N]) position due to Matthew Russell
(inspired by Pat Devlin and Tim Naumovitz)
"""
p = 1
for m in G[i]:
p = p * w(G, m)
return 1-p
def wl(L, R, i):
"""
Inputs Two digraphs L and R (with nops(L)=nops(R), of course, representing
the positions) representing the legal moves for player Left and player Right resp.
and a position i Ourputs 0(1) if Left must lose or may win (with perfect players)
"""
for m in L[i]:
p = p * wr(L, R, m)
return 1-p
def wr(L, R, i):
"""
WL(L, R, i): inputs Two digraphs L and R (with nops(L)=nops(R), of course, representing
the positions) representing the legal moves for player Right and player Left resp.
and a position i Ourputs 0(1) if Left must lose or may win (with perfect players)
"""
for m in R[i]:
p = p * wl(L, R, m)
return 1-p
@cached_function
def nim1(a):
"""
Inputs a non-neg.
integers, representing a Nim-1 position with a counters, outputs whether it
is losing (0) or winning (1).
A legal move consist of removing any number of pennies (up to the total)
from that pile
"""
j = 1
p = 1
while j <= a:
p = p * nim1(a-j)
j = j+1
return 1-p
@cached_function
def nim2(a,b):
"""
inputs a list of length 2 of non-neg.
integers, representing a Nim-3 position with
a, b counters, outputs whether it
is losing (0) or winning (1)
A legal move consist of picking ONE of the piles
and removing any number of pennies (up to the total)
from that pile
"""
j1 = 1
p1 = 1
while j1 <= a:
p1 = p1 * nim2(a-j1, b)
j1 = j1+1
j2 = 1
p2 = 1
while j2 <= b:
p2 = p2 * nim2(a, b-j2)
j2 = j2+1
return 1-p1*p2
@cached_function
def nim3(a, b, c):
"""
Inputs a list of length 3 of non-neg.
integers, representing a Nim-3 position with
a, b, c counters, outputs whether it
is losing (0) or winning (1)
A legal move consist of picking ONE of the piles
and removing any number of pennies (up to the total)
from that pile
"""
j1 = 1
p1 = 1
while j1 <= a:
p1 = p1 * nim3(a-j1, b, c)
j1 = j1+1
j2 = 1
p2 = 1
while j2 <= b:
p2 = p2 * nim3(a, b-j2, c)
j2 = j2+1
j3 = 1
p3 = 1
while j3 <= b:
p3 = p3 * nim3(a, b, c-j3)
j3 = j3+1
return 1-p1*p2*p3
@cached_function
def nim(*args):
"""
Inputs a list of arbitrary length of non-neg.
integers, representing a Nim position with
counters, outputs whether it is losing (0) or winning (1)
A legal move consist of picking ONE of the piles
and removing any number of pennies (up to the total)
from that pile
"""
prd = 1
for i in range(len(args)):
p = 1
j = 1
while j <= args[i]:
L = list(args)
L[i] = L[i]-j
j = j+1
l = tuple(L)
p = p * nim(*l)
prd = p * prd
return 1-prd