Advent of Code: Day #18 - Operation Order

18th of December 2020 |

5 - 6 minutes

Introduction

My solution feels very kludged together today but it works, and my part two is quite nice!

Task One

Given an equation evaluate it from left to right with no order of operations, parentheses are still evaluated first however.

Reading in the data

The equations where just read into an array.

Python Copy

def read_data(path):
    dataset = []
    with open(path) as f:
        for line in f.readlines():
            dataset.append(line.strip())
    return dataset

The Solution

To start with I decided to split the question into a list, "1+(2*3)+(4*(5+6))" became ['1','+',['2','*','3'],'+',['4','*',['5','+','6']]]. I then loop through the items in these lists and create a new expression with the brackets evaluated, I do this by calling the same function on the sub brackets. The sum before would become 1 + 6 + (4 * 11) and then 7 + 44 and finally returned as 51.

Python Copy

def task_one(data):
    # Match numbers, the Plus and Times symbol and a whitespace
    matcher = pyparsing.Word(pyparsing.alphanums) | '+' | '*' | " "
    # Match them between nested parentheses
    parens = pyparsing.nestedExpr('(', ')', content=matcher)

    def try_int(s):
    try:
        return int(s)
    except ValueError:
        return s

    def solve(string_equation):
        def _eval(s):
            """
            Evaluates an expression left to right
            :param s: String expresion
            :return: The answer
            """

            total = 0
            operator = None
            list_expr = [i.strip() for i in re.split(r"([\w']+)", s)[1:-1]]

            for i in list_expr:
                item = try_int(i)
                if type(item) is int:
                    if operator == "*":
                        total *= item
                    elif operator == "+":
                        total += item
                    elif operator is None:
                        total = item
                else:
                    operator = item
            return total

        def _solve(list_equation, depth=0):

            memory = []
            simplified_equation = ""

            for index, item in enumerate(list_equation):
                if type(item) != list:
                    memory.append(item)
                else:
                    # Got to a bracket
                    if len(memory) >= 1:
                        memory.pop()
                        simplified_equation += "".join(memory)
                        memory = []
                        new_eq_tmp = f" {list_equation[index - 1]} {_solve(item, depth + 1)}"
                        simplified_equation += new_eq_tmp
                    else:
                        new_eq_tmp = f" + {_solve(item, depth + 1)}"
                        simplified_equation += new_eq_tmp

            simplified_equation = f"{simplified_equation} {''.join(memory)}"
            if index >= len(list_equation) - 1:
                return _eval(simplified_equation)
            return simplified_equation

        groups = parens.parseString("(" + string_equation + ")").asList()[0]
        return _solve(groups)

    ans = sum([solve(question) for question in data])
    return ans

Task Two

The Solution

For Task Two we are told to implement an order of operations where addition comes before multiplication. To implement this I used a trick from the old FORTRAN complier and wrapped the questions in a load of brackets and then just used the left to right solver we made in part one.

Python Copy

def task_two(data):
    def parenthesise(s):
        return "((" + s.replace("(", "(((").replace(")", ")))").replace("*", "))*((").replace("+", ")+(") + "))"

    return task_one([parenthesise(s) for s in data])

Links

Leaderboard Code: 353270-1fc6ef28

Github Repository A link to the github repo containing all the days.

main.py A direct download of the main.py script

2.9Kb