Home > Uncategorized > The Wolf, the Goat and the Cabbage

The Wolf, the Goat and the Cabbage

This is the story of the Wolf, the Goat and the Cabbage:

Sailor Cat needs to bring a wolf, a goat, and a cabbage across the river.
The boat is tiny and can only carry one passenger at a time.
If he leaves the wolf and the goat alone together, the wolf will eat the goat.
If he leaves the goat and the cabbage alone together, the goat will eat the cabbage.
How can he bring all three safely across the river?

Try it out here. It is not that hard to find the solution with a bit of trial and error. Writing a program that searches for the solutions is a fun excerise. This is my result in haskell.

import Control.Monad
import Data.List

data Item = Goat | Wolf | Salad | Empty deriving (Show, Eq)

solve = mover [Goat,Wolf,Salad] [] []
    where
        mover [] _ _ = return []
        mover left right boat = do 
                        -- unload boat
                        let left' = left ++ boat
                        -- select what to move
                        x <- left  
                        -- load boat
                        let boat' = [x]
                        let left'' = left' \\ boat'
                        -- verify that we can leave
                        guard $ compatible left''
                        -- handle next step
                        map (x:) (movel left'' right boat')

        movel [] _ _ = return []
        movel left right boat = do 
                        -- unload boat
                        let right' = right ++ boat
                        -- select what to move
                        if compatible right' then
                            -- no problem leaving all on the right side. lets just go back empty
                            map (Empty:) (mover left right' [])
                        else do
                            -- we have a problem. pick one to move back to the left
                            y <- right  
                            -- load boat
                            let boat' = [y]
                            let right'' = right' \\ boat'
                            -- verify that we can leave
                            guard $ compatible right''
                            -- handle next step
                            map (y:) (mover left right'' boat')

        compatible [Goat,Wolf] = False
        compatible [Wolf,Goat] = False
        compatible [Salad,Goat] = False
        compatible [Goat,Salad] = False
        compatible _ = True
Advertisements
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: