a1fd6ccd8b34d3a4211750fa2d2f5010d6882795
[advent-of-code-20.git] / advent19 / src / advent19.hs
1 -- import Debug.Trace
2
3 import Text.ParserCombinators.ReadP
4 -- import Text.ParserCombinators.ReadP ((+++))
5 import Data.Char (isDigit, isAlpha)
6
7 import qualified Data.IntMap.Strict as M
8 import Data.IntMap.Strict ((!))
9
10 import Data.Functor (void)
11 import Data.Either
12
13
14 data Rule = Letter Char
15 | Then [Rule]
16 | Or Rule Rule
17 | See Int
18 deriving (Show, Eq)
19
20 type RuleSet = M.IntMap Rule
21
22
23 main :: IO ()
24 main =
25 do text <- readFile "data/advent19.txt"
26 -- print text
27 let (rules, messages) = parse inputP text
28 print $ part1 rules messages
29 print $ part2 rules messages
30
31 setup fname =
32 do text <- readFile fname
33 let (rules, messages) = parse inputP text
34 let newRules = parse rulesP "8: 42 | 42 8\n11: 42 31 | 42 11 31"
35 let updatedRules = M.union newRules rules
36 let myParser = makeParser updatedRules (See 0)
37 return (myParser, updatedRules, messages)
38
39
40 part1 = countMatches
41
42 part2 rules messages = countMatches updatedRules messages
43 where newRules = parse rulesP "8: 42 | 42 8\n11: 42 31 | 42 11 31"
44 updatedRules = M.union newRules rules
45
46 countMatches rules messages
47 = length $ filter ((== "") . snd) results
48 where myParser = makeParser rules (See 0)
49 results = concatMap (readP_to_S myParser) messages
50
51
52 parse :: ReadP a -> String -> a
53 parse parser str = fst $ head $ filter ((== "") . snd) $ readP_to_S parser str
54
55
56 -- Generate the rules
57
58 makeParser :: RuleSet -> Rule -> ReadP ()
59 makeParser m (Letter c) = void $ char c
60 makeParser m (Then rs) = mapM_ (makeParser m) rs
61 makeParser m (Or a b) = (makeParser m a) +++ (makeParser m b)
62 makeParser m (See i) = makeParser m (m!i)
63
64
65 -- Parse the input
66 inputP = (,) <$> rulesP <* blankLines <*> messagesP
67
68 rulesP = M.fromList <$> ruleP `sepBy` endOfLine
69 ruleP = (,) <$> decimal <* (string ": ") <*> ruleBodyP
70 ruleBodyP = choice [letterRuleP, orRuleP, thenRuleP, seeRuleP]
71
72 letterRuleP = Letter <$> between (string "\"") (string "\"") get
73 orRuleP = Or <$> thenRuleP <* (string " | ") <*> thenRuleP
74 thenRuleP = Then <$> seeRuleP `sepBy` (string " ")
75 seeRuleP = See <$> decimal
76
77 messagesP = (munch1 isAlpha) `sepBy` endOfLine
78
79 blankLines = skipMany1 endOfLine
80
81 decimal = read <$> many1 (satisfy isDigit)
82 endOfLine = char '\n'