Advent of Code 2024: Day 04

Code for solutions available on GitHub.

Ceres Search

Ah, it’s time for the 2D array manipulation/searching task. And this time it’s a word search. We have to count the number of times the word “XMAS” appears in a grid like this:

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

The word can be horizontal, vertical, or diagonal. It can also be backwards or forwards. In the example above, “XMAS” occurs 18 times.

There are many ways to do this. I spent a lot of time trying to be clever with the ndarray crate. But in the end I went for the dead simple approach. Vec<Vec<u8>>. Not char, because it’s slightly easier to compare against b"XMAS" than ['X', 'M', 'A', 'S'] and because the input is all ASCII anyway.

let grid = input
    .lines()
    .map(|l| l.bytes().collect_vec())
    .collect_vec();

Now looking for “XMAS” horizontally (both forwards and backwards) is pretty simple. Once again, .windows() comes to the rescue!

let horizontal = grid
    .iter()
    .fold(0, |acc, row| {
        acc + row.as_slice().windows(4).fold(0, |acc, window| {
            if window == b"XMAS" || window == b"SAMX" {
                acc + 1
            } else {
                acc
            }
        });
    });

This works because the rows are contiguous in memory, so windowing through the inner slices just directly gives the answer.

But what about vertically? The columns are not contiguous in memory after all. I chose the easy way out here as well. I transposed the grid into a new nested Vec and used the same code I wrote for the rows to find “XMAS” in the columns. More allocated memory for less thinking.

And diagonals? Well for that there’s not much more to it other than just checking everything (this is where I wanted ndarray to help me, but it’s too late in the evening). By .window()-ing through the rows and iterating through the columns (taking care not to exceed the bounds of the grid), you can gather the two diagonals of each 4x4 sub-grid and check if they are “XMAS” or “SAMX”.

The code is pretty simple, albeit a bit longer than for horizontals and verticals:

let diagonal = grid.as_slice().windows(4).fold(0, |acc, window| {
        let mut diags = 0;
        for i in 0..window[0].len() - 3 {
            let d1 = [
                window[0][i],
                window[1][i + 1],
                window[2][i + 2],
                window[3][i + 3],
            ];
            let d2 = [
                window[3][i],
                window[2][i + 1],
                window[1][i + 2],
                window[0][i + 3],
            ];
            if &d1 == b"XMAS" || &d1 == b"SAMX" {
                diags += 1;
            }
            if &d2 == b"XMAS" || &d2 == b"SAMX" {
                diags += 1;
            }
        }

        acc + diags
    });

Part 2

Oh no, it wasn’t an “XMAS” word search. It was an “X-MAS” word search. What? Well, simply put we are supposed to count the occurences where the string “MAS” occurs twice in the shape of an X. Like this:

M.S
.A.
M.S

Again, both backwards and forwards on both diagonals.

This is actually simpler than part 2. One way to do it – which could also have been employed in part 1 but oh well – is to first find all the positions of the letter ‘A’, since that’s the center of any MAS-X. Given the same grid as above:

let mut a_indices = Vec::new();

for (i, row) in grid.iter().enumerate() {
    for (j, c) in row.iter().enumerate() {
        if *c == b'A' {
            a_indices.push((i, j));
        }
    }
}

We can then iterate through all indices for the letter ‘A’, check that both diagonals contain both an ‘M’ and an ‘S’ in either order. But taking care not to exceed the bounds of the grid by skipping any ‘A’ that is on the edge of the grid.

let mas = a_indices.into_iter().fold(0, |acc, (i, j)| {
    // Skip 'A's on the edge of the grid
    if !(1..grid.len() - 1).contains(&i) || !(1..grid[0].len() - 1).contains(&j) {
        return acc;
    }

    let d1 = [grid[i - 1][j - 1], grid[i + 1][j + 1]];
    let d2 = [grid[i + 1][j - 1], grid[i - 1][j + 1]];

    if (&d1 == b"SM" || &d1 == b"MS") && (&d2 == b"SM" || &d2 == b"MS") {
        acc + 1
    } else {
        acc
    }
});

And we’re done :)