#Nathan Fox
#Homework 4
#I give permission for this file to be posted online,
#though I do NOT give permission to post hw4.pdf

#Help procedure
Help:=proc() : print(` mex(S) , SG(G,i) , RandGame(n,k) `):
print(` SGwyt(i,j) , WinningMove(G,i) `): end:

##Auxiliary Procedures
#mex(S): inputs a set of nonnegative 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)} reachable
#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:

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

L:=[{}]:

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

L:
end:

##Problem 2
#See file hw4.pdf for solution to this problem.

##Problem 3
#See file hw4.pdf for solution to this problem.

##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) local k:
option remember:

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

end:

##Problem 6
#WinningMove(G,i): inputs a game given as a digraph G, and
#a position i (between 1 and nops(G)), and outputs a winning
#move (a member of G[i]) if one exists, or FAIL if i is a
#losing (alias P) position.
WinningMove:=proc(G,i) local j:

for j in G[i] do
    if SG(G,j)=0 then
        return j:
    fi:
od:
return FAIL:
end: