Advent of Code 2024 - day 4 – nickopotamus.co.uk

I’m finally catching up on this year’s advent of code and I’m posting my solutions in R on my Github.

A quick google reveals that there are far more elegant solutions in R out there, and there are moderately active communities on Reddit and Bluesky trying to do the same as me, but I find it a fun little exercise that helps me realise quite how bad at thinking like a computer scientist I really am.

Anyway day 4 had me stumped for a little while, so I thought I’d walk you through my (terribly inefficient) solution in case you were stuck too.

Let’s start by loading the packages we need - tidyverse because everything else seems to be base R, and cookiemonster and httr2 to download the data from the AoC site.

library(tidyverse)     
library(cookiemonster)
library(httr2)

Part 1 is relatively straightforward - build a word-search solver. We’re given an example word search, the word we’re looking for (“XMAS”, obviously), and a link to our own personal dataset:

# Word to search for
word <- "XMAS"

# Example
test_search <- matrix(
  c(
    "M", "M", "M", "S", "X", "X", "M", "A", "S", "M",
    "M", "S", "A", "M", "X", "M", "S", "M", "S", "A",
    "A", "M", "X", "S", "X", "M", "A", "A", "M", "M",
    "M", "S", "A", "M", "A", "S", "M", "S", "M", "X",
    "X", "M", "A", "S", "A", "M", "X", "A", "M", "M",
    "X", "X", "A", "M", "M", "X", "X", "A", "M", "A",
    "S", "M", "S", "M", "S", "A", "S", "X", "S", "S",
    "S", "A", "X", "A", "M", "A", "S", "A", "A", "A",
    "M", "A", "M", "M", "M", "X", "M", "M", "M", "M",
    "M", "X", "M", "X", "A", "X", "M", "A", "S", "X"
  ),
  byrow = TRUE,
  nrow = 10
)

# Get input data
input <- request("https://adventofcode.com/2024/day/4/input") %>% 
  req_options(cookie = get_cookies("adventofcode.com", as = "string")) %>% 
  req_perform() %>% 
  resp_body_string() %>%
  str_trim() %>%      # Remove trailing whitespace
  str_split("\n") %>% # Split input into lines
  unlist() %>%
  str_split("") %>%   # Split each line into individual characters
  do.call(rbind, .)

My first attempt at this tried to extract strings, but I struggled to sensibly code diagonal string extraction. Instead I wrote a function to systematically search the grid, and if it finds the first letter in word (in our case, “X”) look in all possible directions for the next letter (“M”). If that is TRUE, keep going in the same direction and look for the next (“A”) until all the letters (up to a total of nchar(word)) are found.

count_word_occurrences <- function(grid, word) {
  
  # Initialise
  word_length <- nchar(word) # Search word
  rows <- nrow(grid)         # Grid dimensions
  cols <- ncol(grid)
  total_count <- 0           # Number of solutions found
  
  # Define all possible directions
  directions <- list(
    c(0, 1),    # Right
    c(0, -1),   # Left
    c(1, 0),    # Down
    c(-1, 0),   # Up
    c(1, 1),    # Diagonal Down-Right
    c(-1, -1),  # Diagonal Up-Left
    c(1, -1),   # Diagonal Down-Left
    c(-1, 1)    # Diagonal Up-Right
  )
  
  # Helper function to check if a word exists in a given direction
  is_match <- function(x, y, dx, dy) {
    for (k in seq_len(word_length)) {
      new_x <- x + (k - 1) * dx
      new_y <- y + (k - 1) * dy
      
      # Check if out of bounds or character mismatch
      if (new_x < 1 || new_x > rows || new_y < 1 || new_y > cols || 
          grid[new_x, new_y] != substr(word, k, k)) {
        return(FALSE)
      }
    }
    return(TRUE)
  }
  
  # Loop over every cell in the grid
  for (i in seq_len(rows)) {
    for (j in seq_len(cols)) {
      
      # Check all directions from this cell
      for (dir in directions) {
        dx <- dir[1]
        dy <- dir[2]
        if (is_match(i, j, dx, dy)) {
          total_count <- total_count + 1
        }
      }
    }
  }
  
  return(total_count)
}

Lets run it:

test_occurrences <- count_word_occurrences(test_search, word)
cat("There are", test_occurrences, "XMASs in the example grid")

There are 18 XMASs in the example grid

total_occurrences <- count_word_occurrences(input, word)
cat("There are", total_occurrences, "XMASs in the final grid")

There are 2458 XMASs in the final grid

Part 2 was a bit more of a challenge. Here we’re trying to find the “X-MAS” patterns - i.e. any cross where the two diagonals are “MAS”. After much fannying around, I took a brute force approach:

Locate any “A” (as this is the only letter than can be the centre of an X-MAS)
Then check the top and bottom pairs - the only valid combinations are:

“M.S” and “M.S”
“S.M” and “S.M”
“S.S” and “M.M”
“M.M” and “S.S”

I added debugging to log the top_pair and bottom_pair with coordinates, mostly to work out why my attempts at the function kept only finding 3 of the 9 X-MASs in the example grid (the answer - I’d coded the symmetry logic wrong)

count_x_mas <- function(grid) {
  
  # Initialise grid
  rows <- nrow(grid)
  cols <- ncol(grid)
  total_count <- 0
  
  # Helper function to check if the "X-MAS" pattern exists
  is_x_mas <- function(i, j) {
    
    # Check if the pattern is within bounds
    if (i < 2 || i > rows - 1 || j < 2 || j > cols - 1) {
      message("Out of bounds at center: (", i, ", ", j, ")")
      return(FALSE)
    }
    
    # Extract positions of interest
    top_left <- grid[i - 1, j - 1]
    top_right <- grid[i - 1, j + 1]
    bottom_left <- grid[i + 1, j - 1]
    bottom_right <- grid[i + 1, j + 1]
    center <- grid[i, j]
    
    # Ensure the center is "A" (optional debugging statement)
    if (center != "A") {
      # message("Invalid center at: (", i, ", ", j, ") -> Center: ", center)
      return(FALSE)
    }
    
    # Form the top and bottom pairs
    top_pair <- paste0(top_left, ".", top_right)
    bottom_pair <- paste0(bottom_left, ".", bottom_right)
    
    # Valid combinations of top and bottom pairs (symmetry rules for the X-MAS)
    valid_combinations <- list(
      "M.S" = "M.S", 
      "S.M" = "S.M", 
      "S.S" = "M.M", 
      "M.M" = "S.S"
    )
    
    # Check if the combination is valid
    if (!is.null(valid_combinations[[top_pair]]) && valid_combinations[[top_pair]] == bottom_pair) {
      return(TRUE)
    }
    
    # Debugging: Log invalid pairs
    message(
      "Invalid at center: (", i, ", ", j, ") -> ",
      "Top: ", top_pair, ", Bottom: ", bottom_pair
    )
    return(FALSE)
  }
  
  # Iterate over the grid to find "X-MAS" patterns
  for (i in 2:(rows - 1)) {
    for (j in 2:(cols - 1)) {
      if (is_x_mas(i, j)) {
        total_count <- total_count + 1
        # Debugging: Log the position of each valid match
        message("X-MAS found at center: (", i, ", ", j, ")")
      }
    }
  }
  
  return(total_count)
}

Let’s run this on the example:

test_x_mas <- count_x_mas(test_search)

X-MAS found at center: (2, 3)

X-MAS found at center: (3, 7)

X-MAS found at center: (3, 8)

X-MAS found at center: (4, 3)

X-MAS found at center: (4, 5)

Invalid at center: (5, 3) -> Top: S.M, Bottom: X.M

Invalid at center: (5, 5) -> Top: M.S, Bottom: M.X

Invalid at center: (5, 8) -> Top: M.M, Bottom: X.M

Invalid at center: (6, 3) -> Top: M.S, Bottom: M.M

Invalid at center: (6, 8) -> Top: X.M, Bottom: S.S

Invalid at center: (7, 6) -> Top: M.X, Bottom: M.S

X-MAS found at center: (8, 2)

X-MAS found at center: (8, 4)

X-MAS found at center: (8, 6)

X-MAS found at center: (8, 8)

Invalid at center: (8, 9) -> Top: X.S, Bottom: M.M

Invalid at center: (9, 2) -> Top: S.X, Bottom: M.M

cat("There are", test_x_mas, "X-MASs in the example grid")

There are 9 X-MASs in the example grid

And finally our personal dataset:

total_x_mas <- count_x_mas(input)
cat("There are", total_x_mas, "X-MASs in the final grid")

There are 1945 X-MASs in the final grid

Onwards to day 5…