/* (By F.Barbanera)
% gt : goat
% cb : cabbage
% wf : wolf
% shp: sheperd 
%
% rbc(L1,L2):  river banks configuration, the left bank containing the characters in L1 and the right bank the characters in L2
%
% admSeq(L1,L2): admissible Sequences: L1 is a sequence (a list) of river banks configuration such that the reverse of L1 appended
%                to L2 takes from the initial configuration, rbc([gt,cb,wf,shp],[]), to the final one rbc([],[gt,cb,wf,shp]
%
% safeBoatmove(RBC1,RBC2): it is possible to go from the river banks configuration RBC1 to RBS2 by means 
%                          a safe move of two characters on the boat 
%
% admSeq(RCBlist1,RCBlist2): the reverse of RCBlist1 appended to RBClist2 form an admissible solution from the initial to the final configuration.
%                            Admissible solution do not admit repeated configurations. 
% 
%
% 
% The main not elegant point in the program is that configurations are pairs of lists. They should be actually sets.
% So equality up to permutations is needed in some points.
%
*/






solution(L) :- admSeq([rbc([gt,cb,wf,shp],[])],L1),

               L=[rbc([gt,cb,wf,shp],[])|L1].








admSeq([RBC1|L1],[RBC2|L2]) :- safeBoatmove(RBC1,RBC2),                              
                               \+ presentin(RBC2,L1),
                               admSeq([RBC2,RBC1|L1],L2).


admSeq([rbc([],L)|_],[]) :- permutation(L,[gt,cb,wf,shp]).




%  presentin(RBC,RBC-list) determines whether an RBC is in a RBC-list


presentin(rbc(L1,L2),RcbList) :- member(rbc(L3,L4),RcbList), permutation(L3,L1), permutation(L4,L2).

    



safeBoatmove(RBC1,RBC2) :-  boatmove(RBC1,RBC2),
                            \+ unsafe(RBC2).


unsafe(rbc(L1,L2)) :- member(cb,L1), member(gt,L1),\+member(shp,L1);
                      member(gt,L1), member(wf,L1),\+member(shp,L1);
                      member(cb,L2), member(gt,L2),\+member(shp,L2);
                      member(gt,L2), member(wf,L2),\+member(shp,L2).


                      
                                

boatmove(rbc(L1,L2),rbc(L3,L4)) :- select(shp,L1,Rest), select(X,Rest,L3),(L4=[shp,X|L2]);
                                   select(shp,L2,Rest), select(X,Rest,L4),(L3=[shp,X|L1]);
                                   select(shp,L1,L3),(L4=[shp|L2]);
                                   select(shp,L2,L4),(L3=[shp|L1]).



permutation([], []).
permutation(List, [Element | Permutation]) :- select(Element, List, Rest),
                                              permutation(Rest, Permutation).







%%%% Soluzione alternativa. %%%%%%%%%%%


/* File: goat.pl
   Title: The goat problem

   A farmer has to cross a river with a wolf, a goat and a cabbage.
   He has a boat, but in the boat he can take just one thing.
   He cannot let the goat alone with the wolf or the goat with the cabbage. It's obvious why.

   What is the solution?

   */
   /*
   We describe the problem as Nodes in a graph and the solution means to find a path from
   the initial node to the final node.
   state = node is graph

   state(farmer(Bank),goat(Bank),cabbage(Bank),wolf(Bank)).

   Bank can be left (s) or right (d).  
   */

   start:- find(D),writelist(D),fail.

   /* fail is used here in order to force the interpreter to serach 
      for all the possible solutions (otherwise, by writing
      simply 
      start:- find(D),writelist(D). 
      we should explicitely ask the interpreter
      to look for the next solution by means of the space bar.)
   */



   /* at the beginning All are on the same bank
   */

initial(state(farmer(s),goat(s),cabbage(s),wolf(s))).
   /* at the end they have all to be on the other bank
   */
final(state(farmer(d),goat(d),cabbage(d),wolf(d))).

   /* opposite bank. A possible alternative definition is:   
   opp(Bank1,Bank2):- (Bank1=s,Bank2=d);(Bank1=d,Bank2=s).
   */

opp(s,d).  
opp(d,s).

   /* a bad state is a state to be avoided
   in this case:
   Goat cannot be left alone with wolf or cabbage
   The bank where the farmer is (T) has to be opposite
   Where the goat is together with the wolf or the cabbage
   */

bad(state(farmer(T),goat(G),cabbage(C),wolf(W))):- 
   				(G=W,opp(T,G)); (G=C,opp(T,G)).

find(Path):- initial(S),rez(S,Path).

   /* Farmer takes goat */
from(state(farmer(T),goat(T),cabbage(C),wolf(W)),
     state(farmer(T1),goat(T1),cabbage(C),wolf(W))):-opp(T,T1). 

   /* Farmer takes cabbage */
from(state(farmer(T),goat(G),cabbage(T),wolf(W)),
     state(farmer(T1),goat(G),cabbage(T1),wolf(W))):-opp(T,T1). 

   /* Farmer takes wolf */
from(state(farmer(T),goat(G),cabbage(C),wolf(T)),
     state(farmer(T1),goat(G),cabbage(C),wolf(T1))):-opp(T,T1). 

   /* Farmer goes alone */
from(state(farmer(T),goat(G),cabbage(C),wolf(W)),
     state(farmer(T1),goat(G),cabbage(C),wolf(W))):-opp(T,T1). 

rez(State,Sol):- bkt(State,[],Sol).

bkt(State,Path,[State|Path]):- final(State).
bkt(State,Path,Sol):- from(State,N1), 
                      \+bad(N1),
		      \+member(N1,Path),                    
                      bkt(N1,[State|Path],Sol).


writelist([]):- write('\n').
writelist([X|L]):- write(X),write('\n'),writelist(L).