2020-12-18 - Operation Order
(original .ipynb)
Day 18 input is a sequence of calculations (mine is here) involving integers, + and * operators and parenthesised expressions. Part 1 involves finding the sum of these calculations, assuming they have a simple left-to-right order of evaluation. Part 2 involves the same except assuming + has higher precedence than *.
import re
puzzle_input_str = open("puzzle_input/day18.txt", "r").read()
def apply(op, a, b):
if op == "*":
return a * b
elif op == "+":
return a + b
else:
raise Exception(f"Not an operator, tried to eval: {a} {op} {b}")
def parse(tokens):
expression = []
while len(tokens) > 0:
token = tokens.pop(0)
if re.match("\d+", token):
expression.append(int(token))
elif token == "*":
expression.append(token)
elif token == "+":
expression.append(token)
elif token == "(":
expression.append(parse(tokens))
elif token == ")":
return expression
else:
raise Exception(f"{token}, why are you even here")
return expression
def evaluate(expression):
current_value = 0
current_operator = "+"
for e in expression:
if type(e) is int:
current_value = apply(current_operator, current_value, e)
elif type(e) is list:
current_value = apply(current_operator, current_value, evaluate(e))
elif type(e) is str:
current_operator = e
else:
raise Exception("Trying to evaluate something that cannot be evaluated")
return current_value
def calculate(input_str):
# parsing is easier if everything is separated by a space
input_str = input_str.replace("(", "( ")
input_str = input_str.replace(")", " )")
tokens = input_str.split(" ")
expression = parse(tokens)
return evaluate(expression)
# 1 + 2 * 3 + 4 * 5 + 6 becomes 71
# 1 + (2 * 3) + (4 * (5 + 6)) becomes 51
# 2 * 3 + (4 * 5) becomes 26.
# 5 + (8 * 3 + 9 + 3 * 4 * 3) becomes 437.
# 5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4)) becomes 12240.
# ((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2 becomes 13632.
assert 71 == calculate("1 + 2 * 3 + 4 * 5 + 6")
assert 51 == calculate("1 + (2 * 3) + (4 * (5 + 6))")
assert 26 == calculate("2 * 3 + (4 * 5)")
assert 437 == calculate("5 + (8 * 3 + 9 + 3 * 4 * 3)")
assert 12240 == calculate("5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))")
assert 13632 == calculate("((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2")
sum(calculate(expr_str) for expr_str in puzzle_input_str.split("\n"))
6923486965641
def fix_precedence(expression):
# Hello, I am fix_precedence. I am a monster
fixed_expression = []
# yes I enumerate a list, but also sometimes I skip over things
# this is because I am a hideous abomination
skip = False
for i, e in enumerate(expression):
# when you are a hideous abomination like me, you need to do these things
if skip:
skip = False
continue
if type(e) is list:
fixed_expression.append(fix_precedence(e))
elif type(e) is str and e == "+":
# I didn't ask to be born, I just exist because my creator
# didn't want to touch the other parts of his code. I refuse
# to apologise for my existence
lhs = fixed_expression.pop()
rhs = expression[i+1]
rhs_fixed = fix_precedence(rhs) if type(rhs) is list else rhs
fixed_expression.append([lhs, e, rhs_fixed])
skip = True
else:
fixed_expression.append(e)
# yet I yearn for the sweet release of death
return fixed_expression
def calculate_advanced(input_str):
input_str = input_str.replace("(", "( ")
input_str = input_str.replace(")", " )")
tokens = input_str.split(" ")
expression = parse(tokens)
expression = fix_precedence(expression)
return evaluate(expression)
# 1 + (2 * 3) + (4 * (5 + 6)) still becomes 51.
# 2 * 3 + (4 * 5) becomes 46.
# 5 + (8 * 3 + 9 + 3 * 4 * 3) becomes 1445.
# 5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4)) becomes 669060.
# ((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2 becomes 23340.
assert 51 == calculate_advanced("1 + (2 * 3) + (4 * (5 + 6))")
assert 46 == calculate_advanced("2 * 3 + (4 * 5)")
assert 1445 == calculate_advanced("5 + (8 * 3 + 9 + 3 * 4 * 3)")
assert 669060 == calculate_advanced("5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))")
assert 23340 == calculate_advanced("((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2")
sum(calculate_advanced(expr_str) for expr_str in puzzle_input_str.split("\n"))
70722650566361