Advent of Code 2020: Day 18 reflection

The day 18 puzzle from last year’s Advent of Code involved parsing and evaluating arithmetic expressions, but with a twist:

Part 2 is similar, but instead of having the same precedence, addition is evaluated before multiplication.

When I first went about solving this puzzle, I wrote some Python code to look for parentheses, and split expressions at operators, and then evaluate those expressions recursively.

But afterwards I got curious… this seems like an awful lot of work. Can we find a lazier approach?

What if we could use a programming language where we can directly redefine the + and * functions to have a different precedence?

Operator precedence

There may be other languages we could use for this, but the one that came to mind for me was Haskell. Haskell allows you to define your own operators, and to specify their precedence levels.

We can use GHC’s interactive environment to check the default operator precedence for + and *, using the :info command:

ken$ ghci
GHCi, version 8.8.2: https://www.haskell.org/ghc/  :? for help
Prelude> :info +
class Num a where
  (+) :: a -> a -> a
  ...
  	-- Defined in ‘GHC.Num’
infixl 6 +
Prelude> :info *
class Num a where
  ...
  (*) :: a -> a -> a
  ...
  	-- Defined in ‘GHC.Num’
infixl 7 *

The line infixl 6 + tells us that the + operator has precedence level 6.¹ Likewise, the * operator has precedence level 7. Because * has a higher precedence level, it will be evaluated before +.

So, we can just redefine the precedence for + so that it is the same as for *:

Prelude> infixl 7 +

<interactive>:1:10: error:
    The fixity signature for ‘+’ lacks an accompanying binding
      (The fixity signature must be given where ‘+’ is declared)

Well, OK, not quite like that… it looks like we have to redefine the + operator itself at the same time if we want to assign a new operator precedence. We can do that with a no-op definition, using a qualified reference to the original + operator:

Prelude> (+) = (Prelude.+); infixl 7 +
Prelude> 1 + 2 * 3
9

But hey, look at that! Now 1 + 2 * 3 equals 9!

A complete solution

The puzzle asks for the sum of all the expressions in the input file (which has one expression per line).

So, if we take our input file, stick the redefinition of + at the top, and run the whole lot through ghci, we can evaluate all of the expressions in the input.

Something like this command line:

echo "(+) = (Prelude.+); infixl 7 +
$(cat input18.txt)" | ghci -v0

The -v0 option allows us to suppress the prompt output from ghci, so we get just the results of each expression as our output, one per line.

Once we have the expressions evaluated, we still need to get the sum of all the values. We could use some awk for this:

echo "(+) = (Prelude.+); infixl 7 +
$(cat input18.txt)" | ghci -v0 | awk '{sum+=$1} END {print sum}'

We can do a very similar thing for part 2, where we need to swap the precedence of addition and multiplication:

echo "(+) = (Prelude.+); infixl 7 +; (*) = (Prelude.*); infixl 6 *
$(cat input18.txt)" | ghci -v0 | awk '{sum+=$1} END {print sum}'

And there you have it! No need to balance parentheses or parse expressions.

If there were a contest for “most oddball solution”, this would be my entry.