# Viraj Pandya, Experimental Mathematics, Spring 2013
# Homework Assignment 4
# I give Dr. Z permission to post this file on his website.

# See hw4.mw for the examples from pages 91-end of Garvan's Maple tutorial.

# Begin Dr. Z's homework problems:


Help:=proc():
	print(`SGwyt(i,j)`):
end:


#### Importing Dr. Z's programs mex(S), SG(G,i), SG2N(i,j)  from C4.txt

#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:



#### Importing Nim2(L), Nim(Li), Wyt(a,b) from hw4.txt


#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:


#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:


# The Wythoff game is like 2-pile Nim with the extra move that one can remove the SAME 
# number of pennies from BOTH piles. Write a procedure Wyt(a,b) that inputs 0(1) according 
# to whether [a,b] is a losing (winning) position.

# I used the convention here where if both piles have 0 pennies, it 
# is a losing position since nothing can be removed. Else, if both 
# piles have the same number of pennies, then it is a winning position 
# since you can remove the same number of pennies from both piles leaving 
# [0,0] for the next player (a losing position for them). Else, if 
# a<>b (not equal), then Nim2([a,b]) should be called.

Wyt:=proc(a,b) option remember:

	if [a,b]=[0,0] then
		0:
	elif a=b then
		1:
	else
		Nim2([a,b]):
	fi:
end:



##### PROBLEM 2

#Starting from the recursive definition of the Sprague-Grundy 
#function for two-pile Nim (let's call it f(m,n))
#f(m,n)=mex({f(m-1,n),f(m-2,n), ..., f(0,m),   f(m,n-1),f(m,n-2), ..., f(m,0)} ),
#prove, by induction on m and n, the recurrences 
#f(2m,2n)=2f(m,n)   ,   f(2m+1,2n)=2f(m,n)+1   ,   f(2m,2n+1)=2f(m,n)+1   ,   f(2m+1,2n+1)=2f(m,n)
#(that are equivalent to the fact that f(m,n) is the sum-without-carry of m and n in binary) 


# Need to think about the fast recurrence implementation further.


##### PROBLEM 3

# Prove that a position is Losing iff its Sprague-Grundy function is 0 


# Assume a position is Losing. Then, by definition, 
# there are no edges connecting that position to 
# another position in that game's directed graph.
# Thus, by construction of the S-G function,
# f(v) = mex({empty}) = 0. 

# Conversely, assume the S-G function,
# f(v) = mex({f(w)|vw in E}) = 0.
# Then, the only way mex(S) where S is a set
# can return 0 is if S is the empty set or S 
# does not contain 0. If S is the empty set, 
# then that means v is a sink for there are no 
# outgoing edges from v, and so v is a Losing position.
# Else if S does not contain 0, then there is an
# outgoing edge from v to another vertex w where 
# f(w)<>0 (not equal to). But this means that 
# the corresponding set T of f(w) (analagous
# to S of f(v)) contains 0, i.e., a player can
# move from w to another vertex x s.t. f(x)=0
# and so x is a Losing position. In this case then,
# v is also a Losing position.

##### PROBLEM 4

# SGwyt(i,j) inputs two non-negative integers i and j
# and outputs the Sprague-Grundy function of 
# position (i,j) in Wythoff's game, where a legal move
# consists of taking a positive number of pennies from 
# either pile, or the Same number from both. 


SGwyt:=proc(i,j) option remember:

	if [i,j]=[0,0] then
		0:
	elif i=j then
		SG2N(i,i):
	else
		SG2N(i,j):
	fi:
	
end: