06: Guard Gallivant

library(mistlecode)

options(scipen = 999)

mat <- 
  'input.txt' |>
  mistlecode::read_matrix()

Part 1

This wasn’t too bad. I’d been working on the adjacency function earlier trying to figure out an A* method for older puzzles. Just had to trim some fat and it was good enough. For some reason I struggled with getting the break to happen. Initially I just relied on the mat[y,x] reference to fail and that’s how I submitted, but it’s not a good look so I fixed it.

adjacent <- function(point) {
  y <- point[1]; x <- point[2];
  list(
    'up' = c(y-1,x),
    'down' = c(y+1,x),
    'left' = c(y,x-1),
    'right' = c(y,x+1)
  )
}

guy <- which(mat == '^', arr.ind = TRUE)[1,] |> unname()
rotate <- c('up' = 'right', 'right' = 'down', 'down' = 'left', 'left' = 'up')

dir <- 'up'
step <- 0
visited <- matrix(FALSE, nrow(mat), ncol(mat))
repeat {
  visited[guy[1], guy[2]] <- TRUE
  n <- adjacent(guy)[[dir]]
  if (!dplyr::between(n[1], 1, nrow(mat)) | !dplyr::between(n[2], 1, ncol(mat))) break
  if (mat[n[1], n[2]] != '#') guy <- n else dir <- rotate[dir]
  step <- step + 1
}
sum(visited)

[1] 4696

Part 2

It’s never a good sign when you resort to future… But also, I figured a path can’t cross itself more than five times without being in a loop. Before figuring that out, my estimated run time on a single core was 6-8 hours.

The next day…I realized the magic number is four since that’s the number of unique directions you can approach a node from.

tictoc::tic()
start <- which(mat == '^', arr.ind = TRUE)[1,] |> unname()
future::plan(future::multisession, workers = future::availableCores())
progressr::with_progress({
  df <-
    visited |> 
    mistlecode::matrix_to_coords() |> 
    dplyr::filter(.data$data) |>
    dplyr::select(-'data')
  p <- progressr::progressor(steps = nrow(df))
  df |>
  furrr::future_pmap_lgl(\(row, col) {
    p()
    cells <- matrix(0, nrow(mat), ncol(mat))
    dmat <- mat; dmat[row,col] <- '#';
    guy <- start; dir <- 'up'; step <- 0;
    repeat {
      n <- adjacent(guy)[[dir]]
      if (n[1] < 1 || n[1] > nrow(dmat) || n[2] < 1 || n[2] > ncol(dmat)) return(FALSE)
      if (dmat[n[1], n[2]] != '#') {
        cells[n[1], n[2]] <- cells[n[1], n[2]] + 1
        guy <- n
      } else dir <- rotate[dir]
      step <- step + 1
      if (any(cells > 4)) return(TRUE)
    }
  }) |>
  sum()
}, handlers = progressr::handler_cli())

[1] 1443

future::plan(future::sequential())
tictoc::toc()

167.415 sec elapsed