Advent of Code 2020 Day 18

Mon 12 July 2021

This is my solution with commentary for day 18 of the 2020 set of Advent of Code problems.

The problem is to solve a series of equations where the order of operator precedence has been changed. For example:

((5 + 8 + 7 + 6 * 6 + 3) + 4 * 3 * (5 * 2) * 5 * (2 * 9)) + 6 + 3 * (2 * (2 + 4 + 8) * 4) + (9 + 3 + 6 * (9 + 5 * 6 * 3 * 8 * 5) + (4 * 6) + (6 * 3 + 2 + 8))

The problem has two parts:

Part one: multiplication and addition have the same precedence and are done left to right
Part two: the precedence for addition and multiplication is reversed

Solution: Part One

I solved this part twice. First, I wrote code to parse and step through the equation, using a stack to manage the state of the descent into nested parentheses. The python shlex module kept me from having to parse the string at the character level.

This produced the right answer, but in solving part two I saw that its much simpler solution could also be applied to part one.

import shlex

def evaluate(s):

    sh = shlex.shlex(s)

    # each element will be a list with two elements,
    # the current result and current operator
    stack_level_state = [[]]

    while True:

        token = sh.get_token()

        if token == sh.eof:
            # finished with the equation. the top of the stack is a list with two elements,
            # the first being the running result of the arithmetic, so return that
            return stack_level_state[0][0]

        if token == "(":
            # add a new level to the stack
            stack_level_state.append([])

        elif token == ")":
            # upon closing parenthesis, pop this level from the stack. add/mult this result
            # to the parent level's running result, or else make it the parent level's
            # running result.

            finished_stack_level = stack_level_state.pop()

            assert len(finished_stack_level) == 1

            if len(stack_level_state[-1]) == 0:
                stack_level_state[-1] = [finished_stack_level[0]]

            elif len(stack_level_state[-1]) == 2:
                num, op = stack_level_state[-1]

                if op == "+":
                    result = num + finished_stack_level[0]
                elif op == "*":
                    result = num * finished_stack_level[0]

                stack_level_state[-1] = [result]

        elif token in "+*":
            # add the operator to the current level of the stack
            stack_level_state[-1].append(token)

        elif token.isdigit():

            token = int(token)

            # if this level of the stack (this parenthesized equation) has no result
            # yet, make it the furst number found after the opening parenthesis
            if not stack_level_state[-1]:
                stack_level_state[-1].append(token)

            # otherwise, add or multiply this number with the current result
            else:
                num, op = stack_level_state[-1]

                if op == "+":
                    result = num + token

                elif op == "*":
                    result = num * token

                stack_level_state[-1] = [result]


In [4]: evaluate("""((5 + 8 + 7 + 6 * 6 + 3) + 4 * 3 * (5 * 2) * 5 * (2 * 9)) +
   ...:             6 + 3 * (2 * (2 + 4 + 8) * 4) + (9 + 3 + 6 * (9 + 5 * 6 * 3
   ...:             * 8 * 5) + (4 * 6) + (6 * 3 + 2 + 8))""")
Out[4]: 49473700

Solution: Part Two

The new rule is that the precedence for addition and multiplication is reversed, rather than equal. Parenthesis still have highest precedence. In other words:

2 * 3 + (4 * 5) => 46 (rather than 26)

This complicated things such that I didn't see a quick fix for the above algorithm. So I thought about an alternative that wouldn't have to maintain state. And I found a much simpler solution that would continuously evaluate parenthesized expressions from the inside out, replacing them with their result until the whole equation was reduced to its result.

This turned out to be very easy and worked well:

import re

def simplify(s, algorithm):

    while "(" in s:
        for expression in re.findall("\([ \+\*\d]+\)", s):
            s = s.replace(expression, str(algorithm(expression)))

    return algorithm(s)

The algorithm passed in to evaluate the inner (non-nested) parenthesized expressions was a parameter based on whether the calling code is solving part one vs. part two. Here are both algorithms:

import operator
from functools import reduce

def eval_expression_part_1(expression):

    # remove parenthesis
    expression = re.sub("[)(]", "", expression)

    # split expression into tokens
    expression = expression.split()

    operator_map = {"+": operator.add, "*": operator.mul}
    op = operator.add
    result = 0

    for token in expression:
        if token in "+*":
            op = operator_map[token]
        else:
            result = op(result, int(token))

    return result


def eval_expression_part_2(expression):

    # remove parenthesis
    expression = re.sub("[)(]", "", expression)

    # split expression into tokens
    expression = expression.split()

    # handle all addition first
    while "+" in expression:

        idx = expression.index("+")
        result = int(expression[idx-1]) + int(expression[idx+1])

        # replace first operand with the result
        expression[idx-1] = result

        # remove the operator token and spare operand
        del expression[idx]
        del expression[idx]


    # multiply all of the numbers that are left
    expression = [e for e in expression if e != "*"]
    return reduce(lambda a,b: int(a) * int(b), expression)

The actual solution to the Advent of Code problem was to give the sum of a large number of these equations. This code gave the final answers.

In [7]: sum(evaluate(s) for s in open("day-18.txt"))
Out[7]: 50956598240016

In [8]: sum(simplify(s, algorithm=eval_expression_part_1) for s in open("day-18.txt"))
Out[8]: 50956598240016

In [9]: sum(simplify(s, algorithm=eval_expression_part_2) for s in open("day-18.txt"))
Out[9]: 535809575344339