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 10 - Adapter Array

Find the problem description HERE.

Part One - Something for Nothing

Well, now we know exactly how we’ve been able to pull off some of the technical wizardry we’ve achieved in earlier days: we’re a literal wizard! Or, at the very least, we are capable of conducting actual magic through the use of an arbitrarily large number of small implements. Basically a wizard. Spell components, amirite? Today’s puzzle instructs us to turn 0 jolts (presumably a measure of electrical output) into a lot of jolts by using our numerous adapters from our bag of holding (see Day 7). Part one is almost just sorting a list, with a twist!

# Yes, I used two test inputs this time. It came in handy later.
test_input1 <- c(
  "16", "10", "15",  "5",  "1", "11",  
   "7", "19",  "6", "12",  "4"
)

test_input2 <- c(
  "28", "33", "18", "42", "31", "14",
  "46", "20", "48", "47", "24", "23",
  "49", "45", "19", "38", "39", "11",
   "1", "32", "25", "35",  "8", "17",
   "7",  "9",  "4",  "2", "34", "10",
   "3"
)

real_input <- readLines('input.txt')

# Main function, given a numeric vector returns a numeric vector representing
# the differences between each element from the input vector, in order.
get_diff_counts <- function(vec) {
  differences <- sorted_input[-1] - sorted_input[-length(vec)]
  table(differences)
}

input_as_num <- as.numeric(real_input)

# Sort the inputs and add the 0 for the outlet and the +3 for our device to
# either end.
sorted_input <- c(0, sort(input_as_num), max(input_as_num) + 3)
diff_counts <- get_diff_counts(sorted_input)

answer <- diff_counts['1'] * diff_counts['3']  # Number of 1's times number of 3's

Ah, this is going to be an easy day. Right?

Part Two - What Just Happened?

library(purrr)  # For `map_dbl()`

# Helper function, given a number (or numeric vector containing only the values)
# 1, 2, 3, or 4, returns the number of ways a list of 1's `n` long can be combined 
# to give no single value greater than three. As I found out later, this is 
# the *tribonacci* sequence.
run_length_to_combo <- function(n) {
   replacements <- c('1' = 1, '2' = 2, '3' = 4, '4' = 7)
   
   # Function yells at you if you try to get the number of combinations
   # for a run length greater than 4
   unimplemented <- unique(n[!(n %in% names(replacements))])
   if (length(unimplemented) > 0) {
      stop(paste0(
         'No combinations implemented for [',
         paste(unimplemented, sep = ', '), ' ].'
      ))
   }
   
   # Just swaps out the 
   map_dbl(n, ~ replacements[as.character(.x)])
}

# Main function, given a sorted numeric vector, returns the number of possible
# combinations that can be achieved by removing numbers from that vector while
# ensuring that the difference between any two numbers in sequence is always
# 3 or less, consistent with the puzzle rules.
get_possible_combinations <- function(vec) {
   differences <- vec[-1] - vec[-length(vec)]
   
   # rle = Run Length Encoding, check the docs, it's great
   rl <- rle(differences)  
   
   one_run_lengths <- rl$lengths[rl$values == 1]  # I only care about runs of 1's
   
   # Get the # of combinations for each individual run, then multiply them all
   # together
   ind_run_combos <- run_length_to_combo(one_run_lengths)
   prod(ind_run_combos)
}

input_as_num <- as.numeric(real_input)
sorted_input <- c(0, sort(input_as_num), max(input_as_num) + 3)
possible_combinations <- get_possible_combinations(sorted_input)
answer <- as.character(possible_combinations)

Simple, right? I mean, from a “how does this code work” perspective, it kind of is. From a “how on earth do I figure out this puzzle?” perspective, it definitely wasn’t, at least not for me. I could tell from the beginning that there was going to be math involved, but what I couldn’t guess at was how bad I’d be at it. So, here’s the logic involved:

1. From part one, we calculated the differences between each number in the sequence. Comparing this list of differences to the example for making combinations of the test data, you’ll notice that the places where you are able to remove numbers and maintain a difference of 3 or less are sequences of 1’s.
2. For the given input, there are only differences of 1 or 3, and the ‘runs’ of 1’s appear in groups of 1, 2, 3, or 4.
3. Each ‘run’ represents a consistent number of ways it can be permuted, yielding a consistent number of additional combinations per run. Multiplying the number of combinations from each run together, across the entire vector.

How many combinations does each run provide? Well…

run length:         1 | 2    | 3       | 4
                      |      |         |
combinations:       1 | 1, 1 | 1, 1, 1 | 1, 1, 1, 1
                      | 2    | 2, 1    | 2, 1, 1
                      |      | 1, 2    | 1, 2, 1
                      |      | 3       | 1, 1, 2
                      |      |         | 3, 1
                      |      |         | 1, 3
                      |      |         | 2, 2
                      |      |         |
total combinations: 1 | 2    | 4       | 7

After a bit of research, I found that you can extend this sequence of numbers, and that it in fact is the tribonacci sequence, closely related to the more famous sequence of integers. Since we have no combinations of more than 4, the above mapping provides us all the information we need.

Armed with that knowledge, the necessary code became a lot clearer. Now, it’s just a matter of counting the number of runs of 1 by length (1-4), multiplying each identified run length by it’s associated number of combinations contributed to the total, then multiple all the intermediate products. Whew!

Wrap-Up

Don’t get me wrong, I like math. I really do. Not as much as an actual mathematician, mind you, but I don’t mind a bit of statistics or probability or arithmetic. However, when I wake up with the sun and crack open my laptop to see what fresh delight Advent of Code has brought me… I was not prepared for this one. At the end, though, I learned a lot and managed to clean up my initial code a lot to produce this final version, which I am quite pleased with.

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