My Weblog

Blog about programming and math

Missionaries and cannibals problem

In the missionaries and cannibals problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries.) The boat cannot cross the river by itself with no people on board. We can solve this problem using depth first search. Representing the states as number of missionaries, cannibals and boat location in following way.


data Side = Side { missionaries :: Int , cannibals :: Int } deriving ( Show , Eq  )
data Loc = L | R deriving ( Show , Eq  )
data State = State { left :: Side , right :: Side , bloc :: Loc } deriving ( Show , Eq  )

Target is to move every missionaries and cannibals from left to right so our initial state is initialState and final state is finalState.


initialState = State { left =  Side 3 3  , right =  Side 0 0  , bloc = L }
finalState = State  { left =  Side 0 0  , right = Side 3 3  , bloc = R }

Possible movements
1. move ( 2 , 0 )
2. move ( 1 , 0 )
3. move ( 1 , 1 )
4. move ( 0 , 1 )
5. move ( 0 , 2 )
where move ( M , C ) is movement of M missionaries and C cannibals from one side to other side depending on boat location. If boat location is left then move ( M , C ) is moving M missionaries and C cannibals from left to right and vice versa. Using depth first search, we can explore every possible movement

path :: [ State ] -> [ State ] -> [ State ]
path []   vis = reverse vis
path  ( x : xs )  vis 
     | x  == finalState  = reverse ( x : vis )
     | elem x vis = path xs vis 
     | otherwise = path xs'  vis'  where 
              vis'  = x : vis
              xs' =   ( filter  isLegal  ( move x ) ) ++ xs

Encoding the moves and testing the legality

             
move :: State -> [ State ]
move ( State ( Side ml cl ) ( Side mr cr ) L ) = 
        [ State ( Side ( ml - 2 ) cl ) ( Side ( mr + 2 ) cr ) R 
        , State ( Side ( ml - 1 ) cl ) ( Side ( mr + 1 ) cr ) R
        , State ( Side ( ml - 1 ) ( cl - 1 ) ) ( Side ( mr + 1 ) ( cr + 1 ) ) R 
        , State ( Side ml ( cl - 2 ) ) ( Side mr ( cr + 2 ) ) R
        , State ( Side ml ( cl - 1 ) ) ( Side mr ( cr + 1 ) ) R        
        ] 
move  ( State ( Side ml cl ) ( Side mr cr ) R ) = 
        [ State ( Side ( ml + 2 ) cl ) ( Side ( mr - 2 ) cr ) L 
        , State ( Side ( ml + 1 ) cl ) ( Side ( mr - 1 ) cr ) L
        , State ( Side ( ml + 1 ) ( cl + 1 ) ) ( Side ( mr - 1 ) ( cr - 1 ) ) L 
        , State ( Side ml ( cl + 2 ) ) ( Side mr ( cr - 2 ) ) L
        , State ( Side ml ( cl + 1 ) ) ( Side mr ( cr - 1 ) ) L        
        ]           

isLegal :: State -> Bool 
isLegal ( State ( Side ml cl ) ( Side mr cr ) y ) 
        | ml == 0 = mr >= cr  && cr >= 0 
        | mr == 0 = ml >= cl  && cl >= 0
        | otherwise = ml >= cl && mr >= cr && cl >= 0 && cr >= 0  
                        

Complete source code ( In case if you are lazy 🙂 )

import Data.List


data Side = Side { missionaries :: Int , cannibals :: Int } deriving ( Show , Eq  )
data Loc = L | R deriving ( Show , Eq  )
data State = State { left :: Side , right :: Side , bloc :: Loc } deriving ( Show , Eq  )

initialState = State { left =  Side 3 3  , right =  Side 0 0  , bloc = L }
finalState = State  { left =  Side 0 0  , right = Side 3 3  , bloc = R }


path :: [ State ] -> [ State ] -> [ State ]
path []   vis = reverse vis
path  ( x : xs )  vis 
     | x  == finalState  = reverse ( x : vis )
     | elem x vis = path xs vis 
     | otherwise = path xs'  vis'  where 
              vis'  = x : vis
              xs' =   ( filter  isLegal  ( move x ) ) ++ xs
             
move :: State -> [ State ]
move ( State ( Side ml cl ) ( Side mr cr ) L ) = 
        [ State ( Side ( ml - 2 ) cl ) ( Side ( mr + 2 ) cr ) R 
        , State ( Side ( ml - 1 ) cl ) ( Side ( mr + 1 ) cr ) R
        , State ( Side ( ml - 1 ) ( cl - 1 ) ) ( Side ( mr + 1 ) ( cr + 1 ) ) R 
        , State ( Side ml ( cl - 2 ) ) ( Side mr ( cr + 2 ) ) R
        , State ( Side ml ( cl - 1 ) ) ( Side mr ( cr + 1 ) ) R        
        ] 
move  ( State ( Side ml cl ) ( Side mr cr ) R ) = 
        [ State ( Side ( ml + 2 ) cl ) ( Side ( mr - 2 ) cr ) L 
        , State ( Side ( ml + 1 ) cl ) ( Side ( mr - 1 ) cr ) L
        , State ( Side ( ml + 1 ) ( cl + 1 ) ) ( Side ( mr - 1 ) ( cr - 1 ) ) L 
        , State ( Side ml ( cl + 2 ) ) ( Side mr ( cr - 2 ) ) L
        , State ( Side ml ( cl + 1 ) ) ( Side mr ( cr - 1 ) ) L        
        ]           

isLegal :: State -> Bool 
isLegal ( State ( Side ml cl ) ( Side mr cr ) y ) 
        | ml == 0 = mr >= cr  && cr >= 0 
        | mr == 0 = ml >= cl  && cl >= 0
        | otherwise = ml >= cl && mr >= cr && cl >= 0 && cr >= 0  
                        
                         


Main> path [ initialState ] []
[State {left = Side {missionaries = 3, cannibals = 3}, right = Side {missionaries = 0, cannibals = 0}, bloc = L},State {left = Side {missionaries = 2, cannibals = 2}, right = Side {missionaries = 1, cannibals = 1}, bloc = R},State {left = Side {missionaries = 3, cannibals = 2}, right = Side {missionaries = 0, cannibals = 1}, bloc = L},State {left = Side {missionaries = 3, cannibals = 0}, right = Side {missionaries = 0, cannibals = 3}, bloc = R},State {left = Side {missionaries = 3, cannibals = 1}, right = Side {missionaries = 0, cannibals = 2}, bloc = L},State {left = Side {missionaries = 1, cannibals = 1}, right = Side {missionaries = 2, cannibals = 2}, bloc = R},State {left = Side {missionaries = 2, cannibals = 2}, right = Side {missionaries = 1, cannibals = 1}, bloc = L},State {left = Side {missionaries = 0, cannibals = 2}, right = Side {missionaries = 3, cannibals = 1}, bloc = R},State {left = Side {missionaries = 0, cannibals = 3}, right = Side {missionaries = 3, cannibals = 0}, bloc = L},State {left = Side {missionaries = 0, cannibals = 1}, right = Side {missionaries = 3, cannibals = 2}, bloc = R},State {left = Side {missionaries = 1, cannibals = 1}, right = Side {missionaries = 2, cannibals = 2}, bloc = L},State {left = Side {missionaries = 0, cannibals = 0}, right = Side {missionaries = 3, cannibals = 3}, bloc = R}]
*Main> map bloc . path [ initialState ] $ []
[L,R,L,R,L,R,L,R,L,R,L,R]

If you have any suggestion or comment then please let me know.

Advertisements

April 19, 2013 - Posted by | Haskell, Programming | , ,

No comments 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: