F# Wolf Goat Cabbage

Question

So first of all I am sorry for asking this question. But the "Escape from Zurg" article helped me a lot and I could write my own solution to the Wolf Goat Cabbage Problem. I am positing my code below. I want you to tell me

If my code is written in true spirit of F# and functional programming

It is an optimal and good solution to the problem

open System

(* 
  The type direction determines which direction the human is present.
  Left means that Human is present on the left side of the bank.
  Right means human is present on the right side of the bank.
*)
type Direction =
  | Left
  | Right

(*
  Master list of animals
*)
let Animals = ["Wolf"; "Goat"; "Cabbage"]

let DeadlyCombinations = [["Wolf"; "Goat"];["Goat"; "Cabbage"];]

let isMoveDeadly list1 list2 =
  List.exists (fun n -> n = list1) list2

let rec MoveRight animals =
  match animals with
    | [] -> []
    | head::tail -> 
      if (isMoveDeadly tail DeadlyCombinations) then
        MoveRight tail @ [head]
      else
        Console.WriteLine("Going to move " + head)
        tail

let ListDiff list1 list2 = List.filter (fun n -> List.forall (fun x -> x <> n) list1) list2

let MoveLeft animals = 
  let RightList = ListDiff animals Animals 
  let ShouldTakeAnimal = isMoveDeadly RightList DeadlyCombinations
  if (ShouldTakeAnimal) then
    let x = List.head RightList
    Console.WriteLine("Going to move " + x + " back")
    [x]
  else
    Console.WriteLine("Farmer goes back alone")
    []

let rec Solve direction animals =
    match animals with 
    | [] -> Console.WriteLine("Solved")
    | _ ->
        match direction with
        | Left -> Solve Right (MoveRight animals) 
        | Right -> Solve Left (animals @ (MoveLeft animals))

[<EntryPoint>]
let main args =
    Solve Left Animals
    0

Looks pretty functional to me. Probably the same style as I would have written in Scheme. — leppie, Jul 15 '12 at 08:47
@Dr_Asik : Prefer `stdout.WriteLine` to `printfn` in F# when one has no format specifiers. ;-] — ildjarn, Jul 16 '12 at 07:34

score 6 · Accepted Answer · answered Jul 15 '12 at 11:24

The code looks pretty functional. There are a few changes I'd make. Firstly, I'd use sets to represent moves and there are also a few minor suggestions...

Representation. You're representing deadly combinations using a list, so ["Goat"; "Wolf"] is not the same thing as ["Wolf"; "Goat"] and if your algorithm generates move in the other order, it will not detect it as deadly move. You should try to find representations where this cannot happen, so I would change the representation to use sets:

let DeadlyCombinations = [set ["Wolf"; "Goat"]; set ["Goat"; "Cabbage"];]

In the isMoveDeadly function, you can then convert the move to a set using (but maybe it would be better to change the code to use sets everywhere):

let move = set list1

Unnecessary generalization. Aside, the function isMoveDeadly always takes DeadlyMoves as the second argument, so I would not pass it as an argument (that is unneeded generalization) and I'd write:

let isMoveDeadly list = 
  let move = set list
  DeadlyCombinations |> List.exists (fun n -> n = move)

Efficiency tip. In the MoveRight function, you're using list @ [element] pattern which is very inefficient. It means you need to copy the entire list to append the element to the end. It is more efficient to add elements to the front using element::list (less copying) and then reverse the list. I suppose you do not even need to reverse the list if you represent deadly moves as a set, so I'd write:

let rec MoveRight animals = 
  match animals with 
    | [] -> [] 
    | head::tail ->  
      if (isMoveDeadly tail) then 
        head :: (MoveRight tail)
      else 
        Console.WriteLine("Going to move " + head) 
        tail

Representation (again). You implemented your own ListDiff function to find out what animals are not in a given list. This suggests that using sets (instead of lists) would really be a better representation. If you switch to sets, you could use a built-in function Set.difference instead.

F# Wolf Goat Cabbage

1 Answers1