blob: 65d3e877d4d0d3ecdb18010a229c6f5577c5d19b (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
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
|
