Re: The Bridge crossing prolog program

Hi!

vag wrote:

Anyone have the prolog program solving this problem? 

Here is one:


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
touristList([t1,t2,t3,t4]).

time(t1, 6).
time(t2, 7).
time(t3, 10).
time(t4, 15).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

member_rest(E, [E|Es], Es).
member_rest(M, [E|Es], [E|Rest]) :-
        member_rest(M, Es, Rest).

% move two people from left to right

solve_left(s(Lefts0, Rights0), Time0, Plan0, Plan) :-
        member_rest(T1, Lefts0, Lefts1),
        member_rest(T2, Lefts1, Lefts2),
        time(T1, TT1),
        time(T2, TT2),
        Time1 is Time0 - max(TT1, TT2),
        Time1 >= 0,
        Plan0 = [[T1,T2]|Rest],
        solve_right(s(Lefts2, [T1,T2|Rights0]), Time1, Rest, Plan).


% move one tourist from right to left if necessary

solve_right(s(Lefts0, Rights0), Time0, Plan0, Plan) :-
        ( Lefts0 == [] ->
            Plan0 = Plan
        ;
            member_rest(T, Rights0, Rights1),
            time(T, TT),
            Time1 is Time0 - TT,
            Time1 >= 0,
            Plan0 = [[T]|Rest],
            solve_left(s([T|Lefts0], Rights1), Time1, Rest, Plan)
        ).


cross(Max, Plan) :-
        touristList(Ts),
        ( Ts = [Single] ->
            time(Single, Time),
            Time =< Max,
            Plan = [[Single]]
        ;
            solve_left(s(Ts, []), Max, Plan, [])
        ).

Example:

?- cross(42, Plan).

Plan = [[t1, t2], [t1], [t3, t4], [t2], [t2, t1]]

Yes

All the best,
Markus.
.