Advent of Code 2020 - Day 1
Published: 2021-11-12 02:28:41

---
title: Advent of Code 2020 - Day 1
published: true
date: 2020-12-02 00:00:00 UTC
tags: 
canonical_url: https://ericburden.work/blog/2020/12/02/advent-of-code-2020-day-1/
---

In the spirit of the holidays (and programming), I’ll be posting my solutions to the [Advent of Code 2020](https://adventofcode.com/) 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](https://adventofcode.com/2020/day/1).

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

```r
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](https://www.geeksforgeeks.org/two-pointers-technique/) like so:

```r
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:

![](https://ericburden.work/blog/2020-12-03-advent-of-code-2020-day-1/index.en_files/animated_two_pointer_search.gif)

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.

```r
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’.

```r
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:

![](https://ericburden.work/blog/2020-12-03-advent-of-code-2020-day-1/index.en_files/cascading_pointers.gif)

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`.

```r
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!