module Language.PCPL.Solver
( PCP
, Node(..)
, Configuration(..)
, search
, updateConf
) where
import Data.Maybe
import Language.PCPL.Syntax
type PCP = [(Int, Domino)]
data Node = Node [Int] Configuration
data Configuration
= Top [Symbol]
| Bottom [Symbol]
deriving (Eq, Show)
search :: PCP -> [Node] -> [Int]
search pcp level = case filter isSolution level of
[] -> search pcp cs
(Node is _:_) -> is
where
cs = concatMap (children pcp) level
isSolution :: Node -> Bool
isSolution (Node _ (Top [])) = True
isSolution (Node _ (Bottom [])) = True
isSolution _ = False
children :: PCP -> Node -> [Node]
children pcp n = mapMaybe (nextNode n) pcp
nextNode :: Node -> (Int, Domino) -> Maybe Node
nextNode (Node is c) (i, d) = case updateConf c d of
Nothing -> Nothing
Just c' -> Just $ Node (i : is) c'
updateConf :: Configuration -> Domino -> Maybe Configuration
updateConf (Top ts) (Domino xs ys) = reconfigure (Top $ ts ++ xs) (Bottom ys)
updateConf (Bottom bs) (Domino xs ys) = reconfigure (Top xs) (Bottom $ bs ++ ys)
reconfigure :: Configuration -> Configuration -> Maybe Configuration
reconfigure (Top []) b = Just b
reconfigure t (Bottom []) = Just t
reconfigure (Top (x:xs)) (Bottom (y:ys))
| x == y = reconfigure (Top xs) (Bottom ys)
| otherwise = Nothing
reconfigure (Bottom b) (Top t) = reconfigure (Top t) (Bottom b)