#Stuff done on Apr. 15, 2010
#(also PRg finished after class)

OldHelp:=proc(): print(`Orbit1(G,i), IsCyclic(G)`):
print(`ALosers(G), PRg(n,k) , Nim2(N1,N2) `):
end:

Help:=proc(): print(`Losers(G,K), Nim3(N1,N2,N3) `): 
print(`Grab3i(S) `):
end:


Orbit1:=proc(G,i) local F1,F2,T,f1,f2:
F1:=G[i]:
F2:= F1 union {seq(op(G[f1]),f1 in F1)}:

while F1<>F2 do
F1:=F2:
F2:= F2 union {seq(op(G[f2]),f2 in F2)}:
od:

F1:

end:






#IsCyclic(G): inputs a directed graph in the
#above format and decides whether there exist cycles
IsCyclic:=proc(G) local i:

for i from 1 to nops(G) do

if member(i,Orbit1(G,i)) then
  RETURN(true):
fi:
od:

false:
end:


ALosers:=proc(G) local L,W,A,n,Ac,v1,V,i:

if IsCyclic(G) then
  RETURN(FAIL):
fi:

n:=nops(G):
V:={seq(i,i=1..n)}:
L:={}:
W:={}:

for i from 1 to n do
 if G[i]={} then
     L:=L union {i}:
 fi:
od:

A:=L union W:

while A<>V do
Ac:=V minus A:

 for v1 in Ac do
   if G[v1] intersect L<>{} then
       W:=W union {v1}:
   fi:
od:

A:=A union W:
Ac:=V minus A:

 for v1 in Ac do
   if G[v1] minus W={} then
     L:=L union {v1}:  
   fi:
od:
A:=A union L:


od:

L:

end:




#PRg(n,k): the game of removing up to k pennies
#from a pile of n pennies. The output is the directed graph
#in our data-structure for directed graphs G,
#where G is a list of subsets of {1, ..., n} (where n=nops(G))
#evertices are assumed to have names 1 through  n
#and G[i] is the set of vertices reachable from vertex i in one move
#followed by the "key" the list of vertices in their "natural" names.
PRg:=proc(n,k) local V,v,i,T,V1,V2,tv1:
V:=[seq(i,i=0..n)]:

for i from 1 to nops(V) do
  V1[i]:=V[i]:
  V2[V[i]]:=i:
od:


for v in V do
T[v]:={seq(v-i,i=1..min(k,v))}:
T[v]:={seq(V2[tv1],tv1 in T[v])}:
od:


[seq(T[V1[i]],i=1..nops(V))],V:

end:

#Losers(G,K): Given a directed graph G
#representing a comb. game in condensened notation
#where the vertices are labelled 1,2, ..., nops(G)
#and a list K, where K[i] is the natural name
#outputs the losers with their natural names
Losers:=proc(G,K) local i,L:
L:=ALosers(G): {seq(K[i], i in L)}:
end:


#Nim2(N1,N2): the directed graph for two-pile Nim
#where the piles have size <=N1 and <=N2 pennies
Nim2:=proc(N1,N2) local V,i,j,T,i1,j1,Ki,pos,Nei,n1,G:

V:=[seq(seq([i,j],i=0..N1),j=0..N2)]:


#T[[i,j]]=all positions reachable from [i,j] in one move

for i from 0 to N1 do
 for j from 0 to N2 do
  T[[i,j]]:={seq([i1,j],i1=0..i-1),
             seq([i,j1],j1=0..j-1)}:
 od:
od:


for i from 1 to nops(V) do

 Ki[V[i]]:=i:
od:

G:=[]:

for i from 1 to nops(V) do
 pos:=V[i]:
 Nei:=T[pos]:
 Nei:={seq(Ki[n1],n1 in Nei)}:
 G:=[op(G),Nei]:
od:

G,V:

end:


#Nim3(N1,N2,N3): the directed graph for two-pile Nim
#where the piles have size <=N1 and <=N2 <=N1 and <=N3 pennies
Nim3:=proc(N1,N2,N3) local V,i,j,k,T,i1,j1,Ki,pos,Nei,n1,G:
V:=[seq(seq(seq([i,j,k],i=0..N1),j=0..N2),k=0..N3)]:


#T[[i,j,k]]=all positions reachable from [i,j,k] in one move

for i from 0 to N1 do
 for j from 0 to N2 do
  for k from 0 to N3 do
  T[[i,j,k]]:={seq([i1,j,k],i1=0..i-1),
             seq([i,j1,k],j1=0..j-1),
             seq([i,j,k1],k1=0..k-1)
}:
 od:
od:
od:


for i from 1 to nops(V) do

 Ki[V[i]]:=i:
od:

G:=[]:

for i from 1 to nops(V) do
 pos:=V[i]:
 Nei:=T[pos]:
 Nei:={seq(Ki[n1],n1 in Nei)}:
 G:=[op(G),Nei]:
od:

G,V:

end:

#Grab3i(S,i): given  a set of triplets looks
#for those that contain an i in the last position
#and returns the set w/o that i
Grab3i:=proc(S,i) local S1,s:
S1:={}:

for s in S do
 if s[3]=i then
    S1:=S1 union {[op(1..2,s)]}:
 fi:
od:

S1:

end: