prolog bridge puzzle with unlimited people

Question

I'm trying to do the popular problem that goes like this.

A family of 4 is trying to cross a bridge at night. One needs a flashlight to cross the bridge, and only two persons can cross the bridge at the same time, moving at the speed of the slower of the two. Father crosses the bridge in 1 minute, Mother in 2 minutes, Child in 5 minutes and Granny in 10. What is the fastest way for them to cross the bridge?

Except I have to find all of the possible ways in which a family could cross the bridge, and the time that each way would take. The family could have any number of people in it though.

I have this code, but I can't figure out why is wont work.

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

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).

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).


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).

I tried this:

    ruleMaker(Name) :-
    family(Name,[Title/Speed|_]),
    person(Title,Speed).

moveFamily(Name,Journey, TotalTime):-
  ruleMaker(Name),
  findall(Person-Time, person(Person, Time), Left),
  moveFamily(Left, [], Journey),
  findall(Time, member([Time|_], Journey), LTime),
  sumlist(LTime, TotalTime).

Could someone tell me why this isnt working?

Answer 1

I am not giving a solution here so you can work it for yourself, but here goes some suggestions:

You just have to hold two lists, one for the people in the left side and another for the ones in the right side. Initially all the people are in the left side (list).

Then you basically have two cases:

• one in which you move the last two people from the left to the right
• another in which you select two people from the left list and "move" them to the right list, then select one person from the resulting right list and "move" it to the left side. At this point you can do a recursion to solve the problem.
• Once you have the journey you just count the total time taken and you are done.

[Edit: Here goes my solution using builtins as you have a almost working version]

person(father, 1).
person(mother, 2).
person(child, 5).
person(granny, 1).

bridge(Journey, TotalTime):-
  findall(Person-Time, person(Person, Time), Left),
  bridge(Left, [], Journey),
  findall(Time, member([Time|_], Journey), LTime),
  sumlist(LTime, TotalTime).

bridge([P1-T1, P2-T2], _, [[T, [P1-P2]]]):-
  T is max(T1, T2).
bridge(Left, Right, [[LT, [P1-P2]],[RT, [P3]]|Journey]):-
  select(P1-T1, Left, MLeft1),
  select(P2-T2, MLeft1, MLeft2),
  LT is max(T1, T2),
  select(P3-RT, [P1-T1,P2-T2|Right], MRight),
  bridge([P3-RT|MLeft2], MRight, Journey).