$\newcommand{\defeq}{\mathrel{\mathop:}=}$

## 2008/12/28

### 農夫過河

> import Data.List  -- using (unfoldr)


> data Tree a = Node a [Tree a]  deriving Show


> unfoldt :: (b -> (a, [b])) -> b -> Tree a
> unfoldt f b = let (a, bs) = f b in Node a (map (unfoldt f) bs)


> bfs :: Tree a -> [a]


> bfs :: Tree a -> [a]
> bfs = unfoldr f . (:[])
>   where
>     f [] = Nothing
>     f (Node a ts : xs) = Just (a, xs ++ ts)


> type State = (Bool, Bool, Bool, Bool)


• root 是 (False, False, False, False)
• 當某個 state s 可經過一步抵達 state t 時，就讓 t 成為 s 的 child，而且
• 出現在樹中的 state 都沒有慘劇發生，即不會有哪個生物被吞進別人的肚子裡。

> type Trace = String


> stateSpace :: Tree (State, Trace)
> stateSpace = unfoldt f ((False, False, False, False), "")
>   where


>     feasible :: State -> Bool
>     feasible (a, w, g, c) = not (w == g && a /= w || g == c && a /= g)


>     ccons :: Bool -> a -> [a] -> [a]
>     ccons b x = if b then (x:) else id

ccons 是 "conditional cons" 的縮寫：ccons b x xsbTrue 時是 x : xs，否則是 xs。如果舊的 state 是 (a, w, g, c)，一步可抵達的 states 就是
ccons (a == w) (not a, not w,     g,     c) $ccons (a == g) (not a, w, not g, c)$
ccons (a == c) (not a,     w,     g, not c) [ (not a, w, g, c) ]


>     f s @ ((a, w, g, c), tr) = (s, filter (feasible . fst)
>       $ccons (a == w) ((not a, not w, g, c), 'W' : tr) -- Wolf >$ ccons (a == g) ((not a,     w, not g,     c), 'G' : tr)  -- Goat
>       $ccons (a == c) ((not a, w, g, not c), 'C' : tr) -- Cabbage >$ (:[])          ((not a,     w,     g,     c), 'A' : tr)) -- Alone


> solutions :: [Trace]
> solutions = [ reverse tr | ((True, True, True, True), tr) <- bfs stateSpace ]


*Main> head solutions
"GAWGCAG"


--

Labels: