River crossing problem

In the book From Bacteria to Bach and Back by Daniel Dennet there is this note:

Four people come to a river in the night. There is a narrow bridge, and it can only hold two people at a time. They have one torch and, because it’s night, the torch has to be used when crossing the bridge. Person A can cross the bridge in one minute, B in two minutes, C in five minutes, and D in eight minutes. When two people cross the bridge together, they must move at the slower person’s pace. The question is, can they all get across the bridge in fifteen minutes or less?

This is a well know crossing problem like wolf cabbage and goat problem. Many of this problem are solved by simple Prolog program. But now i want solve this problem with a functional language: F#. A simple solution is (based on this):

 

Executing the program yield the following output (can be executed as is in LINQPad):

(15,
 [Move (R,[Person (“A”,1); Person (“B”,2)]); Move (L,[Person (“A”,1)]);
  Move (R,[Person (“C”,5); Person (“D”,8)]); Move (L,[Person (“B”,2)]);
  Move (R,[Person (“A”,1); Person (“B”,2)])])
(15,
 [Move (R,[Person (“A”,1); Person (“B”,2)]); Move (L,[Person (“B”,2)]);
  Move (R,[Person (“C”,5); Person (“D”,8)]); Move (L,[Person (“A”,1)]);
  Move (R,[Person (“A”,1); Person (“B”,2)])])

So the puzzle have two equivalent solution.

Playing with set of Persons and MAX_TIME constant, is possible to explore solution for different problem.

Lascia un commento

Connect with Facebook