/* 

  Missionaries and cannibals problem in Picat.

  See
  http://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem

  Inspired by this Prolog code
  http://www-users.cs.york.ac.uk/~suresh/LAI/exercise1-sol/node3.html
  http://www-users.cs.york.ac.uk/~suresh/LAI/exercise1-sol/node6.html

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


import planner.

main => go.


go => 
   initial_state(Init),
   time(best_plan(Init,L)),
   foreach(Move in L) writeln(Move) end,
   nl,
   writeln(len=L.length),
   nl.

go2 => 
   initial_state(Init),
   time(best_plan_nondet(Init,L)),
   foreach(Move in L) writeln(Move) end,
   nl,
   writeln(len=L.length),
   fail,

   nl.



initial_state(Init) => Init=[3,3,left].

final(Goal) => Goal=[0,0,_].


legal([LM,LC,_]) ?=>
    %% left-hand side either missionaries greater-equals cannibals
    %%                 or    no missionaries and some cannibals
    ( LM >= LC ; (LM == 0, not(LC==0)) ),
    %% right-hand side either missionaries greater-equals cannibals
    %%                 or    no missionaries and some cannibals
    ( (3 - LM) >= (3 - LC) ; (LM == 3, not(LC==3)) ).


table
%% Move 1 missionary across to right
action(From,To,Move,Cost) ?=> 
    From=[LM,LC,left],
    To=[NLM,LC,right],
    Move=[m1_to_right,To],
    LM >= 1,
    NLM = LM - 1,
    legal([NLM,LC,right]),Cost=1.

%% Move 1 missionary across to left
action(From,To,Move,Cost) ?=> 
    From=[LM,LC,left],
    To=[NLM,LC,right],
    Move=[m1_to_left,To],
    (3 - LM) >= 1,
    NLM = LM + 1,
    legal([NLM,LC,right]),Cost=1.


%% Move 1 cannibal across to right
action(From,To,Move,Cost) ?=> 
    From=[LM,LC,left],
    To=[LM,NLC,right],
    Move=[c1_to_right,To],
    LC >= 1,
    NLC = LC - 1,
    legal([LM,NLC,right]),Cost=1.

%% Move 1 cannibal across to left
action(From,To,Move,Cost) ?=> 
    From=[LM,LC,right],
    To=[LM,NLC,left],
    Move=[c1_to_left,To],
    (3 - LC) >= 1,
    NLC = LC + 1,
    legal([LM,NLC,left]),Cost=1.

%% Move 2 missionaries across to right
action(From,To,Move,Cost) ?=> 
    From=[LM,LC,left],
    To=[NLM,LC,right],
    Move=[m2_to_right,To],
    LM >= 2,
    NLM = LM - 2,
    legal([NLM,LC,right]),Cost=1.

%% Move 2 missionaries across to left
action(From,To,Move,Cost) ?=> 
    From=[LM,LC,right],
    To=[NLM,LC,left],
    Move=[m2_to_left,To],
    (3 - LM) >= 2,
    NLM = LM + 2,
    legal([NLM,LC,right]),Cost=1.

%% Move 2 cannibals across to right
action(From,To,Move,Cost) ?=> 
    From=[LM,LC,left],
    To=[LM,NLC,right],
    Move=[c2_to_right,To],
    LC >= 2,
    NLC = LC - 2,
    legal([LM,NLC,right]),Cost=1.

%% Move 2 cannibals across to left
action(From,To,Move,Cost) ?=> 
    From=[LM,LC,right],
    To=[LM,NLC,left],
    Move=[c2_to_left,To],
    (3 - LC) >= 2,
    NLC = LC + 2,
    legal([LM,NLC,left]),Cost=1.


%% Move 1 missionary + 1 cannibal across to right
action(From,To,Move,Cost) ?=> 
    From=[LM,LC,left],
    To=[NLM,NLC,right],
    Move=[m1c1_to_right,To],
    LM >= 1,
    LC >= 1,
    NLM = LM - 1,
    NLC = LC - 1,
    legal([NLM,NLC,right]),Cost=1.


%% Move 1 missionary + 1 cannibal across to left
action(From,To,Move,Cost) => 
    From=[LM,LC,right],
    To=[NLM,NLC,left],
    Move=[m1c1_to_left,To],
    (3 - LM) >= 1,
    (3 - LC) >= 1,
    NLM = LM + 1,
    NLC = LC + 1,
    legal([NLM,NLC,left]),Cost=1.