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 1 - Report Repair

Find the problem description HERE.

Part One - Numbers that Sum

This first part asks you to identify two numbers in a list that sum to 2020 and multiply them together to get the answer. The multiplication step implies that there are only two numbers in the list that will satisfy this problem, which means we can take a naive approach using R vector math:

input <- readLines('input.txt')  # Get the list of numbers from a file
input_nums <- as.numeric(input)  # Convert the strings to numbers

minus_2020 <- 2020 - input_nums  # Subtract all the numbers from 2020

# Find all the numbers in `minus_2020` that are also in the input
adds_to_2020 <- minus_2020[minus_2020 %in% input_nums]

answer <- adds_to_2020[1] * adds_to_2020[2]  # Multiply the two numbers together

This works because of the assumption that there are two, and only two, numbers in that list that add up to 2020. There are a couple of situations that could break this algorithm:

1. More than one pair of numbers that sum to 2020.
2. If 1010 were in the list (half of 2020).

A more robust approach would be a variation on the two pointer technique like so:

p1 <- 1                   # The first pointer, the beginning of the vector
p2 <- length(input_nums)  # The second pointer, the end of the vector
search_space <- sort(input_nums)  # Sorts the numbers in ascending order
current_total <- search_space[p1] + search_space[p2]

# Keep trying until either the pointers cross in the middle OR you find the answer
while (p1 < p2 & current_total != 2020) {
  if (current_total < 2020) { p1 <- p1 + 1 }  # Move p1 toward the end
  if (current_total > 2020) { p2 <- p2 - 1 }  # Move p2 toward the beginning
  current_total <- search_space[p1] + search_space[p2]
}

answer <- if (p1 < p2) { search_space[p1] * search_space[p2] } else { NA }

This works by setting a ‘pointer’ to each end of the input vector, checking the sum of the two numbers being ‘pointed’ at, adjusting one of the pointers toward the middle, then repeating. If the sum is bigger than the target (2020), move the second pointer towards the beginning, and if the sum is bigger than the target, move the first pointer towards the end. Because the input vector is sorted, each iteration moves the sum closer to the target number. If the pointers ever cross, then you know the target sum can’t be found. This can be represented visually like so:

This search is looking for numbers that sum to 56.

Part Two - Same Sum, More Numbers

How could this puzzle get better? More numbers! Specifically, part two requires finding three numbers in the list that sum to 2020 and multiplying them all together to get the final answer. We need to find three numbers, so let’s review three different strategies for getting there.

The Memory Hog

Since I’m implementing these in R, might as well take advantage of my favorite built-in data structure: dataframes! I’m calling this the ‘rainbow table’ approach because I’m literally building a table of all possible combinations of the input vector and just searching for the row that sums to 2020 across.

rainbow_table <- expand.grid(
  list(first = input_nums, second = input_nums, third = input_nums)
)

addends <- with(rainbow_table, rainbow_table[first + second + third == 2020,])
answer <- addends$first[1] * addends$second[1] * addends$third[1]

It works, but larger inputs will be very memory inefficient; the dataframe will live in memory as long as it’s in the environment.

The General Approach

Pointers worked really well with the two-number version of this puzzle; it seemed like there should be a good pointer-based solution for the three-number version. In fact, it should be is possible to implement a solution for any number of pointers. I call this one ‘cascading pointers’.

search_space <- unique(sort(search_space, decreasing = T))
pointers <- seq(n)
mp <- n

while (sum(search_space[pointers]) != total) {
  # The maximum index for the moving pointer `mp`, the length of the
  # search_space minus all the pointers 'in front of' the moving pointer
  farthest_point <- length(search_space) - (length(pointers) - mp)

  # If the moving pointer has moved as far as it can OR the current sum is
  # less than the total (indicating that moving that pointer forward will
  # not result in a sum == total):
  #  - If the moving pointer is the first pointer, the search_space has been
  #  exhausted, return NA
  #  - Otherwise, switch to the preceding pointer as the moving pointer
  if (pointers[mp] == farthest_point | sum(search_space[pointers]) < total) {
    if (mp == 1) { 
      pointers <- NA
      break
    }
    mp <- mp - 1
  }

  # Move the moving pointer ahead one
  pointers[mp] <- pointers[mp] + 1

  # If the moving pointer is not the last pointer in the sequence
  #  - Calculate how far the current pointer is from the next pointer in the
  #  series
  #  - If there is space between the current pointer and the next pointer
  #    - Stash the current pointer
  #    - Assign the next pointer in series as the moving pointer
  #    - Move the new moving pointer to the index immediately after the
  #    preceding pointer
  if (mp < length(pointers)) {
    distance_to_next_pointer <- pointers[mp + 1] - pointers[mp]
    if (distance_to_next_pointer > 1) {
      last_point <- pointers[mp]
      mp <- mp + 1
      pointers[mp] <- last_point + 1
    }
  }
}

answer <- prod(search_space[pointers])

If the comments weren’t enough, here’s how this search proceeds along a smaller vector:

As you can see, every unique combination of elements is marked by a pointer during traversal. This method works, and it feels better than the rainbow table approach, but there’s one more approach that’s a bit more finely tuned for this exact problem.

The Very Specific Solution

The final approach is more direct variation on the two-pointer approach used in the first problem, with the addition of an enclosing for loop. Here, I’m almost combining the two solutions for part one. First, I sort the search space then subtract all the original input numbers from 2020. Then, for each number at sequential index i in minus_2020, I use the two-pointer method to attempt to find the two numbers in the search_space that sum to that number. Those two numbers, plus the number from the search_space at index i, will sum to 2020.

search_space <- sort(input_nums)  # Sorts the numbers in ascending order
minus_2020 <- 2020 - search_space  # All the original numbers subtracted from 2020

for (i in seq(length(search_space))) {
  num <- minus_2020[i]
  p1 <- 1                   # The first pointer, the beginning of the vector
  p2 <- length(search_space)  # The second pointer, the end of the vector

  current_total <- search_space[p1] + search_space[p2]

  while (p1 < p2 & current_total != num) {
    if (current_total < num) { p1 <- p1 + 1 }
    if (current_total > num) { p2 <- p2 - 1 }
    current_total <- search_space[p1] + search_space[p2]
  }

  if (current_total == num) { break }
}

answer <- prod(c(search_space[i], search_space[c(p1, p2)]))

This is a faster approach (if less flexible) than the cascading pointers method and less memory-hungry than the rainbow table method.

Wrap-Up

Day 1 was honestly more challenging that I expected, especially thanks to my dissatisfaction with my first strategy for solving Part Two. On the other hand, I was really pleased with the ‘cascading pointers’ algorithm, as much as for a learning experience as for something I can really use in the future. If you found a different solution (or spotted a mistake in one of mine), please drop me a line!