Day 10

Advent of Code: Worked Solutions

Setup

Import libraries:

library(tidyverse)

Read plaintext input from file:

input <- read_lines("../input/day10.txt")

Convert text input into a numeric matrix:

mtx <- input |> 
  str_split("") |>
  unlist() |> 
  as.integer() |> 
  matrix(nrow = length(input), byrow = TRUE)

Part 1

Define cardinal directions (N/S/E/W) as a list of 2D vectors:

dirs <- list(c(0, 1), c(0, -1), c(1, 0), c(-1, 0))

Define a helper function to determine if a coordinate is within the map bounds:

in_bounds <- \(x, map) between(x[1], 1, nrow(map)) & between(x[2], 1, ncol(map))

Define a function to find the trail ends given a map and a starting coordinate:

find_trail_ends <- function(cur_coord, map) {
  
  # If the trailhead has been reached, return its coordinate.
  if (map[cur_coord] == 9)
    return(list(cur_coord))
  
  # Define the possible next steps within the map bounds
  next_steps <- dirs |> 
    map(~ cur_coord + .x) |> 
    keep(~ in_bounds(.x, map))
  
  trail_ends <- list()
  
  # If the next step leads to a valid path, add its terminal to the list
  for (next_coord in next_steps) {
    if (map[next_coord] == map[cur_coord] + 1) 
      trail_ends <- c(trail_ends, find_trail_ends(next_coord, map))
  }
  
  return(unique(trail_ends))
}

Define a function to score a trail given the map and trailhead:

score_trail <- \(trailhead, map) length(find_trail_ends(trailhead, map))

Get a list of coordinates of all of the trailheads:

trailheads <- which(mtx == 0, arr.ind = TRUE)

trailheads_list <- map(
  1:nrow(trailheads), 
  ~ array(trailheads[.x,], dim = c(1, 2))
)

Score each trailhead and sum the total:

trailheads_list |> 
  map_int(~ score_trail(.x, mtx)) |> 
  sum()

Part 2

Modify the trail rating function:

rate_trail <- function(cur_coord, map) {
  # If the trailhead has been reached, increment the score and exit.
  if (map[cur_coord] == 9)
    return(1)
  
  # Define the possible next steps within the map bounds
  next_steps <- dirs |> 
    map(~ cur_coord + .x) |> 
    keep(~ in_bounds(.x, map))
  
  # Sum the trail ratings of all valid next steps
  map_int(
    next_steps,
    ~ if (map[.x] == map[cur_coord] + 1) rate_trail(.x, map) else 0
  ) |> 
    sum()
}

Re-run on the puzzle input:

trailheads_list |> 
  map_int(~ rate_trail(.x, mtx)) |> 
  sum()