The puzzle of the day prompts us to perform antinatural¹ 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 Parsec.

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]
extractMath = lines . filter (/= ' ')

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 has² a useful combinator that will directly perform the operation in a flat, left-associative manner. So we can use that directly.

expr, num :: Parser Int
expr = (paren expr <|> num) `chainl1` op <?> "expression"
num = read <$> many1 digit <?> "number"

op, plus, times :: Parser (Int -> Int -> Int)
op = plus <|> times <?> "operation"
plus  = (+) <$ char '+'
times = (*) <$ char '*'

This makes use of a rather generic helper I extracted for readability.

paren :: Parser a -> Parser a
paren rec = between (char '(') (char ')') rec <?> "parenthesized group"

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
exprV2 = (paren exprV2 <|> num) `chainl1` plus `chainl1` times <?> "advanced math"

λ> 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 ()
main = do
  math <- extractMath (/= ' ') <$> readFile "day18.in"
  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!