import Data.List
import qualified Data.Set as Set
import Control.Monad

import Debug.Trace

parseRepl :: [String] -> (String,String)
parseRepl [a,"=>",b] = (a,b)
-- = -- subl syntax

startsWith :: String -> String -> Bool
startsWith s prefix = take (length prefix) s == prefix

getRepls :: [(String,String)] -> String -> Set.Set String
getRepls rs s = getRepls' rs s ""

getRepls' :: [(String,String)] -> String -> String -> Set.Set String
getRepls' _ [] _ = Set.empty
getRepls' rs s prefix = foldl (\set s -> Set.insert (prefix++s) set) fromnext
                        $ map (\r -> replace s r)
                        $ filter (\r -> s `startsWith` (fst r)) rs
    where fromnext = getRepls' rs (tail s) $ prefix ++ [head s]
          replace s r = snd r ++ drop (length (fst r)) s

day19_1 :: IO ()
day19_1 = do
    input <- liftM lines $ readFile "day19.txt"
    let rs    = map (parseRepl . words) $ init (init input)
        start = last input
    print $ Set.size $ getRepls rs start

day19_2 :: IO ()
day19_2 = do
    input <- liftM lines $ readFile "day19.txt"
    let rs = map (parseRepl . words) $ init (init input)
        target = last input
        stages = iterate (Set.unions . map (getRepls rs) . Set.toList . (\s -> trace (show $ Set.size s) s)) $ Set.fromList ["e"]
    print $ (Set.unions . map (getRepls rs) . Set.toList) $ (Set.unions . map (getRepls rs) . Set.toList) $ Set.fromList ["e"]
    print $ findIndex (Set.member target) stages

main = day19_2