Day 10

Advent of Code: Worked Solutions

Setup

# Libraries
library(tidyverse)

# Read input from file
input <- read_lines("../input/day10.txt", skip_empty_rows = TRUE)

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

Part 1

Define custom functions:

# North / South / East / West
dirs <- list(c(0,  1), c(0, -1), c(1,  0), c(-1,  0))

# Check if a coordinate is in the bounds of the map
in_bounds <- function(x, map) {
  between(x[1], 1, nrow(map)) & between(x[2], 1, ncol(map))
}

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))
}

score_trail <- function(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()

[1] 531

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 the puzzle input:

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

[1] 1210