#######################
                       #        nim          #
                       #######################
#           Plays the game of nim with you interactively.
#         This game is played with several piles of tokens.
#      The number of piles and their sizes are entered by you.
#             The 2 players alternate turns, where a turn 
#           consists of picking a pile and taking at least
#      one token from that pile. The person who picks up the last
#      token from the last nonempty pile wins. User begins play.
#      The computer plays optimally.
#
#copyleft David Joyner, 5-23-96
#######################################################################

##
##asks user to set up nim piles
##
nimstart := proc ()
#largest number of piles is 10
local k, m, ans, numpiles, nimtable, maxpilesize, dummy,sizepile; 
#print(`Do you want to play Nim? (Enter "Y" or "N" - no semicolon)`);
#ans := readline(terminal); 
ans:=Y;
#print(`ans=`,ans,evalb(ans = ('Y') or ans = y)); 
if evalb(ans = ('Y') or ans = y) then 
 numpiles := readstat(`How many piles? (Enter a positive integer - use semicolon)`); 
 sizepile := array(1 .. numpiles); 
 for k to numpiles do print(`How many in `,k,`-th pile? (Enter a positive integer- no semicolon)`); 
 dummy := readline(terminal); 
 sizepile[k] := parse(dummy) od fi; 
#maxpilesize := `mod`(maxarray(sizepile,numpiles,1),10); 
maxpilesize := maxarray(sizepile,numpiles,1); 
#print(maxpilesize,sizepile); 
nimtable := ArrayOfPiles(sizepile,maxpilesize,numpiles);
print(evalm(nimtable)); 
print(`"nim sum" vector = `,nimber(sizepile,numpiles));
RETURN(sizepile,nimtable,maxpilesize,numpiles); 
end:

maxarray := proc (A::array, m::integer, n::integer) 
local i, j, s, maxa; 
if 1< m and 1 < n then s := seq(seq(A[i,j],i = 1 .. m),j = 1 .. n); 
 maxa := max(s); 
 RETURN(maxa) 
fi; 
if 1 < m and n = 1 then s := seq(A[i],i = 1 .. m); 
 maxa :=max(s); 
 RETURN(maxa) 
fi; 
if m = 1 and 1 < n then s := seq(A[j],j = 1 .. n); 
 maxa := max(s); 
 RETURN(maxa) 
fi; 
end:

##
##sets up array of piles
##
ArrayOfPiles:=proc(piles::array,m::integer,n::integer)
local i,j,piletable,isempty;
global dummy;
isempty:=1;
piletable := array(1 ..m,1 .. n); 
for j from 1 to n do 
 for i from 1 to m do
  if i<= piles[j] then 
   piletable[i,j] := `*`;
   isempty:=0;
    else piletable[i,j] := ` ` 
  fi 
 od 
od; 
if isempty=1 then dummy:=N; RETURN fi;
RETURN(piletable);
end: 

##
##         initialization, set up, and play solitaire nim
##                  
##
playnim := proc () 
local i, j, ans, pilenum, numpick, newpilesize, 
initdata, sizepile, maxpilesize, numpiles; 
global dummy;
dummy := Y; 
initdata := nimstart();
sizepile := initdata[1]; 
maxpilesize := initdata[3]; 
numpiles := initdata[4];
while dummy = Y do 
 ans := readstat(`Enter "Q" to quit, "P" to play (use semi-colon) `);
 if ans = Q then dummy:= N; break fi; 
 print(`Pick a pile number and the number of *'s you want to take from that pile`);
 pilenum := readstat(`Pile number (use semicolon) `); 
 numpick := readstat(`Number of *'s from that pile (use semicolon) `); 
 newpilesize := max(0,sizepile[pilenum]-numpick); 
 sizepile[pilenum] := newpilesize; 
 print(`Your nim-piles are `,ArrayOfPiles(sizepile,maxpilesize,numpiles))
od; 
print(`Thanks for playing`);
end:

##
## simple routine to help compute "nimbers"
##
padic_coeffs:=proc(n::integer,p::integer)
 local a,b,c,i,k,vtemp,v;
a:=padic[evalp](n,p);
#print(`padic 1`,a);
b:=op(2,[op(op(1,a))]);
#print(`padic 2`,b);
c:=[seq(0,i=1..b),op(op(3,[op(op(1,a))]))];
#print(`padic 3`,c);
vtemp:=[seq(c[i],i=1..nops(c)-1)];
#print(`padic 4`,vtemp);
k:=nops(vtemp);
v:=[op(vtemp),seq(0,i=1..10-k)];
#print(`padic 5`,v,k);
RETURN(v);
end:

##
##a help file
##
rules:=proc()
print(`This game is played with several piles of tokens.`);
print(`The number of piles and their sizes are entered into MAPLE.`);
print(`This game is played with 2 players, each taking turn.`);
print(`Each turn consists of picking a pile and taking at least`);
print(`one token from that pile. The person who picks up the last`);
print(`token from the last nonempty pile wins. User begins play.`);
end:

##
##This proc makes the computers nim move
##
computer_nim_move:=proc(piles::array,m::integer,numpiles::integer)
 local i,j,maxpilenum,temppiles,maxpile,temp,stoop,k;
 global dummy;
temppiles:=piles;
stoop:=0;
print(`"nim sum" vector = `,nimber(piles,numpiles));
#print(`even_position = `,even_position(piles,numpiles));
maxpile:=max(seq(piles[i],i=1..numpiles));
#print(`computer_nim_move 1 `,maxpile);
if maxpile=0 then 
  print(`No more moves, you win. `);
  dummy:=N;
  RETURN(piles); 
fi;
for i from 1 to numpiles do
#print(`1`,i);
 if piles[i]=maxpile then
  maxpilenum:=i;
 fi;
od;
for i from 1 to numpiles do
 if stoop<>1 then
  for j from 1 to piles[i] do
   temppiles[i]:=piles[i]-j; 
#   temppiles:=convert([seq(temppiles[k],k=1..numpiles)],array);
   if even_position(temppiles,numpiles)=1 then 
#print(`2 nim sum = `,nimber(temppiles,numpiles));
#print(`2 even_position = `,even_position(temppiles,numpiles));
      stoop:=1;
      break; 
   else 
#print(`3 nim sum of `,temppiles,` = `,nimber(temppiles,numpiles));
#print(`3 even_position = `,even_position(temppiles,numpiles),piles);
temppiles[i]:=temppiles[i]+j;
   fi;
  od;
 fi; ##if stoop
od;
maxpile:=max(seq(temppiles[i],i=1..numpiles));
if maxpile=0 then 
  print(`Computer takes last token, you lose. `);
  dummy:=N;
  RETURN(piles); 
fi;
RETURN(temppiles);
end:

##
## another simple routine to help compute "nimbers"
##
even_position:=proc(piles::array,numpiles::integer)
 local i,j,v,even0;
 global dummy;
even0:=1;
v:=nimber(piles,numpiles);
for j from 1 to numpiles do
   if `mod`(v[j],2)<>0 then even0:=0; break; fi;
od;
RETURN(even0);
end:

##
## another simple routine to help compute "nimbers"
##
nimber:=proc(piles::array,numpiles::integer)
 local i,number;
 global dummy;
number:=[seq(0,i=1..10)];
for i from 1 to numpiles do
 if piles[i]>0 then 
   number:=number+padic_coeffs(piles[i],2);
 fi;
od;
RETURN(number);
end:

##
##         initialization, set up, and play nim with 
##                     the computer
##
play_nim_with_PC := proc () 
local i, j, ans, pilenum, numpick, newpilesize, 
initdata, sizepile, maxpilesize, numpiles; 
global dummy;
dummy := Y; 
initdata := nimstart();
sizepile := initdata[1]; 
maxpilesize := initdata[3]; 
numpiles := initdata[4];
while dummy = Y do 
# ans := readstat(`Enter "Q" to quit, "P" to play (use semi-colon) `);
# if ans = Q then dummy:= N; break fi; 
 print(`Pick a pile number and the number of *'s you want to take from that pile`);
 pilenum := readstat(`Pile number (use semicolon) `); 
 numpick := readstat(`Number of *'s from that pile (use semicolon) `); 
 newpilesize := max(0,sizepile[pilenum]-numpick); 
 sizepile[pilenum] := newpilesize; 
 print(`Your nim-piles are `,ArrayOfPiles(sizepile,maxpilesize,numpiles));
 sizepile:=computer_nim_move(sizepile,maxpilesize,numpiles);
 if dummy<>N then 
  print(`Computer moved: `,ArrayOfPiles(sizepile,maxpilesize,numpiles));
 fi;
od; 
print(`Thanks for playing`);
end:
 
helpnim:=proc()
print(`Type "rules()'" for rules, "playnim();" to play`);
print(`Nim solitaire, and "play_nim_with_PC();" to play Nim against the computer`);
end:

save `nim.m`;