Day 4: Ceres Search

Author

Kasia Kedzierska

Published

December 4, 2024

Modified

December 5, 2024

Today, we’re searching the Ceres monitoring station and we’re helping adorable little Elf with their word search.

Do check out the full details of the task on the official Day 4 of Advent of Code 2024 website – the puzzles come with a cute story.

And as per tradition, let’s set the set the scene with ChatGPT illustration of the day.

Part 1: Searching for XMAS

The challenge is to find occurrences of the word XMAS in a given letter grid. The twist is that the word can appear in any direction: horizontally, vertically, or diagonally, and even in reverse order. This adds a layer of complexity as we must account for all possible orientations.

Here’s an example of a grid with all letters not spelling XMAS removed:

Our task is to count how many times XMAS appears in a provided grid, considering all the possible directions.

For example, in the grid below:

The word XMAS appears 7 times.

My approach

For this one, I want to solve it in a single pass through the grid. Here’s my plan:

I’ll go through each character in the grid.
If I encounter an X or an S, I’ll add it to a dictionary to track potential matches. For each match, I’ll:
- Note the directions to explore (right, diagonal left, diagonal right, and down).
- Keep track of whether I’m spelling the word forward or backward.
- Record the next letter I’m expecting to find.
For each position, I’ll check:
- If it’s already being tracked in the dictionary.
- If so, I’ll see if the letter matches what I’m expecting. If it does, I’ll update the dictionary with the next position to check.
By doing this, I ensure:
- Each position is only processed once.
- I avoid any redundant checks or unnecessary traversals.

This approach keeps things efficient and clean while letting me track progress dynamically.

Setting up

from misc.helper import verify_answer

tiny_example = """
..X...
.SAMX.
.A..A.
XMAS.S
.X....
"""

tiny_example_answer = 4

my_example = """
XMXMMX
ASMMMM
SMAAAA
AMSMMS
MSAMXM
XMASMS
"""

my_example_answer = 8

example_input = """
MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX
"""

example_answer_p1 = 18

from pathlib import Path


def part_one(input: str) -> int:
    xmas = "XMAS"

    if Path(input).exists():
        with open(input) as f:
            input = f.read()

    check_position = {}
    count_words = 0
    directions = [(0, 1), (1, -1), (1, 0), (1, 1)]

    for i, line in enumerate(input.strip().splitlines()):
        for j, char in enumerate(line):
            to_be_checked = check_position.pop((i, j), [])

            for schar, coord, dir in to_be_checked:
                if schar == char:
                    if char in "XS":
                        count_words += 1
                    else:
                        next_pos = (i + coord[0], j + coord[1])
                        next_char = xmas[xmas.find(char) + dir]
                        check_position.setdefault(next_pos, []).append(
                            (next_char, coord, dir)
                        )

            if char in "XS":
                direction_shift = 1 if char == "X" else -1
                for dx, dy in directions:
                    next_pos = (i + dx, j + dy)
                    next_char = xmas[xmas.find(char) + direction_shift]
                    check_position.setdefault(next_pos, []).append(
                        (next_char, (dx, dy), direction_shift)
                    )

        check_position = {
            key: val for key, val in check_position.items() if key[0] > i
        }

    return count_words

verify_answer(part_one, tiny_example, tiny_example_answer)

✔️ That's right! The answer is 4.

verify_answer(part_one, my_example, my_example_answer)

✔️ That's right! The answer is 8.

verify_answer(part_one, example_input, example_answer_p1)

✔️ That's right! The answer is 18.

%time
part_one("../inputs/day_04.txt")

CPU times: user 1 μs, sys: 0 ns, total: 1 μs
Wall time: 4.05 μs

That’s the right answer! You are one gold star ⭐ closer to finding the Chief Historian.

Part 2: Searching for X-MAS

In this task, we need to find the shape X created by words MAS, like this:

For example, in the grid below there are 5 X-MAS shapes:

My approach

Instead of trying to traverse the input in one pass, I’ll keep things simple by reading it to a matrix and checking each 3x3 submatrix for the X-MAS shape. Here’s my plan:

I’ll first parse the grid into a matrix format for easy access.
Then, I’ll loop through all possible 3x3 submatrices in the grid and check each submatrix for the X-MAS shape:

For a valid shape, the following conditions must hold:
- The center of the submatrix must be A.
- The upper-right and lower-left corners must be either:
  - M and S, or
  - S and M.
- Similarly, the upper-left and lower-right corners must be either:
  - M and S, or
  - S and M.
Finally, if all these conditions are satisfied, I’ll increment a counter.

This approach allows me to focus on identifying the pattern in localized regions of the grid, keeping the logic straightforward and easy to implement.

Saving test answer

example_answer_p2 = 9

small_x_mas_example = """
MASMSSM
MAMAAAS
MSSSSMM
MAMMMSM
MAAAAAM
SMSSSSS
"""

small_x_mas_example_answer = 5

def read_input_to_matrix(input: str) -> list:
    if Path(input).exists():
        with open(input) as f:
            input = f.read()

    output = []

    for line in input.strip().splitlines():
        output.append([c for c in line.strip()])

    return output


def part_two(input: str) -> int:
    mat = read_input_to_matrix(input)

    count_mats = 0

    for i in range(len(mat[0]) - 2):
        for j in range(len(mat) - 2):
            center = mat[j + 1][i + 1]
            top_left, bottom_right = mat[j][i], mat[j + 2][i + 2]
            top_right, bottom_left = mat[j][i + 2], mat[j + 2][i]

            cond_center = center == "A"
            cond_lr = (top_left == "M" and bottom_right == "S") or (
                top_left == "S" and bottom_right == "M"
            )
            cond_rl = (top_right == "M" and bottom_left == "S") or (
                top_right == "S" and bottom_left == "M"
            )

            if cond_center and cond_lr and cond_rl:
                count_mats += 1

    return count_mats

verify_answer(part_two, small_x_mas_example, small_x_mas_example_answer)

✔️ That's right! The answer is 5.

verify_answer(part_two, example_input, example_answer_p2)

✔️ That's right! The answer is 9.

%time
part_two("../inputs/day_04.txt")

CPU times: user 1e+03 ns, sys: 0 ns, total: 1e+03 ns
Wall time: 2.15 μs

That’s the right answer! You are one gold star ⭐ closer to finding the Chief Historian.