Solving the Haskell Missionary and Cannibal Problem
Studying the Haskell language, I once again faced the problem of finding some task to develop new skills. After some deliberation, it was decided to implement the breadth-first search algorithm written long ago in python for the problem of ferrying missionaries and cannibals. The decision seemed rather concise to me, so I decided to share it with people (and at the same time listen to criticism).
For those interested, please proceed to Cat.
Three missionaries and three cannibals must be transported from one bank of the river to the other. In the boat on which they will be moving, only two people can fit at a time, while if during the movements the number of cannibals on one shore exceeds the number of missionaries, the missionaries will be eaten (which, of course, must be avoided). It is necessary to find a sequence of safe (not leading missionaries to the sad fate of James Cook) traffic.
The theater begins with a hanger, and the Haskell program begins with the import of the modules necessary for the work. Let's start with them.
To store information about the location of missionaries, cannibals and the shore on which the boat is located, we define our data type.
An attentive reader may ask, “But why does State have only two integer fields? Missionaries can be both on the left bank, and on the right; the same applies to cannibals. It turns out four numerical fields. ”A
true remark, but for certain reasons, information on the number of people ashore without a boat is redundant (for some, it will be said below).
In order for our boat to swim from one coast to another, it is necessary to set all possible movements. There are only five of them:
Do you notice? We do not need to store information about how many missionaries we have on the opposite bank — we can always get their number by subtracting the number of missionaries on the current bank from three. The same applies to cannibals.
oppositeBank - the simplest function that changes the coast label to the opposite.
Having created a new state, we must check whether it is possible (simply put, didn’t we come to a situation where there were four missionaries on the shore with a boat, or, even more fun,one and a half lumberjacks minus one cannibal).
You must also check if the condition is safe. There are three possible options. The first is the number of cannibals equal to the number of missionaries. The second - there are three missionaries on the current shore (in this case, there are no missionaries on the opposite shore and the situation is safe). The third is the opposite of the second — all missionaries gathered on the opposite bank.
So let's write it down.
Now we turn to the most important thing - the breadth-first search. You can find out what it is by clicking on the link , but I will focus on the description of the implementation.
bfsSolution is a recursive procedure. First of all, we take from the list of already constructed paths the path located in the head. We are trying to continue it, building all possible (and safe) continuations. If one of the constructed continuations is the final state, the procedure finishes its work and returns the continued path. Otherwise, we add all the generated paths to the tail of the list and call the procedure again.
The condition is very important.
It does not allow you to return to one of the states passed by the algorithm in the process of constructing this path. For example, if in step n we sent two missionaries from the left bank to the right, then in step (n + 1) there is no point in returning them back to the left bank - we will waste time and we will not go forward a single step (the given program finds on my netbook, the solution is in 0.85 seconds; removing the above condition, I get a pretty big increase in the calculations - it takes 45 seconds to find the answer).
The final touch is the main function.
This article in no way claims to be a comprehensive review and an exhaustive explanation of all possible solutions to this problem. Interested readers can implement a deep search algorithm with returns; There is also another (not yet implemented) idea of “bringing to mind” the above solution - to try to move away from storing all generated solutions in the list of lists and implement an n-ary tree.
For those interested, please proceed to Cat.
Task statement
Three missionaries and three cannibals must be transported from one bank of the river to the other. In the boat on which they will be moving, only two people can fit at a time, while if during the movements the number of cannibals on one shore exceeds the number of missionaries, the missionaries will be eaten (which, of course, must be avoided). It is necessary to find a sequence of safe (not leading missionaries to the sad fate of James Cook) traffic.
Decision
The theater begins with a hanger, and the Haskell program begins with the import of the modules necessary for the work. Let's start with them.
import Data.List To store information about the location of missionaries, cannibals and the shore on which the boat is located, we define our data type.
dataState = State { missioners :: Int, cannibals :: Int, bank :: Char} deriving (Eq, Show)An attentive reader may ask, “But why does State have only two integer fields? Missionaries can be both on the left bank, and on the right; the same applies to cannibals. It turns out four numerical fields. ”A
true remark, but for certain reasons, information on the number of people ashore without a boat is redundant (for some, it will be said below).
In order for our boat to swim from one coast to another, it is necessary to set all possible movements. There are only five of them:
move01 (State msn cnb bk) = State (3 - msn + 2) (3 - cnb) (oppositeBank bk)
move02 (State msn cnb bk) = State (3 - msn) (3 - cnb + 2) (oppositeBank bk)
move03 (State msn cnb bk) = State (3 - msn + 1) (3 - cnb + 1) (oppositeBank bk)
move04 (State msn cnb bk) = State (3 - msn + 1) (3 - cnb) (oppositeBank bk)
move05 (State msn cnb bk) = State (3 - msn) (3 - cnb + 1) (oppositeBank bk)
Do you notice? We do not need to store information about how many missionaries we have on the opposite bank — we can always get their number by subtracting the number of missionaries on the current bank from three. The same applies to cannibals.
oppositeBank - the simplest function that changes the coast label to the opposite.
oppositeBank :: Char -> Char
oppositeBank bank
| bank == 'L' = 'R'
| otherwise = 'L'Having created a new state, we must check whether it is possible (simply put, didn’t we come to a situation where there were four missionaries on the shore with a boat, or, even more fun,
isStatePossible :: State -> Bool
isStatePossible (State msn cnb bk) = msn >= 0 && msn <= 3 && cnb >= 0 && cnb <= 3You must also check if the condition is safe. There are three possible options. The first is the number of cannibals equal to the number of missionaries. The second - there are three missionaries on the current shore (in this case, there are no missionaries on the opposite shore and the situation is safe). The third is the opposite of the second — all missionaries gathered on the opposite bank.
So let's write it down.
isStateSafe :: State -> Bool
isStateSafe(State msn cnb bk) = (cnb == msn) || (msn == 3) || (msn == 0)Now we turn to the most important thing - the breadth-first search. You can find out what it is by clicking on the link , but I will focus on the description of the implementation.
bfsSolution :: [[State]] -> [State]
bfsSolution (path:tail')
| State 3 3 'R' `elem` extensions = State 3 3 'R' : path
| otherwise = bfsSolution $ tail' ++ [ext : path | ext <- extensions, (not . elem ext) path]
where
headState = head path
extensions = filter (\x -> isStatePossible x && isStateSafe x) [move01 headState, move02 headState, move03 headState, move04 headState, move05 headState]
bfsSolution is a recursive procedure. First of all, we take from the list of already constructed paths the path located in the head. We are trying to continue it, building all possible (and safe) continuations. If one of the constructed continuations is the final state, the procedure finishes its work and returns the continued path. Otherwise, we add all the generated paths to the tail of the list and call the procedure again.
The condition is very important.
(not . elem ext) pathIt does not allow you to return to one of the states passed by the algorithm in the process of constructing this path. For example, if in step n we sent two missionaries from the left bank to the right, then in step (n + 1) there is no point in returning them back to the left bank - we will waste time and we will not go forward a single step (the given program finds on my netbook, the solution is in 0.85 seconds; removing the above condition, I get a pretty big increase in the calculations - it takes 45 seconds to find the answer).
The final touch is the main function.
main = do
mapM_ (putStrLn . show) $ (reverse . bfsSolution) ([[State 3 3 'L']])Conclusion
This article in no way claims to be a comprehensive review and an exhaustive explanation of all possible solutions to this problem. Interested readers can implement a deep search algorithm with returns; There is also another (not yet implemented) idea of “bringing to mind” the above solution - to try to move away from storing all generated solutions in the list of lists and implement an n-ary tree.