Discussion on: Advent of Code 2020 Solution Megathread - Day 18: Operation Order

View post

Well today was done in less that 10 minutes, which I have to say was nice as I had a lot on today :-) Parsed expressions into AST, as I have multiple Haskell parsers for DSP programming languages that I've developed over the last few years and so it was a simple cut paste, rename, and factorize for part one and two to work with the same parser.

data Expr = Num Integer | Op Op Expr Expr
  deriving Show

data Op = Add | Mul
  deriving Show

eval :: ([Parser (Expr -> Expr -> Expr)], [Parser (Expr -> Expr -> Expr)]) -> String -> Integer
eval ops = eval' . parseExpr ops

eval' :: Expr -> Integer
eval' (Num x)           = x
eval' (Op Add x y)      = eval' x + eval' y
eval' (Op Mul x y)      = eval' x * eval' y

-- Parser

parseExpr :: ([Parser (Expr -> Expr -> Expr)], [Parser (Expr -> Expr -> Expr)]) -> String -> Expr
parseExpr ops s =
  case parse (spaces *> expression ops <* eof) "" s of
    Left e  -> error $ show e
    Right x -> x

expression :: ([Parser (Expr -> Expr -> Expr)], [Parser (Expr -> Expr -> Expr)]) -> Parser Expr
expression ops = lowerExpr ops
         <|> higherExpr ops
         <|> number
         <|> parens (expression ops)

lowerExpr :: ([Parser (Expr -> Expr -> Expr)], [Parser (Expr -> Expr -> Expr)]) -> Parser Expr
lowerExpr (ops,ops') = try $ expression' `chainl1` operator
  where expression' = higherExpr (ops,ops')
                  <|> number
                  <|> parens (expression (ops,ops'))

        operator = choice ops <* spaces

higherExpr :: ([Parser (Expr -> Expr -> Expr)], 
               [Parser (Expr -> Expr -> Expr)]) -> Parser Expr
higherExpr (ops,ops') = try $ expression' `chainl1` operator
    where expression' = number
                    <|> parens (expression (ops,ops'))

          operator = choice ops' <* spaces

number :: Parser Expr
number = do
  digits <- many1 digit
  spaces
  return $ Num $ read digits

parens :: Parser a -> Parser a
parens = between open close 
  where open  = char '(' <* spaces
        close = char ')' <* spaces

-- lower and higer precedence ops for task1
task1 :: ([Parser (Expr -> Expr -> Expr)], [Parser (Expr -> Expr -> Expr)])
task1 = ([ Op Add <$ char '+', Op Mul <$ char '*' ], [])

-- lower and higer precedence ops for task2
task2 :: ([Parser (Expr -> Expr -> Expr)], [Parser (Expr -> Expr -> Expr)])
task2 = ([Op Mul <$ char '*'], [Op Add <$ char '+'])

main  = do
  is <- readFile "day18_input" <&> lines

  print (sum $ map (eval task1) is)
  print (sum $ map (eval task2) is)