Solving Wolf Goat Cabbage Problem with F#
I am learning F# language. As part of this journey I decided to write the solution to the Wolf, Goat and Cabbage problem in F#.
It was a little hard to get started because I was just not able to think in terms of functional programming and F#. These two articles helped me get started
http://www.paulbutcher.com/2007/09/escape-from-zurg/
http://web.engr.oregonstate.edu/~erwig/papers/Zurg_JFP04.pdf
Had difficulty in reading these two articles as well, because they are from Ruby and Haskell but I got an overall line-of-thought on how to build the solution to such problems.
My first step was to define a list of items which need to be moved from the left river bank to the right river bank and also the constaints
1.let Items = ["Wolf"; "Goat"; "Cabbage"]
2.
3.let DeadlyCombinations = [set ["Wolf"; "Goat"]; set ["Goat"; "Cabbage"];]
Here Items is a just a List, with 3 strings. The DeadlyCombinations is also a list which contains two sets. These sets defines items/animals who cannot be left alone on any bank.
We also need a function to check if a list belongs/contains to deadly combinations or not. for this we write the following function
1.let isMoveDeadly list1 =
2. let listSet = set list1
3. List.exists (fun n -> n = listSet) DeadlyCombinations
Next I need the logic to move an Item from the left bank to the right bank. for this I wrote a method called MoveRight (means move item from left river bank to right river bank).
01.let rec MoveRight items =
02. match items with
03. | [] -> []
04. | head::tail ->
05. if (isMoveDeadly tail) then
06. MoveRight tail @ [head]
07. else
08. Console.WriteLine("Going to move " + head)
09. tail
here MoveRight is the function name. rec is to say that this function will be recursively called and it takes animals as a parameter. here you can see that F# will automatically determine the type of animals which I do the matching logic. The type which is inferred for animals is List.
First line is simple. if the passed list is empty, then return an empty list and get out. Otherwise, split the list into head and the remaining into tail.
Our intention here is to move the head only if tail is not deadly. otherwise we need to pick another item from the list
So we pick the head out of the list and see if the tail is deadly. if yes we put the head at the back of the list and then recursively call the function again so that the 2nd item is picked up as the head.
if the tail is not deadly, then we have effectively moved the head item from the left bank to the right bank.
Since one item is moved from left bank to right bank, we return the remaining list as the output.
Sometimes, we may need to move an item back from the right river bank to the left river bank because the combination on the right river bank may be a deadly one
01.let MoveLeft animals =
02. let RightList = ListDiff animals Animals
03. let ShouldTakeAnimal = isMoveDeadly RightList
04. if (ShouldTakeAnimal) then
05. let x = List.head RightList
06. Console.WriteLine("Going to move " + x + " back")
07. [x]
08. else
09. Console.WriteLine("Farmer comes back alone")
10. []
When an item is moved from left bank to right bank, the farmer has to come back to move the next item from the left bank to the right bank. but this is not so simple because if the farmer leaves the right bank and the combination there is deadly then items would get destroyed. So we need to determine if the farmer can leave from the right bank to the left bank alone... or should he take an item with him.
For this we write our MoveLeft function (move from right river bank to left bank)
Since we do not create a 2nd list for the items on the right river bank, we need to take a Diff between the master list of items on top with the current list of items on the left bank, to get a list of items on the right bank. This is done by the following function which is used in MoveLeft function above
1.let ListDiff list1 list2 = List.filter (fun n -> List.forall (fun x -> x <> n) list1) list2
The first if statement determines if the farmer can leave alone or should he move an item from the right to left bank. this is done by determining that the combination on the right river bank is deadly or not. if yes, then farmer cannot travel alone and he must take an item with him. If the combination is not deadly, then the farmer can travel alone.
With all these functions in place, we can write the master function which will solve the puzzle. The master function needs to keep moving the farmer between left and right banks by calling itself recursively till the puzzle is resolved. My master function looks like
01.let rec Solve direction animals =
02. match animals with
03. | [] -> Console.WriteLine("Solved")
04. | _ ->
05. match direction with
06. | Left -> Solve Right (MoveRight animals)
07. | Right -> Solve Left (animals @ (MoveLeft animals))
Here Solve is a recursive function and it takes two parameters one is direction and the other is the list of animals on the left bank. We start with passing the whole list of items as a parameter.
We need to create a discriminated for direction with is pretty simple
1.type Direction =
2. | Left
3. | Right
The logic of the solve function is the following.
if the list of animals on the left side is empty then the puzzle is solved. if not, then check where is the farmer if the farmer is Left, then Move the animal from the left bank to the right bank by calling MoveRight and if the farmer is on the right bank, then call the function MoveLeft. (the moveleft function will either move the farmer back to left bank alone ... or with an animal if the combination there is deadly).
We finally call our master function in a main method
1.[<entrypoint>]
2.let main args =
3. Solve Left Animals
4. 0
The output of the program is
This example was nice because it got me to think about
- pattern matching
- recursively reducing an input set using head::tail
- breaking down the constraints of the problem into small functions.
What I could not do however in this problem was to do some clojures and other functional stuff like curried functions. I hope to do those in the next problems which I solve.
If you want to improve my code for this problem then feel free to edit this page and improve the code. here is the entire code listing
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 = [set ["Wolf"; "Goat"]; set ["Goat"; "Cabbage"];]
let isMoveDeadly list1 =
let listSet = set list1
List.exists (fun n -> n = listSet) DeadlyCombinations
let rec MoveRight animals =
match animals with
| [] -> []
| head::tail ->
if (isMoveDeadly tail) 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
if (ShouldTakeAnimal) then
let x = List.head RightList
Console.WriteLine("Going to move " + x + " back")
[x]
else
Console.WriteLine("Farmer comes 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