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"
)
real_input <- readLines('input.txt')


# 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!

comments powered by Disqus