/* 

  Farmer, Wolf, Sheep/Goat & Cabbage problem, CP version in Picat.

  This is a port of the Prolog clp(fd) model from
  Playing With Prolog:
  Prolog Essentials clp(fd) Lecture EU session
  https://www.youtube.com/watch?v=325bpuYbs_0&feature=em-lbcastemail
  about 44min...


  Coding: 
  * 1: is on the left bank
  * 0: is on the right bank

  Goal: All on the right bank (i.e. [0,0,0,0])

  The two optimal solutions (7 steps) are:

    [F,W,S,C]
    [1,1,1,1] = [F,W,S,C] = []
    [0,1,0,1] = [W,C] = [F,S]
    [1,1,0,1] = [F,W,C] = [S]
    [0,0,0,1] = [C] = [F,W,S]
    [1,0,1,1] = [F,S,C] = [W]
    [0,0,1,0] = [S] = [F,W,C]
    [1,0,1,0] = [F,S] = [W,C]
    [0,0,0,0] = [] = [F,W,S,C]
    num_steps = 8

    [F,W,S,C]
    [1,1,1,1] = [F,W,S,C] = []
    [0,1,0,1] = [W,C] = [F,S]
    [1,1,0,1] = [F,W,C] = [S]
    [0,1,0,0] = [W] = [F,S,C]
    [1,1,1,0] = [F,W,S] = [C]
    [0,0,1,0] = [S] = [F,W,C]
    [1,0,1,0] = [F,S] = [W,C]
    [0,0,0,0] = [] = [F,W,S,C]
    num_steps = 8


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

*/

import cp.


main => go.

go ?=>
  L = ["F","W","S","C"],
  % Start state: all on the left bank
  wsc([[0,0,0,0]], M),
  solve(M.vars),
  println(L),
  foreach(Step in M)
    % convert to number for easy recognition
    % C = sum([Step[I]*2**(4-I) : I in 1..4]),
    LeftSide  = [L[I] : I in 1..4, Step[I] == 1],
    RightSide = [L[I] : I in 1..4, Step[I] == 0],
    println(Step=LeftSide=RightSide)
  end,
  println(num_steps=M.len),
  nl,
  fail,
  nl.

go => true.


% goal state
wsc(WSC1,WSC2) ?=>
   WSC1 = [[1,1,1,1]|R],
   WSC2 = [[1,1,1,1]|R].
% actions
wsc(WSC1,M) ?=>
  WSC1 = [[F,W,S,C]|R],
  [NF,NW,NS,NC] = NM,
  NM :: 0..1,
  NF #!= F, % move the farmer
  % move max one thing
  (NW #= W #/\ NS #= S) #\/
  (NS #= S #/\ NC #= C) #\/
  (NW #= W #/\ NC #= C),
  % game rules
  NS #= NC #=> NF #= NS,
  NW #= NS #=> NF #= NW,
  wsc([NM,[F,W,S,C]|R], M).