https://adventofcode.com/2020/day/18 ('Operation Order')

I originally did this question in the quick'n'dirty way described below. However there are a few other approaches, including a very sneaky use of Python's own interpreter.

Quick and Dirty Method

In part 1, the * and + operators in the expressions we're given have the same precedence. Evaluating an expression without brackets is therefore pretty easy: we can work through the operators from left to right and apply them. This looks like:

def evaluate_simple(expression):
    'Take an expression without brackets and calculate its value'
    current_op = None
    result = None
    for item in expression.split():
        if item == '+' or item == '*':
            current_op = item
        else:
            value = int(item)
            if current_op is None:
                result = value
            elif current_op == '*':
                result *= value
            elif current_op == '+':
                result += value
            else:
                raise(Exception("Bad expression: " + expression))
    return result

But how do we handle brackets? There will always be an innermost sub-expression that doesn't itself contain brackets and this can be evaluated using evaluate_simple(). Substituting the result back in to the original expression will eliminate a set of brackets, and doing this repeatedly will gradually reduce the expression down to a single number.

For example, consider ((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2:

Find innermost sub-expressions:
((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2
 ^^^^^^^^^^^   ^^^^^^^^^^^^^^^

Evaluate:
(54 * 126 + 6) + 2 + 4 * 2

Find innermost sub-expressions:
(54 * 126 + 6) + 2 + 4 * 2
^^^^^^^^^^^^^^

Evaluate:
6810 + 2 + 4 * 2

No brackets left, so evaluate:
13632

A simple way to look for the innermost sub-expressions is to use a regex. The sub-expressions we're looking for should be surrounded by brackets and contain only digits, addition or multiplication operators, or white space - they cannot contain brackets themselves:

SIMPLE_EXPRESSION_REGEX = re.compile(r'\(([\d +*]+)\)')

Therefore evaluating a whole expression involves repeated application of this regex to find a sub-expression that can be evaluated, followed by use of evaluate_simple() to get its value and then substitution of the value back into the expression string:

def evaluate(expression):
    while '(' in expression:
        # Find sub-expression without brackets
        for simple_expression in SIMPLE_EXPRESSION_REGEX.findall(expression):
            # Replace each sub-expression (and the surrounding
            # brackets) with its value
            result = evaluate_simple(simple_expression)
            expression = expression.replace('(' + simple_expression + ')', str(result))
    # At this point we have a single expression that contains
    # no brackets
    return evaluate_simple(expression)

Part 1 is therefore:

def part1():
    with open('day18.txt', 'rt') as input_file:
        return sum(evaluate(expression) for expression in input_file.read().splitlines())

In part 2, + has higher precedence than *. With a bit of tweaking we can apply the same technique as before as long as within the innermost sub-expressions we evaluate the additions first.

Consider again ((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2:

Find innermost sub-expressions (as per part 1):
((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2
 ^^^^^^^^^^^   ^^^^^^^^^^^^^^^

Within those sub-expressions find additions:
((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2
  ^^^^^         ^^^^^   ^^^^^

Evaluate additions:
((6 * 9) * (15 * 14) + 6) + 2 + 4 * 2

Evaluate resulting bracketed sub-expressions:
(54 * 210 + 6) + 2 + 4 * 2

Find innermost sub-expressions (as per part 1):
(54 * 210 + 6) + 2 + 4 * 2
^^^^^^^^^^^^^^

Within those sub-expressions find additions:
(54 * 210 + 6) + 2 + 4 * 2
      ^^^^^^^

Evaluate additions:
(54 * 216) + 2 + 4 * 2

Evaluate resulting bracketed sub-expressions:
11664 + 2 + 4 * 2

No brackets left, so find additions:
11664 + 2 + 4 * 2
^^^^^^^^^^^^^

Evaluate additions:
11670 * 2

Evaluate resulting expression:
23340

In order to do this, we need to wrap every call to evaluate_simple() with some logic to pick out and evaluate the additions beforehand. We can find the additions using another regex: one that matches two numbers with some whitespace and a plus between them (a glance at the puzzle input suggests that the usage of whitespace is consistent and every operator has a space on either side):

ADD_EXPRESSION = re.compile(r'\d+ \+ \d+')

However we have to be careful when substituting the result back in to the expression string in place of the addition expression. In part 1 we just used the string .replace() method and this worked perfectly well as the string being replaced was always bookended by brackets but could never contain brackets itself. However imagine that we've just evaluated the addition expression 23 + 45 and want to substitute the result 68 back in to the string 23 + 45 + 123 + 456. Here a simple replace operation would result in the string 68 + 1686 - which is clearly not the desired result!

Taking all this into account we end up with this function that wraps evaluate_simple():

def evaluate_simple_with_additions_first(expression)
    match = ADD_EXPRESSION.search(expression)
    while match:
        result = evaluate_simple(match.group())
        # Ensure we replace only the bit of the string where
        # the addition expression was found
        expression = expression[:match.start()] + str(result) + expression[match.end():]
        match = ADD_EXPRESSION.search(expression)
    return evaluate_simple(expression)

The rest of the code is basically the same before, except that evaluate_simple_with_additions_first() is called instead of evaluate_simple():

def evaluate_advanced(expression):
    while '(' in expression:
        # Find sub-expression without brackets
        for simple_expression in SIMPLE_EXPRESSION.findall(expression):
            # Replace each sub-expression (and the surrounding 
            # brackets) with its value
            result = evaluate_simple_with_additions_first(simple_expression)
            expression = expression.replace('(' + simple_expression + ')', str(result))
    # At this point we should have an expression that contains 
    # no brackets
    return evaluate_simple_with_additions_first(expression)

def part2():
    with open('day18.txt', 'rt') as input_file:
        return sum(evaluate_advanced(expression) for expression in input_file.read().splitlines())

This regex-and-substitution approach runs for me in about 5ms for part 1 and 12ms for part 2.

Doing it Properly

There are all sorts of algorithms that can be used to parse expressions containing infix operators like + or * that may have different precedence:

• The Shunting-Yard Algorithm
• Recursive Descent
• Pratt Operator Precedence Parser

To use any of these algorithms we need to turn the expression to be parsed into a stream of tokens, e.g. (, 123, + etc. We can almost do this by splitting on white space, except that the brackets aren't completely surrounded by white space so we must fix that first:

def get_tokenised_lines():
    with open('day18.txt', 'rt') as input_file:
        for line in input_file.read().splitlines():
            # Insert extra whitespace where necessary, then split on whitespace
            yield line.replace('(', ' ( ').replace(')', ' ) ').split()

As I'd written a Pratt parser before, I decided to see what would be involved in getting one working here. This kind of parser feels slightly mysterious and the write-up here certainly won't do it justice. Some better sources of information are:

• Pratt Parsers: Expression Parsing Made Easy (in Java)
• Simple but Powerful Pratt Parsing (in Rust)
• Top Down Operator Precedence (in JavaScript - this article by Douglas Crockford introduced me to Pratt parsers, and goes on to extend one to parse a reasonable subset of JavaScript)

Usually the result of any parsing algorithm is an abstract syntax tree (AST), a data structure that represents the expression, which is then processed in a subsequent step (to evaluate it, or perhaps compile it into machine code or another target format). For example, consider 1 * 2 + 3 * 4. Using the precedence rules from part 2 one possible arrangement of an AST for this expression would be:

      *
     / \
    1   *
       / \
      +   4
     / \
    2   3

Once the tree is built it can be evaluated using depth-first recursion. As we're only dealing with integers and arithmetical operations, we can simplify things by merging the parsing and evaluation into a single step.

A Pratt parser tries to parse an expression recursively using the following rules:

1. An expression can only begin in certain ways. In our case this is either with a number or a (, but in many languages expressions could also start with operators like - or !. For us:
   • If we read a number then that evaluates to itself
   • If we read a ( then there's another expression lurking inside the brackets. Therefore we must recursively read and evaluate that before continuing, making sure we also consume the matching ).
2. If an infix operator (i.e. + and * in our case) is encountered then we must decide what to do: either this operator forms part of the expression being read, or operator precedence rules mean that we should stop parsing the current sub-expression and return to the caller.
   • If we're parsing a sub-expression to the right of a + then we need to stop as soon as we hit a *. This is because + has a higher precedence than * so things either side of the + will 'bind' to it more readily than to a *.
   • If we're parsing a sub-expression to the right of a * then there's no problem if we hit a +: as this has a higher precedence it should form a self-contained sub-expression of its own.
   • As a result, when parsing an expression we need to remember the precedence of the operator we're parsing it for so we can decide whether to stop or continue.

This might be clearer with a couple of examples! For this to work we need to give numerical precedence values to our operators, so let's give * a precedence of 1 and + a precedence of 2.

First let's look at 1 + 2 * 3 (which should evaluate to 9 in part 2):

1. Start reading the expression. This is the outermost expression so it doesn't belong to any operator in particular - as a result we have a 'current precedence' of 0.
2. Get the next token. This is a 1, which evaluates to 1.
3. Look at the next token. It's a + and has a precedence of 2, which is higher than the current precedence of 0. Therefore the + will form part of the current expression and we need to read the sub-expression belonging to it on its right hand side. As a result we recurse, setting the current precedence to 2.
   1. Start reading an expression with the current precedence set to 2.
   2. Get the next token. This is a 2, which evaluates to 2.
   3. Look at the next token. It's a * and has a precedence of 1, which is not higher than the current precedence of 2. Therefore the * does not form part of the current expression and we leave it alone, returning 2 as that's what we have so far.
4. We now know that the sub-expression on the right of the + evaluates to 2, so we can evaluate the addition itself: 1 + 2 gives 3.
5. Now we look at the next token. It's an asterisk and has a precedence of 1, which is higher than the current precedence of 0. Therefore the multiplication will form part of the current expression and we need to read the sub-expression belonging to it on its right-hand side. As a result we recurse, setting the current precedence to 1.
   1. Start reading an expression with the current precedence set to 1.
   2. Get the next token. This is a 3, which evaluates to 3.
   3. There are no tokens left, so this sub-expression must evaluate to 3 and we return 3 to the caller.
6. We now know that the sub-expression on the right of the * evaluates to 3, so we can evaluate the multiplication itself: 3 * 3 gives 9.
7. There are no tokens left, so we return 9 to the caller.

Now consider 1 * 2 + 3 (which should evaluate to 5):

1. Start reading the expression. This is the outermost expression so it doesn't belong to any operator in particular - as a result we have a 'current precedence' of 0.
2. Get the next token. This is a 1, which evaluates to 1.
3. Look at the next token. It's a * and has a precedence of 1, which is higher than the current precedence of 0. Therefore the * will form part of the current expression and we need to read the sub-expression belonging to it on its right hand side. As a result we recurse, setting the current precedence to 1.
   1. Start reading an expression with the current precedence set to 1.
   2. Get the next token. This is a 2, which evaluates to 2.
   3. Look at the next token. It's a + and has a precedence of 2, which is higher than the current precedence of 1. Therefore the + will form part of the current expression and we need to read the sub-expression belonging to it on its right hand side. As a result we recurse, setting the current precedence to 2.
      1. Start reading an expression with the current precedence set to 2.
      2. Get the next token. This is a 3, which evaluates to 3.
      3. There are no tokens left, so this sub-expression must evaluate to 3 and we return 3 to the caller.
   4. We now know that the sub-expression to the right of the + evaluates to 3, so we can evaluate the addition itself: 2 + 3 gives 5.
   5. There are no tokens left so we return 5 to the caller.
4. We now know that the sub-expression to the right of the * evaluates to 5, so we can evaluate the multiplication itself: 1 * 5 gives 5.
5. There are no tokens left so return 5 to the caller.

What about brackets?

• If we encounter an ( then we recurse, setting the current precedence back to 0 as though we were reading the outermost expression.
• If we encounter an ) we always want to stop reading the current sub-expression. We can do this by making ) an operator with a precedence of 0. As a precedence of 0 will never be higher than the current precedence, this will always terminate the current sub-expression.

To turn this into code, we first need a dictionary mapping each operator to its precedence and the function used when the operator is evaluated:

from operator import mul, add

# For part 1: addition and multiplication have the same
# precedence.
# As described above, ')' needs an entry here with a precedence
# of 0.
SIMPLE_OPERATORS = {
    '*': (1, mul),
    '+': (1, add),
    ')': (0, None)
}

# For part 2: addition has a higher precedence than
# multiplication.
ADVANCED_OPERATORS = {
    '*': (1, mul),
    '+': (2, add),
    ')': (0, None)
}

The evaluation function itself requires the tokens to be fed in in reverse order (it's easier to pop tokens from the end of a list than the beginning). It looks like:

def evaluate_pratt(tokens, operators, current_precedence=0):
    'Note: assumes that tokens is a list of tokens in reverse order'
    # At this point we are reading the start of an expression or 
    # sub-expression. The only possibilities here are a number
    # or an open bracket.
    token = tokens.pop()
    if token == '(':
        # Following tokens must be a sub-expression followed 
        # by a ')'. Read the sub-expression, resetting the
        # current_precedence to 0:
        result = evaluate_pratt(tokens, operators)
        # Remove the ')':
        tokens.pop()
    else:
        # Token must be an integer.
        result = int(token)

    while tokens:
        # At this point the left-hand sub-expression has been
        # read and evaluated. The next token must be one of the 
        # operators or a close bracket. Take a look and use the
        # operator dictionary to look up the precedence and the
        # operator's function (if any).
        peek = tokens[-1]
        operator = operators.get(peek)
        if operator is None:
            raise Exception('Unexpected token: ' + peek)
        (power, op) = operator
        # If this operator's precedence is higher than the
        # current precedence then include it in the current
        # expression - otherwise stop reading the expression.
        if power > current_precedence:
            tokens.pop()
            right = evaluate_pratt(tokens, operators, power)
            result = op(result, right)
        else:
            break

    return result

With the above, parts 1 and 2 become:

def part1_new():
    return sum(evaluate_pratt(tokens[::-1], SIMPLE_OPERATORS) for tokens in get_tokenised_lines())

def part2():
    return sum(evaluate_pratt(tokens[::-1], ADVANCED_OPERATORS) for tokens in get_tokenised_lines())

As the two parts are using exactly the same logic (the precedence tables of the operators being the only difference) they take roughly the same amount of time: about 6ms.

Doing it Sneakily

Of course, Python already knows how to parse expressions - it does this every time we run some Python code. Why don't we get Python to do the hard work for us?

To make this work we need to use the eval() built-in function to parse and evaluate the expressions. However we will need to do some tricks to get Python to treat addition and multiplication with same precedence for part 1 - or addition with a higher precedence for part 2.

If, rather than performing arithmetic with integers directly, Python is instead using instances of a class of our own then we can control what it means to multiply and add. Therefore instead of doing eval('1 + 2 * 3') we could do eval('Value(1) + Value(2) * Value(3)') where Value is a class we've defined that represents a numeric value.

However this only gets us part of the way there as Python will still perform Value(2) * Value(3) before the addition because the operator precedence is baked into the language. If we want the precedence of these operations to be the same then we'll need to manipulate things a bit more so we're actually calling eval('Value(1) / Value(2) * Value(3)') - i.e. we've replaced the + operator with the / operator as it has the same precedence as *, but we've also redefined / for the Value class to be addition.

For part 2 we need to go one step further and downgrade the precedence of the * operator. We can do this by replacing * with + (having previously replaced + with /) and defining + to be multiplication.

Putting these ideas together we have:

class Value:
    def __init__(self, value):
        self.value = value

    def __mul__(self, other):
        return Value(self.value * other.value)

    def __truediv__(self, other):
        'Override the / operator to perform addition'
        return Value(self.value + other.value)

    def __add__(self, other):
        'Override the + operator to perform multiplication'
        return Value(self.value * other.value)

VALUE_REGEX = re.compile(r'(\d+)')

def evaluate_sneaky(expression):
    # Wrap the numbers in the expression with a Value constructor
    expression = VALUE_REGEX.sub(r'Value(\1)', expression)
    # Upgrade addition to division to increase precedence
    expression = expression.replace('+', '/')
    return eval(expression).value

def part1():
    with open('day18.txt', 'rt') as input_file:
        return sum(evaluate_sneaky(expression) for expression in input_file.read().splitlines())

def evaluate_advanced_sneaky(expression):
    expression = VALUE_REGEX.sub(r'Value(\1)', expression)
    # Upgrade addition to division to increase precedence
    expression = expression.replace('+', '/')
    # Downgrade multiplication to addition to reduce precedence
    expression = expression.replace('*', '+')
    return eval(expression).value

def part2():
    with open('day18.txt', 'rt') as input_file:
        return sum(evaluate_advanced_sneaky(expression) for expression in input_file.read().splitlines())

This performs less well than the other solutions, taking about 35ms for either part. I guess spinning up the Python expression parsing machinery has a cost!