/***********************************************************
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.
Adapted to B-Prolog by Neng-Fa Zhou
***********************************************************/
top:-
    solve_dfs(jugs(0,0),Moves).

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

:-table dfs(+,-,min).
dfs(State,[],0):-final_state(State).
dfs(State,[Move|Moves],Len):-
    move(State,Move),
    update(State,Move,State1),
    dfs(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).