Task 4

2024-12-13

1 Setup

1.1 Libraries

library(httr)
library(xml2)
library(magrittr)
library(dplyr)
library(purrr)
library(stringr)
library(knitr)

1.2 Retrieve Data from `AoC`

session_cookie <- set_cookies(session = keyring::key_get("AoC-GitHub-Cookie"))
base_url <- paste0("https://adventofcode.com/2024/day/", params$task_nr)
puzzle <- GET(base_url,
              session_cookie) %>% 
  content(encoding = "UTF-8") %>% 
  xml_find_all("///article") %>% 
  lapply(as.character)

puzzle_data <- local({
  GET(paste0(base_url, "/input"),
      session_cookie) %>% 
    content(encoding = "UTF-8") %>% 
    str_split("\n") %>% 
    extract2(1L) %>% 
    head(-1L) %>% 
    str_split("") %>% 
    do.call(rbind, .)
})

2 Puzzle Day 4

2.1 Part 1

2.1.1 Description

— Day 4: Ceres Search —

“Looks like the Chief’s not here. Next!” One of The Historians pulls out a device and pushes the only button on it. After a brief flash, you recognize the interior of the Ceres monitoring station!

As the search for the Chief continues, a small Elf who lives on the station tugs on your shirt; she’d like to know if you could help her with her word search (your puzzle input). She only has to find one word: XMAS.

This word search allows words to be horizontal, vertical, diagonal, written backwards, or even overlapping other words. It’s a little unusual, though, as you don’t merely need to find one instance of XMAS - you need to find all of them. Here are a few ways XMAS might appear, where irrelevant characters have been replaced with .:

..X...
.SAMX.
.A..A.
XMAS.S
.X....

The actual word search will be full of letters instead. For example:

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

In this word search, XMAS occurs a total of 18 times; here’s the same word search again, but where letters not involved in any XMAS have been replaced with .:

....XXMAS.
.SAMXMS...
...S..A...
..A.A.MS.X
XMASAMX.MM
X.....XA.A
S.S.S.S.SS
.A.A.A.A.A
..M.M.M.MM
.X.X.XMASX

Take a look at the little Elf’s word search. How many times does XMAS appear?

2.1.2 Solution

First, we define a function that, from a given starting point extracts all 8 words:

get_word <- function(row, col, .data = puzzle_data, .length = 4L) {
  pos <- expand.grid(
    row_offset = -1:1,
    column_offset = -1:1
  ) %>% 
    as_tibble() %>% 
    filter(row_offset !=0 | column_offset != 0) %>% 
    pmap(function(row_offset, column_offset) {
      t(outer(c(row_offset, column_offset), seq(0, .length - 1L)) + c(row, col))
    })
  dd <- dim(.data)
  valid_pos <- pos %>% 
    discard(\(m) {
      any(m <= 0L | m[, 1] > dd[1L] | m[, 2L] > dd[2L])
    })
  valid_pos %>% 
    map_chr(\(idx) paste(c(.data[idx]), collapse = ""))
}

For instance, the 3 words from position (1 / 1) (to the left, down and down left, the other directions would be out of bounds) are XSMS, XMMX, and XAAX.

What is left is to get all positions starting with an X and get all the words from there. Then, we count how often we get the word XMAS:

xpos <- which(puzzle_data == "X", arr.ind = TRUE) %>% 
  as_tibble()

pmap(xpos, get_word) %>% 
  flatten() %>% 
  str_count(fixed("XMAS")) %>% 
  sum()

## [1] 2654

2.2 Part 2

2.2.1 Description

— Part Two —

The Elf looks quizzically at you. Did you misunderstand the assignment?

Looking for the instructions, you flip over the word search to find that this isn’t actually an XMAS puzzle; it’s an X-MAS puzzle in which you’re supposed to find two MAS in the shape of an X. One way to achieve that is like this:

M.S
.A.
M.S

Irrelevant characters have again been replaced with . in the above diagram. Within the X, each MAS can be written forwards or backwards.

Here’s the same example from before, but this time all of the X-MASes have been kept instead:

.M.S......
..A..MSMS.
.M.S.MAA..
..A.ASMSM.
.M.S.M....
..........
S.S.S.S.S.
.A.A.A.A..
M.M.M.M.M.
..........

In this example, an X-MAS appears 9 times.

Flip the word search from the instructions back over to the word search side and try again. How many times does an X-MAS appear?

2.2.2 Solution

We apply the same idea, first for each position we get the x-shaped words (note that the position is the middle point):

get_xword <- function(row, col, .data = puzzle_data) {
  idx <- rbind(
    c(-1, 0, 1, -1, 1),
    c(-1, 0, -1, 1, 1)
  ) + c(row, col)
  paste(c(.data[t(idx)]), collapse = "")
}

Each A is the middle point of a potential x-word (exclude As in first / last column row as they cannot be a middle point). For each of these positions check whether the x-word is any of the permutations of MAS (we pasted the letters top-left / middle / bottom-left / top-right / bottom-right), those are MAMSS, MASMS, SAMSM and SASMM.

apos <- which(puzzle_data == "A", arr.ind = TRUE) %>% 
  as_tibble() %>% 
  filter(between(row, 2, nrow(puzzle_data) - 1),
         between(col, 2, ncol(puzzle_data) - 1))

pmap(apos, get_xword) %>% 
  flatten() %>% 
  str_count("MAMSS|MASMS|SAMSM|SASMM") %>% 
  sum()

## [1] 1990