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 9 - Encoding Error

Find the problem description HERE.

Part One - It Just Doesn’t Add Up

Non-standard ports, am I right? Ah well, we connected anyway and now we’re ready to hack the flight we’re currently on. Wait, is that what we’re really doing? Seems…unsafe. Ah well, what could go wrong? For this part, we need to identify which number (in a list of 1k numbers) can’t be derived as the sum of two of the previous 25 numbers, ignoring the first 25 numbers as the ‘preamble’. This is pretty similar to Day 1, Part 1, just repeated a bunch of times. I’ve refined my approach a bit to streamline the ‘find two numbers in this list that sum to total’-type problems. Creating a new vector by subtracting the vector of possible addends from the total, then taking the intersect of that new vector and the original vector of addends will yield a set of numbers that appear in both vectors. If there’s at least two numbers in this set, then you know there are at least two numbers in that original vector that sum to the total. If there’s only one number in the set, it means that exactly half your total was in the original vector of addends, but doesn’t mean there are two numbers that sum to the total.

test_input <- c(
   "35", "20", "15", "25", "47", 
   "40", "62", "55", "65", "95",
  "102", "117", "150", "182", "127",
  "219", "299", "277", "309", "576"
)

real_input <- readLines('input.txt')

# Helper function, checks a element of numeric vector `vec` at index `i` to
# determine whether the preceding `len` elements contain at least two items
# that sum to `vec[i]`
check_index <- function(i, vec, len) {
  # Some paranoid input validation
  if (i <= len) { stop('`i` must be greater than `len`') }
  if (length(vec) < i) { stop('`vec` must contain at least `i` items') }

  n <- vec[i] # Current number to check
  n_vec <- vec[(i-len):(i-1)] # Preceding `len` elements

  # Do at least two numbers appear in both the set of numbers you get when all
  # `n_vec` elements are subtracted from `n` and the original `n_vec` numbers?
  length(intersect(n - n_vec, n_vec)) >= 2
}

# Main function, iterates through numeric vector `vec` and checks each element
# in `vec` at index > `len` to determine whether any two of the `len` elements
# prior to `vec[i]` sums to `vec[i]`. Returns the first `i` where this is not
# true.
first_false <- function(vec, len) {
  check_range <- (len+1):length(vec) # Only check `vec` items after the `len`th

  for (i in check_range) {
    if (!check_index(i, input_as_num, check_n)) { return(i) }
  }

  return(NA)
}

input_as_num <- as.numeric(real_input)
check_n <- 25 # Number of previous items to check, 5 for tests, 25 for real data

answer1 <- input_as_num[first_false(input_as_num, check_n)]

answer1 will be used in the second part, so we saved it off with the numeric identifier. Honestly, my first two approachesto this problem were too complicated. I attempted to solve it first with a tabulation approach, which might have worked if the numbers weren’t so large. Unfortunately my (fairly beefy) laptop couldn’t allocate a vector long enough for some of the largest numbers in the real input. Memoization works, but my implementation was much slower than just using intersect() as above.

Part Two - You Feeling Strong, My Friend?

To really expose the weakness of this XMAS encryption, we need to find the contiguous section of the input vector that sums to the answer from part one. Because the inputs aren’t ordered (and sorting them would guarantee failure), I couldn’t come up with any better method that just searching for that range. Noticing a general pattern of numbers getting larger over the input, I started the search from the end hoping for a faster result. Just to check, I did also try searching from the front. Way slower. With that range in hand, we have everything we need to get the answer.

# Helper function, given an index `i`, a number `total`, and a numeric vector `vec`,
# attempts to find a contiguous range in `vec` starting with index `i` that 
# sums to `total`
check_index <- function(i, total, vec) {
  next_i <- i + 1 # The current end of the range in `vec` to check

  while (next_i <= length(vec)) {
    current_sum <- sum(vec[i:next_i]) # Current contiguous sum
    if (current_sum == total) { return(i:next_i) } # Success!
    if (current_sum > total) { return(NULL) } # No need to check further
    next_i <- next_i + 1 # Try the next `next_i`
  }
}

# Main function, given a number `total` and a numeric vector `vec`, finds the
# first contiguous segment of `vec` that sums to `total`, working backwards
# from the end of `vec`
contiguous_range_sum <- function(total, vec) {
  for (p in seq(length(vec)-1, 1)) { # Work backwards from the end
    sum_range <- check_index(p, total, vec)
    if (!is.null(sum_range)) { return(sum_range) } # NULL if no range is found
  }
  NA_integer_
}

input_as_num <- as.numeric(real_input)
sum_range <- contiguous_range_sum(answer1, input_as_num)
contiguous_nums <- input_as_num[sum_range]
answer2 <- min(contiguous_nums) + max(contiguous_nums)

I also went through a couple of unnecessarily complicated permutations of this code, but after a couple re-factors I’m pretty happy with the result.

Wrap-Up

This puzzle was pretty straightforward overall. There were a couple of not-immediately-obvious-to-me tweaks that sped up the execution a good bit, such as iterating backwards in part two. I managed to get in my own way a good bit in part one, but overall this was a nice reprieve from some of the more difficult problems from earlier days.

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