Four people need to cross a bridge at night which only supports two people at the same time. Person A needs 1 minute to cross the bridge, B needs 2 minutes, C needs 5 minutes and D needs 10 minutes. When two people cross the bridge they move at the slowest person’s pace. They have a torch which has battery left for only 17 minutes. They can’t cross the bridge without light. How can they manage to cross the bridge?

One might guess that an obvious solution would be to let the fastest person (A) shuttle each other person over the bridge and return alone with the torch. This would give the following schedule:

A, B | -> | 2 |

A | <- | 1 |

A,C | -> | 5 |

A | <- | 1 |

A,D | -> | 10 |

The total duration of this schedule would be 19 minutes, so the torch would run out of battery while person A and D are still on the bridge.

The optimal solution consists of letting the two slowest people (C and D) cross the bridge together, giving the following schedule:

A, B | -> | 2 |

B | <- | 2 |

C,D | -> | 10 |

A | <- | 1 |

A,B | -> | 2 |

Which gives a total crossing time of exactly 17 minutes.

Writing a prolog program to solve this kind of river crossing problems is a walk in the park. Check it out if you want to know an alternative solution.

## 4 Comments

## Kevin · November 20, 2009 at 8:44 pm

Goedenavond, I’ve been correcting Prolog homework and I think I’ve actually “corrected” your solution.. hehe. If you’re interested, what I gave as feedback was just that appending and then sorting is a bit more inefficient than just inserting it into the right spot in the first place:

zet_in(P, [P2|Rest], [P2|Rest2]) :-

P @> P2,

!,

zet_in(P, Rest, Rest2).

zet_in(Person, Rest, [Person|Rest]).

(At least if you want to make this general on to longer lists, and especially if sort/2 were quicksort, but I think in SWI it’s merge sort.) You could of course avoid the problem by instead having only one list, something like:

[-1, 2, -5, 10]

and having a flip1(L,L2,Sign) predicate that traverses the list and flips one of the number that have the same sign as Sign and then stops, so that

flip1([-1, 2, -5, 10], [ 1, 2, -5, 10], -1) and

flip1([-1, 2, -5, 10], [-1, 2, 5, 10], -1) are true;

flip2 does the same thing for two numbers but calls flip1 on the tail list in its base case.

(Not all my students are so well versed in the ways of Google though. One of them actually gave me a solution where the list of people was represented as a bit set, with breadth first search on difference lists…)

## Nerisha · June 3, 2010 at 10:10 am

Hi,

Has anyone solved this in C#, VB, or Delphi?

## ali · July 1, 2012 at 1:28 pm

Hi,How to query about your code ?

it always returns “No.” (I use Strawberry Prolog IDE).

I did not understand Kevin’s Solution.

## ali · July 1, 2012 at 3:03 pm

I found solution! after installing SWI Prolog.

problem was related to IDE.