Day 4: Ceres Search

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

Read in the problem:

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

Here’s the left corner:

lets[1:10, 1:10]

      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
 [1,] "S"  "A"  "M"  "M"  "S"  "M"  "S"  "X"  "M"  "M"  
 [2,] "M"  "A"  "S"  "A"  "A"  "A"  "M"  "A"  "M"  "M"  
 [3,] "S"  "A"  "M"  "X"  "S"  "M"  "S"  "M"  "M"  "M"  
 [4,] "M"  "A"  "S"  "A"  "X"  "A"  "A"  "A"  "S"  "X"  
 [5,] "S"  "X"  "M"  "A"  "S"  "M"  "S"  "M"  "S"  "A"  
 [6,] "S"  "X"  "M"  "A"  "M"  "A"  "X"  "A"  "M"  "M"  
 [7,] "M"  "A"  "X"  "S"  "X"  "X"  "M"  "A"  "M"  "X"  
 [8,] "S"  "S"  "M"  "M"  "A"  "M"  "S"  "A"  "M"  "X"  
 [9,] "X"  "M"  "A"  "M"  "A"  "M"  "S"  "A"  "S"  "X"  
[10,] "X"  "S"  "M"  "M"  "A"  "X"  "S"  "A"  "M"  "X"  

nrow(lets)

[1] 140

ncol(lets)

[1] 140

I don’t want to worry about walking off the edge of the matrix; this means I don’t have to:

val <- function(mat, r, c) {
  if (between(r, 1, nrow(mat)) &&
      between(c, 1, ncol(mat)))
    mat[r, c]
  else
    NA
}

Part 1

Turn a vector, potentially with missingness (assuming it’s at the ends), into a string with NAs removed:

stringify <- function(vec) {
  vec |> na.omit() |> paste(collapse = "")
}

Walk along the matrix, mat, starting at the start and stepping the steps, e.g., using a negative step to move backwards.

walk <- function(mat, start_r, start_c, r_step, c_step, n) {
  res <- rep(NA, n)

  r <- start_r
  c <- start_c
  i <- 1
  
  while (i <= n) {
    res[i] <- mat |> val(r, c)
    r <- r + r_step
    c <- c + c_step
    i <- i + 1
  }
  
  stringify(res)
}

For example, east:

lets |> walk(1, 1, 1, 1, 4)

[1] "SAMA"

South west:

lets |> walk(1, 4, 1, -1, 4)

[1] "MSAM"

All the directions we want to wander:

directions <- expand.grid(r_step = c(-1, 0, 1),
                          c_step = c(-1, 0, 1)) |>
  filter(r_step != 0 | c_step != 0)
directions

Scan in all directions from point (r,c):

scan_point <- function(mat, r, c, n) {
  map2_chr(directions$r_step,
           directions$c_step,
           \(r_step, c_step) walk(mat, r, c, r_step, c_step, n))
}

everywhere <- expand.grid(r = 1:nrow(lets),
                          c = 1:ncol(lets))

tic()
all_of_em <- map2(everywhere$r,
                  everywhere$c,
                  \(r, c) scan_point(lets, r, c, 4))
toc()

45.55 sec elapsed

That was very slow, maybe because I saved 156800 strings, whereas I could just have counted matches.

The answer:

map_int(all_of_em, \(xs) sum(xs == "XMAS")) |> sum()

[1] 2547

Part 2

Sweep across, walking three steps southeast and southwest. Count how often we get “MAS” or “SAM” on those.

target <- c("MAS", "SAM")

is_cross_mas <- function(mat, r, c) {
  text_SE <- walk(mat, r - 1, c - 1, 1, 1, 3)
  text_SW <- walk(mat, r - 1, c + 1, 1, -1, 3)
  
  (text_SE %in% target) && (text_SW %in% target)
}

I could strip off the outer border where there can’t be a match; however, val defined at the top means I don’t have to.

tic()
cross_count <- map2_lgl(
                everywhere$r,
                everywhere$c,
                \(r, c) is_cross_mas(lets, r, c)
               )
toc()

8.64 sec elapsed

The answer:

sum(cross_count)

[1] 1939