Day 6

Advent of Code: Worked Solutions

Setup

# Libraries
library(tidyverse)

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

Part 1

# Guard functions --------------------------------------------------------------
guards <- c("^", ">", "v", "<")
guard_shift <- c(tail(guards, -1), head(guards, 1))

rotate_guard <- function(cur) guard_shift[guards == cur]

guard_dir <- function(char) {
  case_match(char,
    "^" ~ matrix(c(-1,  0), nrow = 1),
    ">" ~ matrix(c( 0,  1), nrow = 1),
    "v" ~ matrix(c( 1,  0), nrow = 1),
    "<" ~ matrix(c( 0, -1), nrow = 1)
  )
}

in_bounds <- function(coord, mtx) {
  between(coord[1], 1, nrow(mtx)) & between(coord[2], 1, ncol(mtx))
}

map_path <- function(mtx) {

  # Initiate guard's starting position and direction
  cur_char  <- keep(mtx, ~ .x %in% guards)
  cur_coord <- which(mtx == cur_char, arr.ind = TRUE)
  cur_dir   <- guard_dir(cur_char)
  
  # As long as the guard is in bounds, iteratively update its coords and direction
  repeat {
    next_coord <- cur_coord + cur_dir
    
    # If next step is out-of-bounds, update matrix and exit
    if (!in_bounds(next_coord, mtx)) {
      mtx[cur_coord] <- "X"
      break
    }
    # If next step is an obstacle, rotate the guard
    else if (mtx[next_coord] == '#') {
      cur_char <- rotate_guard(cur_char)
      cur_dir  <- guard_dir(cur_char)
    }
    # Otherwise advance the guard forward
    else {
      mtx[cur_coord] <- "X"
      cur_coord <- next_coord
    }
  }
  
  mtx
}

# Convert input into a matrix
mtx <- input |> 
  str_split("") |> 
  unlist() |> 
  matrix(nrow = length(input), byrow = TRUE)

# Map the guard's path
guard_path <- map_path(mtx)

# Count distinct positions visited
sum(guard_path == "X")

Part 2

Change the path mapping function to test for loops

path_loops <- function(mtx) {

  # Initiate guard's starting position and direction
  cur_char  <- keep(mtx, ~ .x %in% guards)
  cur_coord <- which(mtx == cur_char, arr.ind = TRUE)
  cur_dir   <- guard_dir(cur_char)
  path_hist <- matrix("", nrow(mtx), ncol(mtx))

  # As long as the guard is in bounds, iteratively update its coords and direction
  repeat {
    next_coord <- cur_coord + cur_dir
    
    # Check if the guard is looping or if they have left the area
    if (str_detect(path_hist[cur_coord], fixed(cur_char))) 
      return(TRUE)
    else if (!in_bounds(next_coord, mtx)) 
      return(FALSE)
    
    # If next step is an obstacle, rotate the guard
    else if (mtx[next_coord] == '#') {
      # Update path history
      path_hist[cur_coord] <- str_c(path_hist[cur_coord], cur_char)
      # Update guard
      cur_char <- rotate_guard(cur_char)
      cur_dir  <- guard_dir(cur_char)
    }
    # Otherwise advance the guard forward
    else {
      # Update path history
      path_hist[cur_coord] <- str_c(path_hist[cur_coord], cur_char)
      # Update guard
      cur_coord <- next_coord
    }
  }
}

# Create a variation of the map for each possible obstacle location
obstacles <- which(guard_path == "X" & !(mtx %in% guards))

# Test each obstacle location for loops and sum result
obstacles |> 
  map(~ replace(mtx, .x, "#")) |> 
  map_lgl(path_loops) |> 
  sum()