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 3 - Toboggan Trajectory

Find the problem description HERE.

Part One - Slippery Slope

This problem looks like a lot of fun! Essentially, given a 2-dimensional array of characters (where . represents empty space and # represents a tree), a starting location, and directions for traversing the map, we need to count how many trees we land on while traveling down the map. The extra ’twist’ is that we’re only given the left-most portion of a horizontally-repeating map. No sweat! In fact, this is the perfect excuse to make use of R matrices.

# Helper function, converts a character map to a matrix, where each character
# is held in a corresponding matrix index
trees_map <- function(pattern) {
  pattern_no_whitespace <- str_remove_all(pattern, '[ \\t]')
  lines <- str_split(pattern_no_whitespace, '\n', simplify = T)
  line_vecs <- str_split(lines, '')
  mmap <- reduce(line_vecs, rbind)
  row.names(mmap) <- seq(nrow(mmap))

  mmap
}

# The main function, traverses the map and counts the number of trees 
# encountered given a matrix of `.`s and `#`s (tmap) and a vector containing
# the number of rows to move down and the number of columns to move right with
# each iteration (slope)
trees_encountered <- function(tmap, slope) {
  cursor <- c(row = 1, col = 1)
  trees <- list()
  map_h <- nrow(tmap)  # Initial matrix dimensions
  map_w <- ncol(tmap)  # Initial matrix dimensions

  while(cursor['row'] <= nrow(tmap)) {
    # If the cursor is on the right edge of the map, extend the map by
    # adding a copy of the original to the right
    if (cursor['col'] > ncol(tmap)) {
      tmap <- cbind(tmap, tmap[1:map_h, 1:map_w])
    }

    # If the cursor is on a tree, add the tree to the list
    if (tmap[cursor['row'], cursor['col']] == '#') {
      trees[[length(trees) + 1]] <- cursor
    }

    # Move the cursor according to the current slope
    cursor <- cursor + slope
  }

  trees  # Return a list coordinates for trees encountered (row, col)
}

tmap <- trees_map(input)
found_trees <- trees_encountered(tmap, c(1, 3)) # The test slope
answer = length(found_trees)

Now, you may be thinking: “Wouldn’t it be more efficient to just wrap the cursor horizontally when it reaches the right-hand side of the matrix?” The answer is: yeah, sure, whatever, but then I couldn’t have made this sweet animation!

This shows the algorithm traversing the test map with the slope of c(1, 3). Remember, matrix coordinates are in the format of [row, column], which is the reverse of the (arguably more intuitive) cartesian format of [x, y] or [column, row].

Part Two - Sisyphean Sleigh

I guess the journey was the important part, not the destination, since the second part of the problem has us conceptually climbing back up the hill and sliding back down again following different slopes, multiplying the number of trees from each trip together to find the answer. Unfortunately, we’ve already figured out how to traverse the slope in a fairly generic way, so the solution to this part is just to use our functions again.

# All the slopes we need to traverse
slopes <- list(c(1, 1), c(1, 3), c(1, 5), c(1, 7), c(2, 1))

# Traverse each slope and identify the trees
all_trees <- sapply(slopes, trees_encountered, tmap = trees_map(input))
answer <- prod(lengths(all_trees)) 

I say ‘unfortunately’, but this is one of those places that R really shines by simplifying the task of repeated operations on larger data sets.

Wrap-Up

Day 3 almost felt unfair to implement in R, with it’s native 2-dimensional data structures and functions that make it easy to apply a function over and over again (I’m looking at you, apply family). On the other hand, I don’t get to use matrices much in everyday work, so having an excuse to practice the ins and outs of matrix math and indexing probably counts as eating my vegetables, intellectually speaking. If you found a different solution (or spotted a mistake in one of mine), please drop me a line!