######################################################################
##CHOMP.txt: Save this file as  CHOMP.txt                            #
## To use it, stay in the                                            #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read CHOMP.txt<Enter>                              #
##Then follow the instructions given there                           #
##                                                                   #
##Written by Doron Zeilberger, Rutgers University ,                  #
#DoronZeil at gmail dot com                                          #
######################################################################
 
#Created: 
 
print(`Created:  Aug. 8, 2018`):
print(` This is CHOMP.txt `):
print(`a short porgram (using the obvious algorithms) to compute the winning moves (if they exist) for Chomp positions`):
print(`written by Doron Zeilberger`):
print(`Acknowledgment: This short program was inspired by an email message fron Purui Zhang and Lu Yan, who wrote an`):
print(`intersting paper, suggesting a multi-player version. It would be nice to extend this program to their general game.`):
print(``):
print(`Please report bugs to DoronZeil at gmail dot com `):
print(``):
 print(`The most current version of this  package and paper`):
 print(` are  available from`):
 print(`http://sites.math.rutgers.edu/~zeilberg/  .`):

print(`---------------------------------------`):
 print(`For a list of the Supporting procedures type ezra1();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`---------------------------------------`):

print(`---------------------------------------`):
 print(`For a list of the MAIN procedures type ezra();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`---------------------------------------`):

with(combinat):

ezra1:=proc()

if args=NULL then
 print(` The supporting procedures are: KickZ, Bite, GB`):
 print(``):

else
ezra(args):
fi:

end:

ezra:=proc()

if args=NULL then
 print(`The main procedures are: IsL, IsLg, Paper, WM, WWM `):
 print(` `):



elif nops([args])=1 and op(1,[args])=Bite then
print(`Bite(L,i,j): inputs a Chomp position L, given as a weakly decreasing vectore of positive integers, and outputs the position`):
print(`obtained by Chomping at the the cell at row i and column j. Try:`):
print(`Bite([5,4,3],3,3);`):

elif nops([args])=1 and op(1,[args])=GB then
print(`GB(i,j): the set of good bites with an i by j chocolate bar. Try:`):
print(`GB(3,4);`):

elif nops([args])=1 and op(1,[args])=IsL then
print(`IsL(L): inputs a weakly-decreasing list of positive integers describing a Chomp position, where there`):
print(`there are L[1] squares at the to row, L[2] sequares at the second row, etc. and decides whether it is a  losing position`):
print(`(i.e. a P position, the Previous player won), or a winning position, i.e. an N position, (the Next player won).`):
print(`Outputs a pair [true,FAIL]  in the former case and [false, AwinningMove] in the latter case. Try:`):
print(`IsL([4,4,4]);`):

elif nops([args])=1 and op(1,[args])=IsLg then
print(`IsLg(L): Like IsL(L) (q.v.) but instead of giving only ONE winning move (when they exist) gives all of them. Try:`):
print(`IsLg([4,4,4]);`):

elif nops([args])=1 and op(1,[args])=KickZ then
print(`KickZ(L): kicks the 0 out of L, for example KickZ([4,5,0,0]) is [4,5]. Try: `):
print(` KickZ([5,4,3,0]); `):

elif nops([args])=1 and op(1,[args])=Paper then
print(`Paper(N): inputs a positive integer and outputs a paper extending the e Chomp Winning Bites Table in Winning Ways II, p. 599`):
print(`Try:`):
print(`Paper(8);`):

elif nops([args])=1 and op(1,[args])=WM then
print(`WM(N): inputs a positive integer N, and outputs for each 2<=j<=i<=N the winning moves when the initial position is a`):
print(`j by i chocolate bar, i.e. the position is [i,i,...,i] repeated j times.`):
print(`Try: `):
print(`WM(5); `):

elif nops([args])=1 and op(1,[args])=WWM then
print(`WWM(N): Winning Ways II, Ch.  18, Fig. 12,  p. 599 table for all 1<=a,b<=N. Try:`):
print(`WWM(6);`):






else
print(`There is no ezra for`,args):
fi:
 
end:


ez:=proc(): print(` IsL(L), IsLg(L), WM(N)  `): end:

#KickZ(L): kicks the 0 out
KickZ:=proc(L) local i:
for i from nops(L) by -1 while L[i]=0 do od:
[op(1..i,L)]:
end:

#Bite(L,i,j): the position obtained by biting at cell [i,j] of position L.
#Try:
#Bite([3,2,1],1,1);
Bite:=proc(L,i,j) local i1:
KickZ([op(1..i-1,L),seq(min(j-1,L[i1]),i1=i..nops(L))]):
end:





#IsL(L): is the position losing:
IsL:=proc(L) local gu,i,j,gu1:
option remember:
if L=[1] then
 RETURN([true,FAIL]):
fi:


gu:={seq([1,j],j=2..L[1])} union {seq(seq([i,j],j=1..L[i]),i=2..nops(L))}:


for gu1 in gu do

if  IsL(Bite(L,op(gu1)))[1] then

  RETURN([false,gu1]):
fi:
od:
[true,FAIL]:
end:

#IsLg(L): is the position losing:
IsLg:=proc(L) local gu,i,j,gu1,mu:
option remember:
if L=[1] then
 RETURN([true,FAIL]):
fi:


gu:={seq([1,j],j=2..L[1])} union {seq(seq([i,j],j=1..L[i]),i=2..nops(L))}:

mu:={}:

for gu1 in gu do
 
if  IsL(Bite(L,op(gu1)))[1] then
 mu:=mu union {gu1}:
fi:

od:

if mu<>{} then
[false,mu]:
 else
[true,FAIL]:
fi:

end:


#WM(N): all the winning moves for a rectangular chocolate bar
WM:=proc(N) local i,j,lu,lu1,mu:
 lu:=[]:
 for i from 2 to N do
  lu1:=[]:
  for j from 2 to i do
    mu:=IsLg([i$j]):

    if mu[1]=true then
      print(`Something terrible happened, the Gale-Nash argument has been refuted`):
      RETURN(FAIL,lu):
     else
      lu1:=[op(lu1),mu[2]]:
      if nops(mu[2])=1 then
        print(`For a `, j, `by `, i, `chocolate bar there is only one winning move, chomp at cell`, mu[2][1]):
      else
         print(`For a `, j, `by `, i, `chocolate bar there are`,nops(mu[2]),  `winning moves, chomp at any of the cells`, mu[2]):
    fi:
  fi:
   od:
  lu:=[op(lu),lu1]:
 od:
    
lu:   

end:

#GB(i,j): the set of good bites with an i by j chocolate bar. Try:
#GB(3,4);
GB:=proc(i,j) local mu,mu1:

if i=1 and j=1 then
   RETURN(0):
fi:
if j>i then
 mu:=GB(j,i):
 RETURN({seq([mu1[2],mu1[1]],mu1 in mu)}):
fi:

 mu:=IsLg([i$j]):

 if mu[1] then
  RETURN(FAIL):
 fi:

mu[2]:

end:

#Targem1(a,b,mu): translates to the notation of Winning Ways II, Ch.  18, Fig. 12,  p. 599 the pair mu  with an a by b chocolate box.
#Try:
#Targem1(5,3,[2,1]);
Targem1:=proc(a,b,mu) 
[a-mu[2]+1,b-mu[1]+1]:
end:

#Targem1n(a,b,mu): translates to the notation of Winning Ways II, Ch.  18, Fig. 12,  p. 599 the pair mu  with an a by b chocolate box.
#Try:
#Targem1n(5,3,[2,1]);
Targem1n:=proc(a,b,mu)  local x:
cat(a-mu[2]+1,x,b-mu[1]+1):

end:

#Targemn(a,b,mu): translates to the notation of Winning Ways II, Ch.  18, Fig. 12,  p. 599 the pair mu  with an a by b chocolate box.
#for sets. Try:
#Targemn(5,3,{[2,1]});
Targemn:=proc(a,b,S) local mu1:
if S=0 then
 0:
else
{seq(Targem1n(a,b,mu1),mu1 in S)}:
fi:
end:

#WWM(N): Winning Ways II, Ch.  18, Fig. 12,  p. 599 table for all 1<=a,b<=N. Try:
#WWM(6);
WWM:=proc(N) local i,j:
matrix([seq([seq(Targemn(i,j,GB(i,j)),j=1..N)],i=1..N)]):
end:

#Paper(N): inputs a positive integer and outputs a paper extending the e Chomp Winning Bites Table in Winning Ways II, p. 599
#Try:
#Paper(8);
Paper:=proc(N) local gu:
print(``):
print(`Extension of the Chomp Winning Bites Table in Winning Ways II, p. 599`):
print(``):
print(`By Shalosh B. Ekhad `):
print(``):
gu:=WWM(N):
print(``):
print(`You start with an a by b chocolcate bar where the top-left sequare is poisoned and anyone eating it would die.`):
print(`At each turn a player takes a bite removing all square to its right and below it. David Gale famously`):
print(`proved that the first player has a winning move, but finding it (or them) is not that easy!`):
print(`In the classic Winning Ways, v. 2, p. 509 there is a table of the good bites. Here we extend it to all`):
print(`a by b chocolate bars with 1<=a,b<=`, N):
print(``):
print(gu):
end: