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 15 - Rambunctious Recitation

Find the problem description HERE.

Part One - Reindeer Elf Games

For part one, we have elves playing a memory game. Given a list of numbers, the elves say each number in turn. When they reach the end of the list, they begin saying the number of rounds it has been since the number spoken on the previous turn had been spoken prior to the previous turn. So, for the list 0, 3, 6, you get [0, 3, 6], 0, 3, 1, 0, 4, 0 for the first 9 turns. The real question is: What will the number spoken on turn 2020 be?

I’ll be honest, the implementation below isn’t my first crack at this one, but, for reasons that will become clear later (or sooner if you’re starting to get an idea of how these puzzles are structured), it was the fastest implementation I could come up with in R.

library(testthat)  # For tests

# Given a starting sequence `start_vec` and a number `n`, returns the `n`th 
# number of the elve's counting game, according to the rules in the puzzle
# instructions. Note, the `rounds` vector below contains, at each index, the
# last round (prior to the most recent round) that the number (index - 1) was
# spoken. This is because R is 1-indexed, so the value for '0' is stored in
# index '1' and so on.
number_spoken <- function(start_vec, n) {
  rounds <- numeric(0)                 # Empty vector for the round a number was last spoken
  start_len <- length(start_vec)       # Length of the `start_vec`
  last_number <- start_vec[start_len]  # Last number spoken, starting value
  
  # Fill in the starting numbers into `rounds`
  for (i in 1:start_len) { rounds[[start_vec[i]+1]] <- i }
  
  # For each number after the starting veector...
  for (i in (start_len+1):n) {
    index <- last_number + 1  # Correction for 1-indexing
    
    # If the `index` either contains the number of the last round or an NA, 
    # then the last round was the first time `last_number` was spoken and the
    # `next_number` should be '0'. Otherwise, the `next_number` should be the
    # number of the last round (i-1) minus the number of the previous round
    # in which the number was spoken (rounds[last_number+1])
    next_number <- if (is.na(rounds[index]) || rounds[index] == i - 1) {
      0
    } else {
      (i - 1) - rounds[last_number+1]
    }
    
    rounds[last_number+1] <- i - 1  # Update the round number stored for this number
    last_number <- next_number      # The new `last_number` is this `next_number`
    
    # Sanity Check
    if (i %% 10000 == 0) { cat('\r', paste('Simulating round:', i)) }
  }
  
  next_number  # Return the `n`th number spoken
}

test_that("sample inputs return expected results", {
  expect_equal(number_spoken(c(0, 3, 6), 2020), 436)
  expect_equal(number_spoken(c(1, 3, 2), 2020), 1)
  expect_equal(number_spoken(c(1, 2, 3), 2020), 27)
  expect_equal(number_spoken(c(2, 3, 1), 2020), 78)
  expect_equal(number_spoken(c(3, 2, 1), 2020), 438)
  expect_equal(number_spoken(c(3, 1, 2), 2020), 1836)
})

answer1 <- number_spoken(c(2, 0, 1, 7, 4, 14, 18), 2020)

# Answer: 496

For reasons that I can’t recall, I was inspired to use testing for this puzzle. I think it had something to do with the number of test inputs we were given, since the testthat package and functions give me an easy way to test them all at once. I could also make tweaks to my implementation while being sure I didn’t miss any known edge cases.

Part Two - MORE!

source('exercise_1.R')

# Yep, that's it.
answer2 <- number_spoken(c( 2, 0, 1, 7, 4, 14, 18), 30000000)

This is why the speed of the implementation mattered.

Wrap-Up

Ah, there are some days when I’m jealous of the folks using compiled languages, but then I realize that my day job makes MUCH better use of shiny dashboards and data analysis with tidyverse than it does blazing fast array lookups, and I snap out of it. That said, this was an excellent opportunity to learn some things about doing things quickly in R (which is something I hadn’t spent much time on up to now). My brief takeaway is: getting a value from a known index in a vector, even if the vector contains a lot of NA’s , is pretty snappy. It’s definitely faster than looking up values by key in an environment, and it’s way faster than using a named list as a sort of pseudo-dictionary. Overall, a good day!

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