-- Missionaries and cannibals with the Constrained Constructor pattern
-- Sergio Antoy
-- Wed Jun 13 10:48:15 PDT 2001

-- 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

--import inc_search

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 = State 3 3 True
end   = State 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

data Path = Initial State | Extend Path State

lastState (Initial  x) = x
lastState (Extend _ x) = x

-- 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 p s | valid p &> noCycle p = Extend p s
   where valid   (Initial t)  = s =:= move t
         valid   (Extend _ t) = s =:= move t
         noCycle (Initial t)  = if (s == t) then failed else success
         noCycle (Extend x t) = if (s == t) then failed else noCycle x

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

extendPath p = makePath p (move (lastState p))

-- is the path complete?

isEndState p = (lastState p == end)

-- solve the puzzle

-- non-deterministic search:
main1 = searchNonDet     extendPath (Initial start) isEndState

-- depth-first search:
main2 = searchDepthFirst extendPath (Initial start) isEndState