#####    HW 4  #######


Help:=proc():  print("SGwyt(a,b), WinningMove(G,i)"): end:
##### 2 ##########


# We prove that if f is the Sprague-Grundy function on two pile nim games then 2f(m,n)=f(2m,2n),
# 2f(m,n)+1=f(2m+1,2n)=f(2m,2n+1), and f(2m+1,2n+1)=2f(m,n) by induction on the total size
# of the larger (doubled game) 
# The Base Case when the sums of the piles are 4 or less can easily be checked.
# For the inductive step, we note that all legal moves have pile size strictly less than the current
# pile size.  First we take the case of both piles even, i.e. f(2m,2n).  The set of all the legal moves
# has the form {2(m',n)+(0/1,0) or 2(m,n')+(0,0/1) :  m'<m, n'<n}.  So by induction the
# Sprague Grundy function of these piles takes on exactly the set of all the values in the sumset
# 2{0,1,2,...,f(m,n)-1}+{0,1}={0,1,...,2f(m,n)-1}.  And so f(2m,2n)= 2f(m,n).
# For the case of exactly one odde f(2m+1,2n) or f(2m,2n+1) we see that these have the same move set
# {2(m',n)+(0/1,0) or 2(m,n')+(0,0/1) :  m'<m, n'<n}, but now with the single additional possible move
# outside of this range of (2m,2n).  This new pile we checked above has Sprague Grundy of 2f(m,n) so
# f(2m+1,2n)=f(2m,2n+1)=mex(2f(m,n),{2(m',n)+(0/1,0) or 2(m,n')+(0,0/1) :  m'<m, n'<n})=2f(m,n)+1.
# Lastly for the case of 2 odd inputs f(2m+1,2n+1) our legal move set is again of the form
# {2(m',n)+(0/1,0) or 2(m,n')+(0,0/1) :  m'<m, n'<n} but now with the additional moves of (2m+1,n) and
# (2m,2n+1).  However, we have computed these to have Sprague Grundy of 2f(m,n)+1 and so 
# f(2m+1,2n+1)=mex({2(m',n)+(0/1,0) or 2(m,n')+(0,0/1) :  m'<m, n'<n},2f(m,n)+1)=2f(m,n).

###########QED################################

########## 3 ##########


# We proceed by induction on the length of the longest path from a given vertex to any sink.
# The base case will be sinks, which have Sprague Grundy of 0 (mex({})=0) and indeed are defined 
# to be losers.
# For the inductive step, we note that all possible moves from a given vertex v to a child w will have a 
# shorter longest path to any sink than the position from which they came, and so by induction we have that
# they are losing if and only if they have Sprague Grundy of 0.  But v is winning if and only if it has a child which
# is losing.  As we just noted by induction this is equivalent to having a child with Sprague Grundy of 0, which is exactly
# the condition which guarantees having nonzero Sprague Grundy.  Therefore we have that a vertex is winning
# iff its Sprague Grundy is nonzero, as we wanted to show.

######### QED ##################################


####   4 ###########
SGwyt:=proc(a::nonnegint,b::nonnegint) local i,j,S,B:
option remember:
S:={}:
for i from 0 to a-1 do
	S:={op(S),[i,b]}:
od:
for j from 0 to b-1 do
	S:={op(S),[a,j]}:
od:
for j from 1 to min(a,b) do
	S:={op(S),[a-j,b-j]}:
od:
mex({seq(SGwyt(op(B)), B in S)}):
end:


#####  6   #########
WinningMove:=proc(G,i::posint) local j,k,S:
option remember:
for j in G[i] do
	if fGi(G,j)=0 then
		RETURN(j):
	fi:
od:
Fail:
end:

######























###########################    STUFF FROM CLASS   #######################
#Feb. 4, 2013,  C4.txt Sprague-Grundy function of non-partizan games

Help4:=proc(): print(` mex(s), SG(G,i) , SG2N(i,j) , SG1(i,j)`): 
print(`NimSum(L) `):
end:

#mex(S): inputs a set of non-neg. integers and outputs
#the minimum of the set {0,1,2,3,...}\S
mex:=proc(S) local i:

for i from 0 to nops(S) while i in S do od:
i:
end:


#SG(G,i): inputs a digraph (representing a cycle-less
#combinatorial game with positions 1, 2, ..., nops(G)
#and  G[i] is the subset of {1, ..., nops(G)} rechable
#in one legal move
#outputs the value of the Sprague-Grundy function
#at vertex i
SG:=proc(G,i) local m:
option remember:

mex({seq(SG(G,m), m in G[i])}): 


end:

#SG2N(i,j): The S-G function of positon [i,j] in 2-pile Nim
SG2N:=proc(i,j) local k:
option remember:

mex({ seq(SG2N(i-k,j),k=1..i), seq(SG2N(i,j-k),k=1..j)}):

end:

with(Bits):

#NimSum(L): the Nim sum of the list of non-neg. integers
#in L
NimSum:=proc(L)

if L=[] then
 RETURN(0):
elif nops(L)=1 then
 RETURN(L[1]):
 else
  NimSum( [Xor(L[1],L[2]), op(3..nops(L),L)]):
fi:


end:

#NimSumPat(L): the Nim sum of the list of non-neg. integers
#in L
NimSumPat:=proc(L)

if L=[] then
 RETURN(0):

 else
 RETURN(Xor(L[1],NimSumPat([op(2..nops(L),L)]))):
fi:


end:


#SG(2*m,2*n)=2*SG(m,n)
#SG(2*m,2*n+1)=2*SG(m,n)+1
#SG(2*m+1,2*n)=2*SG(m,n)+1
#SG(2*m+1,2*n+1)=2*SG(m,n):


#a^(2*n)= (a^n)^2 , a^(2*n+1)=(a^n)^2*a
#a^i=a^(i-1)*a

#SG1(m,n): Like SG2N(m,n), but done using the fast recurrene
SG1:=proc(m,n)
option remember:

if m=0 and n=0 then
 RETURN(0):
elif m mod 2=0 and n mod 2 =0 then
 RETURN(2*SG1(m/2,n/2)):
elif m mod 2=1 and n mod 2 =0 then
 RETURN(2*SG1((m-1)/2,n/2)+1  ):

elif m mod 2=0 and n mod 2 =1 then
 RETURN(2*SG1(m/2,(n-1)/2)+1  ):

else
 RETURN(2*SG1((m-1)/2,(n-1)/2)  ):

fi:

end:










####Old stuff

#C3.txt: Jan. 31, 2013 class continuing no-partizan combinatorial games
#and starting partizan games
Help3:=proc(): print(` W(G,i), WL(L,R,i), WR(L,R,i) `): 
print(`Nim1(a), Nim2(Li),Nim3(Li), Nim(Li)  `):
end:

#W(G,i): same as fGi(G,i) from C2.txt
#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)
W:=proc(G,i) local m:
option remember:
1-mul(W(G,m),m in G[i]):
end:


#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)
WL:=proc(L,R,i) local m:
option remember:

1-mul(WR(L,R,m),m in L[i]):

end:

#WR(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 Right must lose or may win (with perfect players)
WR:=proc(L,R,i) local m:
option remember:

1-mul(WL(L,R,m),m in R[i]):

end:

#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
Nim1:=proc(a) local i:
option remember:

1-mul(Nim1(a-i),i=1..a):

end:

#Nim2(Li): inputs a list of length 2 of non-neg.
#integers, representing a Nim-3 position with
#Li[1],Li[2] 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
Nim2:=proc(Li) local i:
option remember:

1-mul(Nim2([Li[1]-i,Li[2]]),i=1..Li[1])*
mul(Nim2([Li[1],Li[2]-i]),i=1..Li[2]):

end:

#Nim3(Li): inputs a list of length 3 of non-neg.
#integers, representing a Nim-3 position with
#Li[1],Li[2],Li[3] 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
Nim3:=proc(Li) option remember:
1-mul(Nim3([Li[1]-i,Li[2],Li[3]]),i=1..Li[1])*
mul(Nim3([Li[1],Li[2]-i,Li[3]]),i=1..Li[2])*
mul(Nim3([Li[1],Li[2],Li[3]-i]),i=1..Li[3]):

end:

#Nim(Li): L of any length
Nim:=proc(Li) local i,j:
option remember:

1-mul(
mul(
Nim([ op(1..j-1, Li), Li[j]-i, op(j+1..nops(Li),Li) ]),
i=1..Li[j]),
j=1..nops(Li)):

end:




#####old stuff
#Jan. 28, 2013, general non-partisan games
Help2:=proc(): print(` fGi(G,i) , AM(G) , IsCyclic(G) `): 
print(`WList(G), RandGame(n,k) `):
end:

#Every non-partisan combinatorial game can be described
#abstractly as a directed graph. The positions are
#the vertices, and there is a DIRECTED edge between
#vertex v1 to v2, if it is a legal move
#We represent a digraph as a list L
#The vertices are called 1,2,.., n:=nops(L)
#and for i=1,2, ..., n, L[i] is the set of
#vertices for which there is a directed edge from i to 
#For example G=[{},{1},{1,2}], the edges are
#{[2,1],[3,1],[3,2]}



#IsCyclic(G): inputs a directed graph (described as
#a list of sets, andoutputs true (false) if it has
#a cycle
IsCyclic:=proc(G) local i,M1,M:
option remember:

M:=AM(G):
M1:=M:

#Soon-to-be PhD candidate 
#Jacob  Baron thinks that it safer to do nops(G)+1
for i from 1 to nops(G)+1 do

 if trace(M1)>0 then
   RETURN(true):
 fi:

M1:=evalm(M1*M):

od:

false:

end:


#fGi(G,i), inputs a directed graph G and
#an integer i between 1 and nops(G) and outputs
#0(resp. 1) if vertex i is a Losing (Winning) position

fGi:=proc(G,i) local M,m:
option remember:

if not (type(i,integer) and type(G,list) and i>=1 and i<=nops(G))
   then
   print(`bad input`):
   RETURN(FAIL):
fi:


#if IsCyclic(G) then
#print(`graph has cycles`):
#    RETURN(FAIL):

#fi:

if G[i]={} then
 RETURN(0):
fi:

M:=G[i]:

if {seq(fGi(G,m), m in M)}={1} then
   RETURN(0):
 else
   RETURN(1):
fi:

end:

with(linalg):

#AM(G): adjacency matrix of G (written a matrix M)
#M[i,j]=1 (0) of j belongs (does not belong) 
#to G[i] 
AM:=proc(G) local n,i,j,M:

n:=nops(G):

M:=matrix(n,n):


for i from 1 to n do
 for j from 1 to n do
   if j in G[i] then

     M[i,j]:=1:

    else

       M[i,j]:=0:
    fi:
 od:
od:

op(M):

end:


#WList(G): Winning list
#Inputs a directed G (representing a game)
#and outputs a list of length nops(G) such that
#L[i]=0 or 1 according to whether position (vertex) i
#is a losing or winning position
WList:=proc(G) local i:
[seq(fGi(G,i),i=1..nops(G))]:
end:

#RandGame(n,k): inputs pos. integers n and k
#and outputs a random digraph that has the
#property that out of vertex i all the labels
#are less i, and there are (usually) k outgoing
#edges
RandGame:=proc(n,k) local L,i,tomas,j:

L:=[{}]:

for i from 2 to n do
 
tomas:={seq(rand(1..i-1)(),j=1..k)}:

L:=[op(L), tomas]:
od:

L:

end:

#end old stuff