-- Missionaries and cannibals with the Constrained Constructor pattern
-- Sergio Antoy
-- Fri Jan 17 13:32:43 PST 2003

-- Three missionaries and three cannibals want to cross a river
-- with a boat that can hold up to two people.
-- Furthermore, the missionaries, if any, on either bank of the river
-- cannot be outnumbered by the cannibals
-- (otherwise, as the intuition hints, they would be eaten by the cannibals).

-- state of the puzzle:
-- it consists of the number of missionaries and cannibals 
-- and the presence of the boat on the initial bank of the river

data State = State Int Int Bool

-- Constrained Constructor on State
-- the number of missionaries and cannibals must be valid, i.e.
-- between 0 and 3 inclusive
-- the number of missionaries and cannibals must be safe, i.e.
-- on each bank he missionaries, if any, on either bank of the river
-- cannot be outnumbered by the cannibals

makeState m c l | valid && safe = State m c l
   where valid = 0 <= m && m <= 3 && 0 <= c && c <= 3
         safe  = m == 3 || m == 0 || m == c

-- start and end states of the puzzle

start = makeState 3 3 True
end   = makeState 0 0 False

-- make a move: either 1 or 2 people and the boat move to the other bank

move (State m c True)  = makeState (m-1) c False
move (State m c True)  = makeState (m-2) c False
move (State m c True)  = makeState m (c-1) False
move (State m c True)  = makeState m (c-2) False
move (State m c True)  = makeState (m-1) (c-1) False
move (State m c False) = makeState (m+1) c True
move (State m c False) = makeState (m+2) c True
move (State m c False) = makeState m (c+1) True
move (State m c False) = makeState m (c+2) True
move (State m c False) = makeState (m+1) (c+1) True

-- path of the puzzle
-- a path is a sequence of state of the puzzle

type Path = [State]

-- Constrained Constructor on Path
-- In any path, any state except the initial one must be
-- obtained from the preceeding state by means of a move
-- and cycles are not allowed.

makePath s p | valid && noCycle = s:p
   where valid   = s == move (head p)
         noCycle = all (s /=) p

-- extend the path argument to the end state
-- see the Incremental Solution pattern

extend (s:p) = if (s == end) then s:p
               else extend (makePath (move s) (s:p))

-- solve the puzzle

main = extend [start]