:- use_module(library(clpfd)).
:- use_module(library(lists)).

%%% The cabbage and wolf puzzle
%%% State = [ Cabbage, Goat, Wolf, Man ]
%%% Values: 0 left, 1 boat, 2 right
%%% goal: establish if there is a plan of K
%%% steps that carries all items from left to right
%%% For K = 15 it founds 2 solutions

planning(K,Plan) :-
    N is 4*K,
    length(Plan,N),
    domain(Plan,0,2),
    begin([0,0,0,0],Plan),
    end(  [2,2,2,2],Plan),
    constrain(Plan),
    labeling([ff],Plan),
    stampa(Plan),nl.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% meta predicate that finds the minimum N
%%% such that a solution is found.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

meta :-
    statistics(walltime,_),
    meta(3).
    
meta(N) :-
    N < 30,    
    (planning(N,_),!,
     statistics(walltime,[_,T1]),
     format("Global time: ~q ms~n",[T1]),
     format("Solution in ~q stages~n",[N]);
     M is N + 4,
     meta(M)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

constrain(Plan) :-
    constrain(Plan,left),
    all_feasible(Plan).

%%% state transition: 4 cases

constrain([_,_,_,_],_):-!.
constrain([C1,G1,W1,M1,C2,G2,W2,M2|R],left):-
    left_to_boat(C1,C2),left_to_boat(G1,G2),
    left_to_boat(W1,W2), left_to_boat(M1,M2),
%%%    Boat in 1..2,    count(1,[C2,G2,W2,M2],#=,Boat),
    constrain([C2,G2,W2,M2|R],left_to_right).
constrain([C1,G1,W1,M1,C2,G2,W2,M2|R],left_to_right):-
    boat_to_right(C1,C2), boat_to_right(G1,G2),
    boat_to_right(W1,W2), boat_to_right(M1,M2),
    constrain([C2,G2,W2,M2|R],right).
constrain([C1,G1,W1,M1,C2,G2,W2,M2|R],right):-
    right_to_boat(C1,C2), right_to_boat(G1,G2),
    right_to_boat(W1,W2), right_to_boat(M1,M2),
%%%    Boat in 1..2,    count(1,[C2,G2,W2,M2],#=,Boat),
    constrain([C2,G2,W2,M2|R],right_to_left).
constrain([C1,G1,W1,M1,C2,G2,W2,M2|R],right_to_left):-
    boat_to_left(C1,C2), boat_to_left(G1,G2),
    boat_to_left(W1,W2), boat_to_left(M1,M2),
    constrain([C2,G2,W2,M2|R],left).
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
left_to_boat(X1,X2) :-
    X1 #= 0 #=> X2 #< 2,
    X1 #= 2 #=> X2 #= X1.
boat_to_right(X1,X2) :-
    X1 #= 1 #=> X2 #= 2, 
    X1 #\= 1 #=> X2 #= X1.
right_to_boat(X1,X2) :-
    X1 #= 2 #=> X2 #> 0,
    X1 #= 0 #=> X2 #= X1.
boat_to_left(X1,X2) :-
    X1 #= 1 #=> X2 #= 0,
    X1 #\= 1  #=> X2 #= X1.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% state check
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

all_feasible([]).
all_feasible([C,G,W,M|R]) :-
   feasible(C,G,W,M),
   all_feasible(R).

feasible(C,G,W,M):-   
%%% Mai capra e cavolo senza uomo
   (C #= G #=> C #= M),
%%% Mai capra e lupo senza uomo
   (W #= G #=> G #= M),
%%% Al massimo in due in barca
   Boat in 0 .. 2,
   count(1,[C,G,W,M],#=,Boat),
%%% Se qualcuno in barca, allora c'e' l'uomo:
   (W #= 1 #=> M #= 1),
   (C #= 1 #=> M #= 1),
   (G #= 1 #=> M #= 1).
   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% AUXILIARY PREDICATES:

begin([],_).
begin([A|R],[A|S]) :-
    begin(R,S).
end(Last,Plan) :-
    append(_,Last,Plan).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

stampa([]).
stampa([C,G,W,M|R]):-
    findall(I,nth(I,[C,G,W,M],0),Left),
    findall(J,nth(J,[C,G,W,M],1),Boat),
    findall(K,nth(K,[C,G,W,M],2),Right),
    write('left: '),
    stampalista(Left),
    write('boat: '),
    stampalista(Boat),
    write('right: '),
    stampalista(Right),nl,
    write('---------------------------------------'),
    write('---------------------------------------'),nl,    
    stampa(R).

stampalista(List) :-
    length(List,N),
    forall_write(List),
    M is 20 - 5*N,
    stampabianchi(M).
    
forall_write([]).
forall_write([N|R]) :-
    (N = 1, write('cabb ');
     N = 2, write('goat ');
     N = 3, write('wolf ');
     N = 4, write('man  ')),
    forall_write(R).

stampabianchi(0):-!.
stampabianchi(M):-
     write(' '),
     M1 is M-1,
     stampabianchi(M1).
     
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
