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?

If this is homework you should show us what you've done and what is the problem with your solution. — gusbro, Apr 12 '12 at 20:52
well, i'm having trouble starting the predicate. It must have these parameters. 1. The name of the family (as given in a family fact) -- must be bound 2. A list of moves that would take the family across the river -- must be unbound 3. The time the sequence of moves would take -- must be unbound — user1204349, Apr 12 '12 at 20:57
Your solution seems to have problems with the if-then-else construct. Parenthesize to fix it — gusbro, Apr 12 '12 at 21:44

gusbro · Answer 1 · 2012-04-12T21:56:39.583

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

thanks alot for that solution. I need the problem to work with any family, not just this particular family. To define a family, i need to give a "family" fact, where the first parameter is a name for the family and the second is a list of the family members. Each family member is in the form Name/Time. For example, we would define the family in the original example with this fact: `family(original, [father/1, mother/2, child/5, granny/10]).` I'll try to figure something out, but this is generally where all my problems with the little assignment have been. — user1204349, Apr 12 '12 at 23:11
It should be easy. For example in my solution you would need to receive another parameter Family and replace the first findall with `family(Family, Left)` and use `/` instead of `-` as the pairing term for Person-Time. Also note that you would have to rename bridge/3 with another name. — gusbro, Apr 13 '12 at 14:38

prolog bridge puzzle with unlimited people

1 Answers1