AoC 2024 Day 04: Ceres Search

An elf from the Ceres monitoring station needs help finding XMAS… or is it X-MAS? 🤔

Before diving in, have a read of the Day 04 story.

Input Data #

The input data is a grid of characters. Here’s an example:

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

Part 1 #

The goal is to find the number of occurrences of the string XMAS in the input data. Occurrences can be horizontal, vertical, diagonal, backwards, and can overlap with each other.

Our approach will be to iterate over each character in the grid, check if it matches the first character in XMAS. If it does, we then look in all neighbours of that location for the next character in XMAS. If we find it, we continue to the next character in XMAS. If we don’t find it, we break out of the loop and move on to the next character in the grid.

We’ll load the input data into a List<String> using the readInput function from Day 01 and pass it to the following part1 function.

Each string in the list represents a row in the grid.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

fun part1(input: List<String>): Int {
    val directions = listOf(
        0 to 1,    // Right
        1 to 0,    // Down
        0 to -1,   // Left
        -1 to 0,   // Up
        1 to 1,    // Down-right
        1 to -1,   // Down-left
        -1 to 1,   // Up-right
        -1 to -1   // Up-left
    )

    val search = "XMAS"

    return input.indices.sumOf { row ->
        input[0].indices.sumOf { col ->
            directions.count { (dx, dy) ->
                search.indices.all { i ->
                    val (nx, ny) = row + i * dx to col + i * dy
                    nx in input.indices &&
                            ny in input[nx].indices &&
                            input[nx][ny] == search[i]
                }
            }
        }
    }
}

On line 2, we define the list of possible directions to search in from any point on the grid.

Lines 15-16 iterates over every cell in the grid.

Line 17 iterates over every direction in the list of directions. The count function takes a predicate function that returns true if the condition is met. In this case, we’re checking if the next character in XMAS is found in the grid in the direction specified by dx and dy. We use the all function to check if all the characters in XMAS are found in the grid in the direction specified by dx and dy.

The sumOf functions then sum up the number of counts.

Part 2 #

Things get a little more complicated for typically strange AoC reasons. We’re now asked to find the number of pairs of occurences of the string MAS that form an X!

There are four possible combinations of MAS that form an X:

S.S    S.M    M.M    M.S
.A.    .A.    .A.    .A.
M.M    S.M    S.S    M.S

Our approach will be to find each A in the grid and then check the diagonal neighbours to see of they match one of the possible four combinations.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

fun part2(input: List<String>): Int {
    // Order in each String: Northwest, Northeast, Southeast, Southwest
    val patterns = listOf("SSMM", "SMMS", "MMSS", "MSSM")

    return (1 until input.size - 1).sumOf { row ->
        (1 until input[0].length - 1).count { col ->
            input[row][col] == 'A' &&
                    listOf(
                        input[row - 1][col - 1], // Northwest
                        input[row - 1][col + 1], // Northeast
                        input[row + 1][col + 1], // Southeast
                        input[row + 1][col - 1]  // Southwest
                    ).joinToString("") in patterns
        }
    }
}

Lines 5-6 iterate over every cell in the grid, skipping the first and last rows and columns because As at the edges can’t form an X, and the sumOf and count functions work together to return the number of cells that match the conditions in the lambda in lines 7-13.

The lambda checks if the current cell is an A and if the diagonal neighbours match one of the four possible patterns.

That’s it! The full source code is up on GitHub.