Missionaries and Cannibals Problem
A friend told me about a university task he had once (many years ago) in functional programming.
The task was to practice functional programming on the Missionaries and Cannibals Problem. The functional programming language was told to make the solution simply by just defining the problem properly and let the functional program (probably recursively) find the solution.
Of course, I had to make an attempt in Haskell.
I must admit that had to work out the solution myself using pen and paper before I completed the haskell program to solve it programmatically. I was not sure if I had to take the people in the boat into account when defining the states.
Anyway the final solution is as follows. It just determine the minimal amount of turns to move everyone. To determine how it is done you need a different structure where previous state can be backtracked.
import Data.List (nub, findIndex)
{-
Missionaries and Cannibals crossing the river problem (from west to east shore)
http://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem
Compile: ghc -O2 MissionaryProblem.hs
Run: ./MissionaryProblem
TODO: We need a tree structure to determine the valid path from s0 to the final state
-}
type Turns = Int -- moves 0..
type Cannibals = Int -- cannibals n = 0..3 on west shore (3-n on east shore)
type Missionaries = Int -- missionaries 0..3 on west shore
type State = (Turns, Missionaries, Cannibals)
type StateOp = (Missionaries, Cannibals)
-- Initial state when 3 missionaries and cannibals reside on west shore
s0 :: State
s0 = (0, 3, 3)
-- Do state operation on state
stateOp :: State -> StateOp -> State
stateOp (ts,ms,cs) (dm,dc) = (ts+1,ms+dm,cs+dc)
-- Possible states operations when boat is on west shore
westStateOps :: [StateOp]
westStateOps = [ (-dm,-dc) | dm <- [0..2], dc <- [0..2], let n = dm+dc, n >= 1, n <= 2 ]
-- Possible states operations when boat is on east shore
eastStateOps :: [StateOp]
eastStateOps = map (\(dm,dc) -> (-dm,-dc)) westStateOps
-- Determine if boat is on west shore
boatWest :: State -> Bool
boatWest (ts,_,_) = even ts
-- Determine if we have a valid state i.e. number of missonaries are more or equal to
-- the number of cannibals on each shore
validState :: State -> Bool
validState (_,ms,cs) = not $ (ms > 0 && ms < cs)
|| (ms < 3 && ms > cs)
|| (ms < 0) || (ms > 3) -- people mustn't disappear or breed
|| (cs < 0) || (cs > 3)
-- Wanted final state
done :: State -> Bool
done (_,ms,cs) = (ms == 0) && (cs == 0)
-- Determine all validState states following a specific state
nextStates :: State -> [State]
nextStates s | (boatWest s) = nub $ filter validState $ map (stateOp s) westStateOps
| otherwise = nub $ filter validState $ map (stateOp s) eastStateOps
-- All possible states at turn t
statesAt :: Turns -> [State]
statesAt 0 = [s0]
statesAt n = nub $ concatMap nextStates $ statesAt (n-1)
-- Determine at which lowest possible turn where all has arrived safely on the east shore
main = print $ findIndex ((>0) . length) $ map (filter done . statesAt) [0..]
The output of the program is just the state index when all have passed. 11 is turn 12 because first turn is numbered 0.
$ ./MissionaryProblem
Just 11