Day 6

Advent of Code: Worked Solutions

Setup

Import libraries:

library(tidyverse)

Read text input from file:

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

Convert text input of the map into a 1/0 matrix (saving the guard’s initial location):

mtx <- input |> 
  str_split("") |> 
  unlist() |> 
  case_match("." ~ 0, "#" ~ 1, c("^", "v", "<", ">") ~ 2) |> 
  matrix(nrow = length(input), byrow = TRUE)

init <- as.vector(which(mtx == 2, arr.ind = TRUE))

mtx <- replace(mtx, mtx == 2, 0)

Part 1

Define a function that loops through guard positions until it leaves the map, returning a list of all positions where they turned:

maxdim <- c(1, ncol(mtx), nrow(mtx), 1)
mtxdir <- c(-1, 1, 1, -1)
mtxaxis <- c(1, 2, 1, 2)

guard_path <- function(mtx, init) {
  guard <- init
  hist <- list(guard)
  idx <- 1
  
  repeat {
    dir <- mtxdir[idx]
    dim <- maxdim[idx]
    axis <- mtxaxis[idx]
    
    if (axis == 1) {
      path <- mtx[(guard[1] + dir):dim, guard[2]]
    } else {
      path <- mtx[guard[1], (guard[2] + dir):dim]
    }
    
    # Quit if we reach the edge of the map without an obstacle
    if (all(path == 0)) {
      guard[axis] <- dim
      hist <- c(hist, list(guard))
      return(hist)
    }
    
    # Move the guard
    guard[axis] <- guard[axis] + dir * head(which(path == 1) - 1, 1)
    
    # If we've entered a loop (same position + same direction), exit early
    if (list(guard) %in% hist) {
      # (we can't compare nested lists directly, so must compare str vers)
      hist_str <- map_chr(hist, ~ str_flatten(.x, collapse = "|"))
      guard_str <- str_flatten(guard, collapse = "|")
      if (idx %in% ((which(guard_str == hist_str) - 2) %% 4 + 1))
        return()
    }
    
    # Update the guard's history and the indexing
    hist <- c(hist, list(guard))
    idx <- idx %% 4 + 1
  }
}

Get the guard’s path for the puzzle input, then count the number of unique positions visited by the guard:

path <- guard_path(mtx, init)

path_full <- map2(head(path, -1), tail(path, -1), \(source, target) {
  expand_grid(row = source[1]:target[1], col = source[2]:target[2])
}) |> 
  bind_rows() |> 
  distinct()

nrow(path_full)

Part 2

For each location in the full path (except the starting location), add an obstacle to the matrix. Check the result for loops:

path_full |>
  tail(-1) |>
  pmap_lgl(\(row, col) {
    mtx[row, col] <- 1
    is.null(guard_path(mtx, init))
  }) |> 
  sum()