/*********************************************************************************/
/**                                                          	     		**/
/**  Zastosowanie programowania w logice do poszukiwania ścieżki w grafie na    **/
/**  przykładzie problemu "dwóch dzbanków".           				**/
/**                                                          	     		**/
/**  Dane są dwa dzbanki: 3-litrowy i 4-litrowy oraz ujęcie wody. W stanie 	**/
/**  początkowy, obydwa dzbanki są puste. Znaleźć sposób osiągnięcia stanu	**/
/**  końcowego, w którym dzbanek 4-litrowy jest pusty a dzbanek 3-litrowy	**/
/**  zawiera 2 litry wody. Jednocześnie zakłada się, że można w tym celu	**/
/**  można wykonywać wyłącznie wymienione niżej działania.			**/
/**  1. Każdy dzbanek można (całkowicie) napełnić lub opróżnić korzystając z	**/
/**     ujęcia wody.								**/
/**  2. Można przelewać wodę z jednego dzbanka do drugiego aż do napełnienia	**/
/**	dzbanka "docelowego" lub opróżnienia dzbanka "źródłowego".		**/
/**                                                          	     		**/
/**  Zapytanie o rozwiązanie:							**/
/**     ?- solve([0,0],[0,2],P).                  				**/
/**                                                          	     		**/
/**  Zapytanie o rozwiązanie najkrótsze:					**/
/**    ?- findall(P,solve([0,0],[0,2],P),LP),min_length(LP,M,_).		**/
/**  Wynikiem jest wartość zmiennej M. Podcel z predefiniowanym predykatem 	**/
/**  findall/3 tworzy listę LP wszystkich rozwiązań rozpatrywanego problemu.	**/ 
/**  Predykat min_length(+LLst,?Min,?MinLen) w ogólności służy do znajdowania	**/
/**  na liście list LLst elementu Min o długości MinLen takiej, że długość 	**/
/**  żadnego innego elementu listy LLst nie jest mniejsza od MinLen. W toku	**/
/**  nawrotów, pod zmienną Min zostają podstawione wszystkie elementy listy 	**/
/**  LLst, spełniające ww. warunek.						**/
/*********************************************************************************/

solve(B,E,P):-
	path(B,E,[B],P1),
	reverse(P1,P).

path(B,B,W,W).
path(B,E,Wp,W):-
	next_state(B,B1),
	not(member(B1,Wp)),
	path(B1,E,[B1|Wp],W).

next_state([X,Y],[0,Y]) :- X > 0.
next_state([X,Y],[X,0]) :- Y > 0.
next_state([X,Y],[4,Y]) :- X < 4.
next_state([X,Y],[X,3]) :- Y < 3.
next_state([X,Y],[4,Z]) :- X < 4, Z is Y - (4 - X), Z >= 0.
next_state([X,Y],[Z,3]) :- Y < 3, Z is X - (3 - Y), Z >= 0.
next_state([X,Y],[Z,0]) :- Y > 0, Z is X + Y, Z =< 4.
next_state([X,Y],[0,Z]) :- X > 0, Z is X + Y, Z =< 3.

/*********************************************************************************/

min_length([H],H,LH) :- length(H,LH), !.
min_length([H|T],MT,LMT) :-
  length(H,LH), 
  min_length(T,MT,LMT),
  LMT =< LH.
min_length([H|T],H,LH) :-
  length(H,LH), 
  min_length(T,_,LMT),
  LH =< LMT,!.