/***********************************************************
taken from "Extension Table Built-ins for Prolog", 
by Chang-Guan Fa & Suzanne W. Dietrich
Software Practive and Experience, Vol22, No.7, 573-597, 1992.
***********************************************************/
top:-
    plan(jugs(0,0),Moves,_).

go:-
    cputime(Start),
    plan(jugs(0,0),Moves,_),
    cputime(End),
    write(Moves),nl,
    T is End-Start,
    write('TIME:'),write(T),nl.

:-table plan(+,-,min).
plan(State,[],Len):-final_state(State),!,Len=0.
plan(State,[Move|Moves],Len):-
    move(State,Move),
    update(State,Move,State1),
    plan(State1,Moves,Len1),
    Len is Len1+1.

final_state(jugs(4,_)).
final_state(jugs(_,4)).

move(jugs(V1,V2),fill(1)).
move(jugs(V1,V2),fill(2)).
move(jugs(V1,V2),empty(1)):-V1>0.
move(jugs(V1,V2),empty(2)):-V2>0.
move(jugs(V1,V2),transfer(2,1)):-V2>0.
move(jugs(V1,V2),transfer(1,2)):-V1>0.

update(jugs(V1,V2),empty(1),jugs(0,V2)).
update(jugs(V1,V2),empty(2),jugs(V1,0)).
update(jugs(V1,V2),fill(1),jugs(C1,V2)):-capacity(1,C1).
update(jugs(V1,V2),fill(2),jugs(V1,C2)):-capacity(2,C2).
update(jugs(V1,V2),transfer(2,1),jugs(W1,W2)):-
    capcity(1,C1),
    Liquid is V1+V2,
    Excess is Liquid-C1,
    (Excess=<0->W1=Liquid,W2=0;
     W1 is C1,W2=Excess).
update(jugs(V1,V2),transfer(1,2),jugs(W1,W2)):-
    capcity(2,C2),
    Liquid is V1+V2,
    Excess is Liquid-C2,
    (Excess=<0->W2=Liquid,W1=0;
     W2 is C2,W1=Excess).

capacity(1,8).
capcity(2,5).