The puzzle of the day prompts us to perform antinatural1 math. This looks like the kind of puzzle that would be easier solved with two regex replacements and an
eval, but I started this year in Haskell, let’s keep at it. As usual in this series, this post is a literate Haskell program.
I’ll use parser combinator library
import Text.Parsec type Parser = Parsec String ()
I don’t want to get lost in tokenization or risk forgetting to skip spaces, so I’ll just simplify the input before processing it.
extractMath :: String -> [String] = lines . filter (/= ' ')extractMath
Now to write the parser. It’s rather straightforward. An expression is a flat chain of operations performed on subexpressions. Those subexpressions are either a literal number or another expression.
Parsec has2 a useful combinator that will directly perform the operation in a flat, left-associative manner. So we can use that directly.
num :: Parser Int expr,= (paren expr <|> num) `chainl1` op <?> "expression" expr = read <$> many1 digit <?> "number" num times :: Parser (Int -> Int -> Int) op, plus,= plus <|> times <?> "operation" op = (+) <$ char '+' plus = (*) <$ char '*'times
This makes use of a rather generic helper I extracted for readability.
paren :: Parser a -> Parser a = between (char '(') (char ')') rec <?> "parenthesized group"paren rec
And… that’s all there is to it! Parser combinators don’t have innate preference for the human way of ordering operations, and they’ll provide us with the results we want unconfused:
λ> traverse (parse (expr <* eof) "expression") $ extractMath sample Right [51,26,437,12240,13632]
Now for part 2. The operations are ordered here. Let’s adjust the parser for that.
exprV2 :: Parser Int = (paren exprV2 <|> num) `chainl1` plus `chainl1` times <?> "advanced math"exprV2
λ> traverse (parse (exprV2 <* eof) "expression") $ extractMath sample Right [51,46,1445,669060,23340]
The parser was unimpressed by the plot twist. Here’s the end of the code for completeness.
main :: IO () = do main <- extractMath (/= ' ') <$> readFile "day18.in" math print $ sum <$> traverse (parse (expr <* eof) "basic math") math print $ sum <$> traverse (parse (exprV2 <* eof) "advanced math") math
This concludes day 18. I hope you enjoyed it. See you tomorrow!