-
Notifications
You must be signed in to change notification settings - Fork 0
/
19.hs
58 lines (48 loc) · 1.71 KB
/
19.hs
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import Data.IntMap (IntMap, (!), insert, fromList)
import Data.Function ((&))
import Data.List (foldl', isPrefixOf)
import Runner (runner)
{-|
Solver for Day 19 of the Advent of Code 2020
Problem description: https://adventofcode.com/2020/day/19
-}
data Rule = Terminal Char | Compound [[Int]]
main :: IO ()
main = runner solve1 solve2
solve1 :: String -> Int
solve1 input =
let (rules, messages) = parseInput input
in length $ filter (matches 0 rules) messages
solve2 :: String -> Int
solve2 input =
let
(rules, messages) = parseInput input
rules' = rules
& insert 8 (Compound [[42], [42, 8]])
& insert 11 (Compound [[42, 31], [42, 11, 31]])
in length $ filter (matches 0 rules') messages
matches :: Int -> IntMap Rule -> String -> Bool
matches ruleNumber rules = any null . dropMatches ruleNumber
where
dropMatches ruleNumber s = case rules ! ruleNumber of
Terminal c -> if [c] `isPrefixOf` s then [tail s] else []
Compound os -> concatMap (foldl' (flip (concatMap . dropMatches)) [s]) os
parseInput :: String -> (IntMap Rule, [String])
parseInput input =
let [rules, messages] = splitOn [""] $ lines input
in (fromList $ parseRule <$> rules, messages)
parseRule :: String -> (Int, Rule)
parseRule s =
let
[n, ruleBody] = splitOn ": " s
ruleValue = if head ruleBody == '"'
then Terminal $ ruleBody !! 1
else Compound $ map read . words <$> splitOn " | " ruleBody
in (read n, ruleValue)
splitOn :: Eq a => [a] -> [a] -> [[a]]
splitOn s t = splitOn' (t, [])
where
splitOn' (t@(~(x:xs)), bs)
| null t = [reverse bs]
| s `isPrefixOf` t = reverse bs : splitOn' (drop (length s) t, [])
| otherwise = splitOn' (xs, x:bs)