%   Solution for "Escape from Zurg"
%   Written by Markus Triska (triska@gmx.at), Sept. 4th 2007

toy_time(buzz,   5).
toy_time(woody, 10).
toy_time(rex,   20).
toy_time(hamm,  25).

%   The current state is represented as a term of the form st(T,Left,Right),
%   where: T is an integer storing the time taken so far, Left is a list of
%   toys standing on the left, Right is a list of toys standing on the right.

order(Os) :- findall(Toy, toy_time(Toy,_), Ts), solve(st(0,Ts,[]), Os, []).

solve(st(T0,Left0,Right0)) -->
        { select(Toy1, Left0, Left1), select(Toy2, Left1, Left2),
          Toy1 @< Toy2,
          toy_time(Toy1, Time1), toy_time(Toy2, Time2),
          T1 is T0 + max(Time1,Time2), T1 =< 60 },
        [r(Toy1,Toy2)],
        solve_(st(T1,Left2,[Toy1,Toy2|Right0])).

solve_(st(_,[],_))          --> !, [].
solve_(st(T0,Left0,Right0)) -->
        { select(Toy, Right0, Right1),
          toy_time(Toy, Time),
          T1 is T0 + Time, T1 =< 60 },
        [l(Toy)],
        solve(st(T1,[Toy|Left0],Right1)).

%?- order(Os).
%@ Os = [r(buzz, woody), l(buzz), r(hamm, rex), l(woody), r(buzz, woody)] ;
%@ Os = [r(buzz, woody), l(woody), r(hamm, rex), l(buzz), r(buzz, woody)] ;
%@ No