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

open System

//cambia per trovare soluzioni in tempi diversi
let MAX_TIME = 15

type Person = 
  | Person of string * int

type Direction =
  | L
  | R

type Move =
  | Move of Direction * Person list

//estende il modulo List
module List =
  let rec combinations items =
    [
      match items with
      | [] -> ()
      | x::xs ->
        for y in xs do yield x, y
        yield! combinations xs
    ]

let rec Solve cost moves atStart atEnd dir =
  seq {
    if cost > MAX_TIME then ()
    elif Set.isEmpty atStart then yield cost, List.rev moves
    else
      match dir with
      | L ->
        for Person(_, time) as person in atEnd do
          let move = Move(dir, [person])
          yield! Solve (cost + time) (move :: moves) (Set.add person atStart) (Set.remove person atEnd) R
      | R ->
        let combinations = List.combinations (Set.toList atStart)
        for (Person(_, time1) as person1), (Person(_, time2) as person2) in combinations do  
          let move = Move(dir, [person1; person2])
          let persons = set [person1; person2]
          yield! Solve (cost + (max time1 time2)) (move :: moves) (atStart - persons) (atEnd + persons) L
  }      

let Persons =
  set [
    Person("A", 1)
    Person("B", 2)
    Person("C", 5)
    Person("D", 8)
    //Person("E", 1)
  ]

Solve 0 [] Persons Set.empty R
|> Seq.iter (printfn "%A")

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.