Discussion on: Advent of Code 2020 Solution Megathread - Day 19: Monster Messages

data Rule = RS [Int] (Maybe [Int]) | RC Char
    deriving (Eq, Show)

quotedString :: Parser Rule
quotedString = do
    TP.char '"'
    xs <- TP.many (TP.noneOf "\"" TP.<|> (TP.char '\\' >> TP.char '\"'))
    TP.char '"'
    return $ RC (head xs)

number :: Parser Int
number = do
  digits <- many1 TP.digit
  TP.spaces
  return $ read digits

ruleSeq :: Parser Rule
ruleSeq = do
    ls <- many1 (TP.spaces >> number)
    rs <- optionMaybe (TP.spaces >> TP.char '|' >> many1 (TP.spaces >> number))
    return $ RS ls rs

rule :: Parser (Int, Rule)
rule = do 
    i <- number
    TP.char ':'
    r <- TP.try (TP.spaces >> quotedString) TP.<|> ruleSeq
    return (i, r)

parse :: Parser a -> String -> a
parse p s =
    case TP.parse (TP.spaces *> p <* eof) "" s of
    Left e  -> error $ show e
    Right x -> x

build :: M.Map Int Rule -> Rule -> Parser ()
build m (RS ls rs) = choice (TP.try (aux ls) : maybe [] (\ rs -> [aux rs]) rs)
    where
        aux [n] = build m (m M.! n)
        aux (n:xs) = do
                        _ <- build m (m M.! n)
                        _ <- aux xs
                        return ()
build _ (RC c) = void (TP.char c)

main = do
    (rs,is) <- readFile "day19_input" 
                    <&> lines <&> span (/="") <&> bimap (M.fromList . map (parse rule)) tail
    let zero = rs M.! 0
        g = isRight . TP.parse (TP.spaces *> build rs zero <* eof) "" 

    print (length $ filter id $ map g is)

    -- part 2 (we need to be a little careful to not get stuck in that loop :-))
    let p42 = build rs (rs M.! 42)
        p31 = build rs (rs M.! 31)
        p = do 
              r42 <- TP.many1 $ TP.try p42
              r31 <- TP.many1 $ TP.try p31
              if length r42 > length r31 then return () else fail "no luck"
        g' = isRight . TP.parse (TP.spaces *> p <* eof) ""

    print (length $ filter id $ map g' is)