######################################################################
## Cannibals.txt: Save this file as  Cannibals.txt to use it,     #
# stay in the                                                        #
## same directory, get into Maple (by typing: maple <Enter> )        #
#then type: read `Cannibals.txt`: <Enter>                            #
## Then follow the instructions given there                          #
##                                                                   #
## Written by George Spahn and Doron Zeilberger, Rutgers University ,#
##  DoronZeil@gmail.com      .                                       # 
######################################################################

with(combinat):

Digits:=100:

print(`First Written: Oct. 2022: tested for Maple 20  `):
print():
print(`This is Cannibals.txt, A Maple package`):
print(`accompanying George Spahn and Doron Zeilberger's  article: `):
print(` Variations on the Missionaries and Cannibals Problem`):
print(`-------------------------------`):

print(`-------------------------------`):
print():
print(`The most current version is available on WWW at:`):
print(` http://www.math.rutgers.edu/~zeilberg/tokhniot/Cannibals.txt .`):
print(`Please report all bugs to: zeilberg at math dot rutgers dot edu .`):
print():
print(`-------------------------------`):
print(`For general help, and a list of the MAIN functions,`):
print(` type "ezra();". For specific help type "ezra(procedure_name);" `):

print(`-------------------------------`):
print(`For a list of the supporting functions type: ezra1();`):
print(`For help with a specific procedure, type "ezra(procedure_name);"`):
print():
 print(`-------------------------------`):


ezra1:=proc()
if args=NULL then

print(` The supporting procedures are:  AllS, IGS, kids, KidPaths, PathsK, Rev `):
print(` `):

else
 ezra(args):
fi:
end:

ezra:=proc()

if args=NULL then

print(` Cannibals.txt: A Maple package for solving and exploring Missionaries and Cannibals puzzles`):
print(`The main procedures are : Nums, Sols, SO`):



elif nargs=1 and args[1]=AllS then
print(`AllS(M,C,B,d): inputs positive integers M and C and non-neg. integer d and outpts all the reachable states from the initial state [M,C,1]`):
print(`AllS(3,3,2,0):`):

elif nargs=1 and args[1]=kids then
print(`kids(S,M,C,d,B): all the states reachable from the state S with boat capacity B, in a (M,C,d,B) Missionaries and Cannibals puzzle, where initially there are M missionaries`):
print(`C cannibals, a rowboad that can take at most B passengers and at every time, at both banks and the boat the number of Missiopnaries minus the Number of Cannibals is >=d. Try:`):
print(`kids([3,3,1],3,3,0,2);`):

elif nargs=1 and args[1]=KidPaths then
print(`KidPaths(M,C,B,d,P): all the continuations of the path P in a Missionaries and Cannibals puzzle (M,C,B,d). Try:`):
print(`KidPaths(3,3,2,0,[[3,3,1]]);`):

elif nargs=1 and args[1]=IGS then
print(`IGS(S,M,C,d): Given a state S decides whether it is a good state. Try:`):
print(`IGS([3,3,0],3,3,1);`):

elif nargs=1 and args[1]=Nums then
print(`Nums(M,C,B,d): The number of crossings it takes to solve the (M,C,B,d)-Missionaries and Cannibals problem followed by the number of ways of doing it. Try: `):
print(`Nums(3,3,2,0);`):

elif nargs=1 and args[1]=PathsK then
print(`PathsK(M,C,B,d,K): all the paths of length K in a Missionaries and Cannibals puzzle with M missionaries, C cannibals, Boad capacity B, and always #missionaries-#cannicabls>=d on either banks if there are missionaries present`):
print(`on either bank and in the boat. Try:`):
print(`PathsK(3,3,2,0,9);`):

elif nargs=1 and args[1]=Rev then
print(`Rev(P,M,C): The reverse of the path P. Try:`):
print(`Rev([[3,3,1],[2,2,0]],3,3);`):

elif nargs=1 and args[1]=Sols then
print(`Sols(M,C,B,d): All the minimal solutions to  a Missionaries and Cannibals puzzle with M missionaries, C cannibals, Boat maximum occupancy B, and`):
print(`the reqiorement at at all time #missionaries-#cannibals>=d on both banks and the boat if any missiobaries are present. Try:`):
print(`Sols(3,3,2,0);`):


elif nargs=1 and args[1]=SO then
print(`SO(M,C,B,d,S): Given a solution found using Sols(M,C,B,d), gives a detailed verbose rendition. Try`):
print(`SO(3,3,2,0,Sols(3,3,2,0)[1]);`):

else
 print(`There is no such thing as`, args):

fi:



end:



#IGS(S,M,C,d): Given a state S decides whether it is a good state. Try:
#IGS([3,3,1],3,3,1);

IGS:=proc(S,M,C,d) :

if not (S[1]>=0 and S[1]<=M and S[2]>=0 and S[2]<=C and member(S[3],{0,1}) ) then
 RETURN(false):
fi:

if S[1]>0 and S[2]>0  and S[1]-S[2]<d then
 RETURN(false):
fi:


if M-S[1]>0 and C-S[2]>0 and (M-S[1])-(C-S[2])<d then
 RETURN(false):
fi:



true:
end:



#kids(S,M,C,d,B): all the states reachable from the state S with boat capacity B
kids:=proc(S,M,C,d,B) local b1,b2,B1,gu,S1:
option remember:
if not (S[3]=0 or S[3]=1) then
 RETURN(FAIL):
fi:

if not IGS(S,M,C,d) then
 RETURN(FAIL):
fi:

gu:={}:

if S[3]=1 then

for B1 from 1 to B do
 for b1 from 0 to B1 do
 b2:=B1-b1:
 if b1<=S[1] and b2<=S[2] then
 if  not (b2>0 and b1>0 and b1-b2<d) then

 S1:=[S[1]-b1,S[2]-b2,0]:
  if IGS(S1,M,C,d) then
    gu:=gu union {S1}:
  fi:
fi:
fi:
 od:
od:


elif S[3]=0 then
for B1 from 1 to B do
 for b1 from 0 to B1 do
 b2:=B1-b1:
  if b1<=M-S[1] and b2<=C-S[2] then
  if  not (b2>0 and b1>0 and b1-b2<d) then
 S1:=[S[1]+b1,S[2]+b2,1]:
  if IGS(S1,M,C,d) then
    gu:=gu union {S1}:
  fi:
fi:
fi:
 od:
od:
fi:

gu:

end:


#AllS(M,C,B,d): inputs positive integers M and C and non-neg. integer d and outpts all the reachable states from the initial state [M,C,1]
#AllS(3,3,2,0):
AllS:=proc(M,C,B,d) local gu,S,gu1,gu2:
option remember:
if not IGS([M,C,1],M,C,d) then
 RETURN(FAIL):
fi:


gu:={[M,C,1]}:

gu1:=gu union {seq(op(kids(S,M,C,d,B)), S in gu)} :

while gu<>gu1 do
 gu2:=gu1 union {seq(op(kids(S,M,C,d,B)), S in gu1)} :
gu:=gu1:
gu1:=gu2:
od:

gu1:

end:


#KidPaths(M,C,B,d,P): all the continuations of the path P in a Missionaries and Cannibals puzzle (M,C,B,d). Try:
#KidPaths(3,3,2,0,[[3,3,1]]);
KidPaths:=proc(M,C,B,d,P) local gu,gu1:
option remember:
gu:=kids(P[-1],M,C,d,B) minus {op(P)}:
{seq([op(P),gu1],gu1 in gu)}:
end:


#PathsK(M,C,B,d,K): all the paths of length K in a Missionaries and Cannibals puzzle with M missionaries, C cannibals, Boad capacity B, and always #missionaries-#cannicabls>=d on either banks of there areboth cannicbals and missionaries
#on either bank. Try:
#PathsK(3,3,2,0,9);
PathsK:=proc(M,C,B,d,K) local gu,gu1:
option remember:
if K=1 then
RETURN({[[M,C,1]]}):
fi:

gu:=PathsK(M,C,B,d,K-1):

{seq(op(KidPaths(M,C,B,d,gu1)),gu1 in gu)}:
end:


#Sols(M,C,B,d): All the minimal solutions to the puzzle. Try:
#Sols(3,3,2,0);
Sols:=proc(M,C,B,d) local gu,gu1,K,lu:

for K from 1 to nops(AllS(M,C,B,d)) do
gu:=PathsK(M,C,B,d,K);
lu:={}:
for gu1 in gu do
if gu1[-1]=[0,0,0] then
 lu:=lu union {gu1}:
fi:
od:
if lu<>{} then
 RETURN(lu):
fi:
od:

lu:
end:

#Rev(P,M,C): The reverse of the path P
Rev:=proc(P,M,C) local i,k:
k:=nops(P):
[seq([M-P[k+1-i][1],C-P[k+1-i][2],1-P[k+1-i][3]],i=1..k)]:
end:

#SO(M,C,B,d,S): spelling out the solution S
SO:=proc(M,C,B,d,S) local sira,i:

if not (type(S,list) and nops(S) mod 2=0) then
 RETURN(FAIL):
fi:

print(`Solution of a Missonaries and Cannibals River Crossing Problem`):
print(``):
print(M, `missionaries and `, C, `cannibals have to cross a river using a rowboat that can have at most`, B, `passengers `):
print(``):
print(`At no time, on either bank of the river, and in the boat, should the excess of missionaries to cannibals be less than`, d, `if there are both cannibals and  missionaries present, of course` ):
print(``):
print(`How to cross the river safely?`):
print(``):
print(`Here is how to do it in`, nops(S)/2-1, `double-crossings followed by one last crossing`):
print(``):




for i from 1 to nops(S)/2-1 do

print(`Right now the boat is at the Originating bank and there are`, S[2*i-1][1], `missionaries and `,  S[2*i-1][2], `cannibals there while there are`, M-S[2*i-1][1], ` missionaries and `, C-S[2*i-1][2] , ` canniabls on the other bank `):

 sira:=[S[2*i-1][1]-S[2*i][1], S[2*i-1][2]-S[2*i][2]]:
print(``):
print(`For the`, i, ` -th crossing from the Originating bank to the Terminal bank, put on the boat`, sira[1], ` missionaries and `, sira[2], `cannibals `):
print(``):
 sira:=[S[2*i+1][1]-S[2*i][1], S[2*i+1][2]-S[2*i][2]]:
print(``):
print(`Right now  the boat is at the Terminating bank and there are`, M-S[2*i][1], `missionaries and `,  C-S[2*i][2], `cannibals there while there are`, S[2*i][1], ` missionaries and `, S[2*i][2] ,`  canniabls on the other bank `):
print(``):
print(`For the`, i, ` -th crossing from the Terminal bank back to the Originating bank, put on the boat`, sira[1], ` missionaries and `, sira[2], `cannibals `):
print(``):
od:

 sira:=[S[-2][1]-S[-1][1], S[-2][2]-S[-1][2]]:
print(``):
print(`Now the boat is at the Originating bank and there are`, S[-2][1], `missionaries and `,  S[-2][2], `cannibals there while there are`, M-S[-2][1], ` missionaries and `, C-S[-2][2] , ` canniabls on the other bank `):
print(``):
print(`Finally for the `, nops(S)/2, ` -th crossing from the Original  bank to the Terminal bank, put on the boat`, sira[1], ` missionaries and `, sira[2], `cannibals `):
print(``):
print(`Now everyone is in the Terminal bank`):
print(`------------------------------------------------`):

end:


#Nums(M,C,B,d): The number of crossings it takes to solve the (M,C,B,d)-Missionaries and Cannibals problem followed by the number of ways of doing it.
#Try:
#Nums(3,3,2,0);
Nums:=proc(M,C,B,d) local gu:
gu:=Sols(M,C,B,d):
if gu={} then
 RETURN(FAIL):
else
[nops(gu[1]),nops(gu)]:
fi:
end: