:- module(_, [solve_jugs/3], [assertions, regtypes, nativeprops]).

%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %% jugs.pl -- The jugs problem coded in prolog
 %% AFSID           : $__Header$
 %% Author          : Manuel Carro Li~nares
 %% Created On      : Sun Feb 28 22:20:48 1993
 %% Last Modified By: MCL
 %% Last Modified On: Tue Jun  8 19:12:48 1999
 %% Update Count    : 24
 %% Status          : Lengthy and verbose, but correct.

 %% Problem:
 %% Write the prolog code for the water jugs problem:
 %% There are two jugs, one holding 3 and the other 5 gallons of water.
 %% A number of things can be done with the jugs:  they can be filled,
 %% emptied, and dumped one into the other either until the poured-into
 %% jug is full or until the poured-out-of jug is empty.  Devise a
 %% sequence of actions that will produce 4 gallons of water in the larger
 %% jug. Note that only integer values of water will be used.


 %% First of all, the problem, as I see it, is badly specified; if 4
 %% gallons of water have to remain in the larger jug, there is a smaller
 %% jug, isn't it? The text you posted (above) does not mention anything
 %% about it, but I vaguely understand that the jugs can contain 5 and 3
 %% gallons of water, so they both are full at the beginning. Well, let's
 %% start... 

 %% I prefer clear code as long as it does not impede performance...

 %% The basic data structure is a functor
 %% 
 %% jug(Water)
 %% 
 %% and the state of the problem is given by
 %% 
 %% state(SmallJug, LargeJug)
 %% 
 %% Actions are described as functors of the form
 %% 
 %% action(Action, Jug, Amount)
 %% 
 %% or
 %%
 %% action(Action, Jug)
 %% 
 %% where Amount refers to an integer number of gallons of water,
 %% Jug can be small or large and action can be empty, fill and pour, the
 %% latter meaning that the jug alluded to is poured a given amount of water
 %% into the other jug.
 %%
 %% The solution is given as a list of functors of the form
 %%
 %% step(Action, Resulting)
 %%
 %% Its meaning is obvious.
 %% 

 %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %% solve_jugs(+Initial, +Final, ?ListOfSteps): ListOfSteps is the
 %% solution to the jugs problem.
 %% E.g., Initial = state(jug(3),jug(5)),
 %%       Final = state(jug(0),jug(4))
 %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- entry solve_jugs(A,B,C) : state * state * term.
:- pred solve_jugs(A,B,C) : state * state * term.

solve_jugs(Initial, Final, Solution):-
	solve_jugs_(Initial, Final, Solution).

:- pred solve_jugs_(A,B,C) :
	state * state * term =>
	state * state * liststeps.

solve_jugs_(Initial, Final, Solution) :-
	solve_jugs_2(Initial, Final, [], Solution).

 %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %% solve_jugs_2(+CurrentState, ?GoalState, +StatesSoFar, ?Steps): Steps
 %% describe the history of the system from CurrentState to GoalState,
 %% having been traversed StatesSoFar.
 %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- pred solve_jugs_2(A,B,C,D) :
	state * state * liststates * term =>
	state * state * liststates * liststeps.

solve_jugs_2(End, End, _States, []).
solve_jugs_2(Actual, Goal, StatesSoFar, [step(Action, NextState)|Steps]):-
	\+ member(Actual, StatesSoFar),
	change_state_(Actual, NextState, Action),
	solve_jugs_2(NextState, Goal, [Actual|StatesSoFar], Steps).

:- regtype state/1.
state(state(J1,J2)) :- jug(J1), jug(J2).

:- regtype jug/1.
jug(jug(J1)) :- num(J1).

:- regtype action/1.
action(action(A,B)) :- atm(A), atm(B).
action(action(A,B,W)) :- atm(A), atm(B), num(W).

:- regtype liststeps/1.
liststeps([]).
liststeps([X|Xs]) :- step(X), liststeps(Xs).

:- regtype liststates/1.
liststates([]).
liststates([X|Xs]) :- state(X), liststates(Xs).

:- regtype step/1.
step(step(Action, Ns)) :- action(Action), state(Ns).

 %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %% change_state(+State, ?NextState, ?Action): Action is legal, and changes
 %% State into NextState
 %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- pred change_state_(A,B,C) : state * term * term => state * state * action.
change_state_(state(J1,J2), state(NJ1,NJ2),A):-
	change_state(J1, J2, NJ1, NJ2, A).

:- pred change_state(J1,J2,NJ1,NJ2,A) :
	jug * jug * term * term * term =>
	jug * jug * jug * jug * action.

change_state(jug(W1), W2, jug(0), W2, action(empty, small)):- W1 > 0.
change_state(W1, jug(W2), W1, jug(0), action(empty, large)):- W2 > 0.
%
change_state(jug(W1), W2, jug(3), W2, action(fill, small)):-  W1 < 3.
change_state(W1, jug(W2), W1, jug(5), action(fill, large)):-  W2 < 5.
%
change_state(jug(W1),jug(W2),jug(0),jug(NW2),action(pour,small,W1)):-
	W1 > 0,
	W1 + W2 =< 5,
	NW2 is W1 + W2.
change_state(jug(W1),jug(W2),jug(NW1),jug(5),action(pour,small,Am)):-
	W1 > 0,
	W1 + W2 > 5,
	NW1 is W1 + W2 - 5,
	Am is W1 - NW1.
%
change_state(jug(W1),jug(W2),jug(NW1),jug(0),action(pour,large,W2)):-
	W2 > 0,
	W1 + W2 =< 3,
	NW1 is W1 + W2.
change_state(jug(W1),jug(W2),jug(3),jug(NW2),action(pour,large,Am)):-
	W2 > 0,
	W1 + W2 > 3,
	NW2 is W1 + W2 - 3,
	Am is W2 - NW2.



 %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %% member(?Element, ?List): Element is an element of list List
 %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 %% member(Element, [Element|_]).
 %% member(Element, [_|RestOfElements]):-
 %% 	member(Element, RestOfElements).
