Day 6: Guard Gallivant

library(tidyverse)
library(stringr)
library(tictoc)

Read in the problem:

dat <- read_lines("aoc06.txt")
mapmat <- str_split_fixed(dat, "", n = str_length(dat[1]))

Top left corner of the map:

mapmat[1:10, 1:10]

      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
 [1,] "."  "."  "."  "."  "."  "."  "."  "."  "."  "."  
 [2,] "."  "."  "."  "."  "."  "."  "#"  "."  "."  "."  
 [3,] "."  "."  "."  "#"  "."  "#"  "."  "."  "."  "."  
 [4,] "."  "."  "."  "."  "."  "."  "."  "."  "."  "."  
 [5,] "."  "."  "."  "."  "."  "."  "."  "."  "."  "."  
 [6,] "."  "."  "."  "."  "."  "."  "."  "."  "."  "."  
 [7,] "."  "."  "."  "."  "."  "."  "."  "."  "."  "."  
 [8,] "."  "."  "#"  "."  "."  "."  "."  "#"  "."  "."  
 [9,] "."  "."  "."  "."  "."  "."  "."  "."  "."  "."  
[10,] "."  "."  "."  "#"  "."  "."  "."  "#"  "#"  "."  

Part 1

Here are the moves:

moves <- read.csv(text = "now,then,row_step,col_step
N,E,-1,0
S,W,1,0
W,N,0,-1
E,S,0,1")
moves

A dirty loop:

work_map <- mapmat
cur_dir <- "N"
cur_pos <- which(work_map == "^", arr.ind = TRUE)
work_map[cur_pos] <- "X"

tic()
done <- FALSE
while (!done) {
  cur_move <- moves |>
    filter(now == cur_dir)
  
  new_pos <- matrix(c(NA, NA), nrow = 1, ncol = 2)
  new_pos[1] <- cur_pos[1] + cur_move$row_step
  new_pos[2] <- cur_pos[2] + cur_move$col_step
  
  if (!between(new_pos[1], 1, nrow(work_map)) ||
      !between(new_pos[2], 1, ncol(work_map))) {
    done <- TRUE  
  }
  else if (work_map[new_pos] %in% c(".", "X")) {
    work_map[new_pos] <- "X"
    cur_pos <- new_pos
  }
  else  {
    cur_dir <- cur_move$then
  }
}
toc()

3.86 sec elapsed

Two bugs that wasted some time:

1. Forgot that the guard can walk over their own path again.

2. Needed to check that the new position was still on the map, rather than only current position.

which(work_map == "X") |> length()

[1] 5129

Part 2

Originally ran out of time; just realised that I’d already worked out the search space with the X’s above:

start_pos <- which(mapmat == "^", arr.ind = TRUE)

I’m sure there’s a smaller space, but at least this is less than a day’s computations…

Remove the starting position:

potentials <- which(work_map == "X", arr.ind = TRUE) |>
  as.data.frame() |>
  filter(!(row == start_pos[1] & col == start_pos[2]))
nrow(potentials)

[1] 5128

Spot a loop by checking if we have passed the same location, pointing the same direction, twice.

has_loop <- function(the_map) {
  cur_dir <- "N"
  cur_pos <- which(the_map == "^", arr.ind = TRUE)
  blank_map <- matrix(0, nrow = nrow(the_map), ncol = ncol(the_map))
  been_here <- list(N = blank_map,
                    S = blank_map,
                    W = blank_map,
                    E = blank_map)
  
  done <- FALSE
  loopy <- FALSE
  while (!done) {
    been_here[[cur_dir]][cur_pos] <- been_here[[cur_dir]][cur_pos] + 1
    if (been_here[[cur_dir]][cur_pos] == 2) {
      loopy <- TRUE
      break
    }
    
    cur_move <- moves |>
      filter(now == cur_dir)
    
    new_pos <- matrix(c(NA, NA), nrow = 1, ncol = 2)
    new_pos[1] <- cur_pos[1] + cur_move$row_step
    new_pos[2] <- cur_pos[2] + cur_move$col_step
    
    if (!between(new_pos[1], 1, nrow(the_map)) ||
        !between(new_pos[2], 1, ncol(the_map))) {
      done <- TRUE
    }
    else if (the_map[new_pos] != "#") {
      cur_pos <- new_pos
    }
    else  {
      cur_dir <- cur_move$then
    }
  }
  
  loopy
}

Stick a block at (x,y) and check if there’s a loop.

block_loops <- function(the_map, x, y) {
  the_map[x, y] <- "#"
  has_loop(the_map)
}

Do it for all the locations we visited in Part 1.

tic()
res <- map2_lgl(potentials[,1],
                potentials[,2],
                \(x, y) block_loops(mapmat, x, y),
                .progress = TRUE)
toc()

First (and last) time run, it was 14440.11 sec.

sum(res)

[1] 1888