Kenneth Jenkins

Advent of Code 2020: Day 18 reflection

Why parse, when Haskell can do it for you?

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

The homework (your puzzle input) consists of a series of expressions that consist of addition (+), multiplication (*), and parentheses ((...)). Just like normal math, parentheses indicate that the expression inside must be evaluated before it can be used by the surrounding expression. Addition still finds the sum of the numbers on both sides of the operator, and multiplication still finds the product.

However, the rules of operator precedence have changed. Rather than evaluating multiplication before addition, the operators have the same precedence, and are evaluated left-to-right regardless of the order in which they appear.

These expressions consisted of integers, addition, multiplication, and parentheses to group sub-expressions.

(from https://adventofcode.com/2020/day/18)

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.1 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.


  1. This line is known as a fixity declaration. The l in infixl specifies that the + operator is left associative. There’s also infixr for right associativity, and a plain infix for non-associative operators. (See §4.4.2 of The Haskell 2010 Language for more info.) ↩︎