/* Ecrit par Nicolas Zinovieff (p6mip138) */

/*
	etatactuel(grande(X),petite(Y)) signifie que la grande contient X litres et la petite Y litres
*/

/* remplir - vider les cruches */
etatsuivant(etatactuel(grande(X),petite(Y)),etatactuel(grande(8),petite(Y))) :- X < 8.
etatsuivant(etatactuel(grande(X),petite(Y)),etatactuel(grande(X),petite(5))) :- Y < 5.
etatsuivant(etatactuel(grande(X),petite(Y)),etatactuel(grande(0),petite(Y))) :- X > 0.
etatsuivant(etatactuel(grande(X),petite(Y)),etatactuel(grande(X),petite(0))) :- Y > 0.
/* vider la grande dans la petite */
etatsuivant(etatactuel(grande(XX),petite(YY)),etatactuel(grande(X),petite(5))) :- XX > (5 - YY), X is XX - (5 - YY), X < XX.
etatsuivant(etatactuel(grande(XX),petite(YY)),etatactuel(grande(0),petite(Y))) :- XX =< (5 - YY), Y is YY + XX, Y > YY.
/* vider la petite dans la grande */
etatsuivant(etatactuel(grande(XX),petite(YY)),etatactuel(grande(8),petite(Y))) :- YY > (8 - XX), Y is YY - (8 - XX), Y < YY.
etatsuivant(etatactuel(grande(XX),petite(YY)),etatactuel(grande(X),petite(0))) :- YY =< (8 - XX), X is XX + YY, XX+YY > XX.

/* recherche avec accumulateur */
possible_gallons(X, X, CList, CList).
possible_gallons(X, Y, CList, List) :-
	etatsuivant(X, Z),
	not(member(Z, CList)),
	possible_gallons(Z, Y, [Z | CList], List).

chemin_gallons(X, Y, FoundPath) :- possible_gallons(X, Y, [X], FoundPath).

/* recherche en largeur */
recherche_largeur(X,Y,C) :- cherche(Y,[[X]],C).

cherche(Y,[[Y|Chs]|_],[Y|Chs]) :- !. /* la solution est la bonne mais inversee */
cherche(Y,[[S|Chs]|AutresChemins],Sol) :- findall([Suc,S|Chs],etatsuivant(S,Suc),NewChemins),
											append(AutresChemins,NewChemins,Chemins),
											cherche(Y,Chemins,Sol).

but_gallons :- chemin_gallons(etatactuel(grande(0),petite(0)),etatactuel(grande(4),petite(0)), Liste),reverse(Liste,R),write(R).
but_gallons2 :- recherche_largeur(etatactuel(grande(0),petite(0)),etatactuel(grande(4),petite(0)), Liste),reverse(Liste,R),write(R).