Advent of Code 2020 - Day 18

By Eric Burden | December 19, 2020

In the spirit of the holidays (and programming), I’ll be posting my solutions to the Advent of Code 2020 puzzles here, at least one day after they’re posted (no spoilers!). I’ll be implementing the solutions in R because, well, that’s what I like! What I won’t be doing is posting any of the actual answers, just the reasoning behind them.

Also, as a general convention, whenever the puzzle has downloadable input, I’m saving it in a file named input.txt.

Day 18 - Operation Order

Find the problem description HERE.

Part One - Common Core?

You know, it just doesn’t seem right, the way they keep changing math… I mean, it’s math, right? Whatever. We can handle this. The good news is that parentheses continue to work correctly, so we can just work from the innermost parentheses outward to find the results per line.

library(stringr)  # For all the str_*() functions
library(stringi)  # For stri_replace_all_fixed()

test_input <- c(
"2 * 3 + (4 * 5)",
"5 + (8 * 3 + 9 + 3 * 4 * 3)",
"5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))",
"((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2"
)

# Given a string with at least some part contained in parentheses
# parens_w_contents, return the string inside the parentheses
parens_contents <- function(parens_w_contents) {
str_extract(parens_w_contents, '(?<=\$$).+(?=\$$)')
}

# Given a string exp_part, return a list of the string components split
# on space sequences
tokenize <- function(exp_part) {
str_split(exp_part, '\\s+')
}

# Given a character vector of regex patterns patterns, a character vector
# of replacement strings replacements, and a string expression exp, replace
# each instance of a pattern with the corresponding replacement string in exp
sub_value <- function(patterns, replacements, exp) {
stri_replace_all_fixed(exp, patterns, replacements, vectorize_all = F)
}

# Given a list of character strings tokens consisting of either numbers, the
# '+' symbol, or the '*' symbol (notably, no parentheses!) evaluate the tokens
# as a mathematical expression from left to right, as described by the puzzle
# instructions
eval_tokens <- function(tokens) {
operator <- +
total <- 0
for (token in tokens) {
if (str_detect(token, '\\d+')) {
next_number <- as.numeric(token)
total <- operator(total, next_number)
} else {
operator <- match.fun(token)
}
}
total
}

# Given a string containing one or more expressions wrapped in parentheses
# exp_w_parens, evaluate all expressions contained in the innermost set
# of parentheses.
# Example: simplify('2 * (3 + (4 * 5) + 6)') => '2 * (3 + 20 + 6)
# Example: simplify('(1 + (2 * 3) + (4 + 5)) => '(1 + 6 + 9)
simplify <- function(exp_w_parens) {
# Extract all innermost parentheses expressions, with parentheses included
inner_parens <- str_extract_all(exp_w_parens, '\$$[\\d\\s\\+\\*]+\$$')

contents <- lapply(inner_parens, parens_contents)  # Unwrap parentheses
token_lists <- lapply(contents, tokenize)          # Tokenize the contents

# Evaluate each tokenized contents expression
replacements <- lapply(token_lists, function(x) { lapply(x, eval_tokens) })

# Replace each inner_parens string in the original exp_w_parens with the
# evaluated value
mapply(sub_value, inner_parens, replacements, MoreArgs = list(exp = exp_w_parens))
}

# Given a list of expressions exps, repeatedly simplify and evaluate the
# innermost parenthetical expressions until the expression has been reduced
# to a single value, as shown in the example. As follows:
# '2 * 3 + (4 * 5)' => '2 * 3 + 20' => '6 + 20' => 26
eval_exps <- function(exps) {
# If the expression contains any parenthetical components, evaluate them
# starting with the innermost parenthetical components and working outwards
needs_simplifying <- str_detect(exps, '[\$$\$$]')
while (any(needs_simplifying)) {
exps[needs_simplifying] <- lapply(exps[needs_simplifying], simplify)
needs_simplifying <- str_detect(exps, '[\$$\$$]')
}

# Once exps has been converted entirely to simple tokens, evaluate
# the entire remaining expressions to a numeric vector
vapply(tokenize(exps), eval_tokens, numeric(1))
}

results <- eval_exps(real_input)  # Evaluate all the things!
answer1 <- sum(results)           # Sum the results


No sweat! I can’t shake the feeling that there’s some more clever ‘data-structure-ish’ way to handle this (maybe involving a stack or some such), but it’s not immediately obvious to me.

Part Two - Indistinguishable from Magic

Turns out that ‘advanced’ in this case means ‘all your previous answers are wrong’. Actually, that’s not terribly far off from my experience of math in general… For part two, addition and subtraction now have an order of operations, it’s just backwards from the actual order in which these should be evaluated according to PEMDAS. For our purposes, it mostly means changing how we evaluate the tokens in the expressions once we’ve broken them down.

source('exercise_1.R')

test_input <- c(
"1 + (2 * 3) + (4 * (5 + 6))",
"2 * 3 + (4 * 5)",
"5 + (8 * 3 + 9 + 3 * 4 * 3)",
"5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))",
"((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2"
)

# Given a list of character strings tokens consisting of either numbers, the
# '+' symbol, or the '*' symbol (notably, no parentheses!) evaluate the tokens
# as a mathematical expression as described in the puzzle input
# Example: '2 * 3 + (4 * 5)' => '2 * 3 + 20' => '2 * 23' => '46'
eval_tokens <- function(tokens) {
total <- 0                 # Running total
summed_nums <- numeric(0)  # List of summed numbers

# For each token in the list...
for (token in tokens) {

if (str_detect(token, '\\d+')) {
# If the token is a number, then add it to the running total
next_number <- as.numeric(token)
total <- total + next_number
} else if (token == '*') {
# Otherwise, if the token is a '*' operator, append the running total to
# the vector summed_nums, then restart the total
summed_nums <- c(summed_nums, total)
total <- 0
}

# Just ignore the '+' operators...
}

# Finally, multiply all the summed_nums (and total) together
prod(summed_nums, total)
}

results <- eval_exps(real_input)  # Evaluate again!
answer2 <- sum(results)           # Sum the results


If we anticipated the list of tokens to ever grow very long, we’d likely gain some performance by changing summed_nums to a stack, adding total to it, then converting to a vector afterward.

Wrap-Up

I started trying to solve this one by trying to build the expressions into some semblance of an abstract syntax tree and evaluating that, but I realized that I might be over-complicating it a bit. That said, I’d really like to see that sort of approach, I bet I could learn a lot from it.

If you found a different solution (or spotted a mistake in one of mine), please drop me a line!