How to solve Advent of Code 2024 - Day 4 with Python

Our first grid-based challenge of this years's Advent of Code! 🎄❄️💻

But before we get right into the day and my solution for this day's puzzle, here is the info on how I approach this whole event (where my code is, what editor I use, etc):

Advent of Code 2024 - Info Post

It’s the most festive time of the year - Advent of Code! The highlight of every coder’s December 🎄❄️💻🎉 Here’s everything about my participation, I will link to this from every days’ post. What even IS Advent of Code??!! Good question, my friend. Here is this year’s about page: https:

Machine Learning ChroniclesSarah Glasmacher

Day 4 Puzzle

On my blog here, I will go through the puzzle and my way of solving it. If you want, you can jump directly to the code solution here:
GitHub .py script

Here is the challenge, if you want to read the full puzzle:
Advent of Code 2024 - Day 4

Yesterday I finally understood that we visit a location from previous years of Advent of Code every day 🫣 Today that location is the Ceres monitoring station from 2019 Day 10 - Again I have no stars before 2021 yet, so once again I am clueless on the back story.

We are asked to help a local elf with her word search, finding variations of "XMAS" (and the reversed "SAMX") in a grid of letters. 🔍

Part 1

Day 4 gives you a grid like this:

# Example input
MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

Normally, I like to do most things only with standard Python libraries in this challenge. I do make an exception for grid-based tasks and I do use numpy. (See https://numpy.org/)

Solution Approach:

• read in the grid and transform it into a np.array of char-entries
• extract all the rows and columns as strings (and create their reversed versions via slicing)
• extract the diagonals via np.diag. - this only extracts the top-left to bottom-right diagonals
• for the other diagonals flip the matrix left-to-right or horizontally, then apply np.diag again
• do a substring search for "XMAS" on all these strings

This is sort-of a brute-force approach to the problem, so if this was not Day 4, it probably would have gotten me into problems. Another approach I thought of while in the middle of debugging was to scan the array for "X" and see if they have neighboring "M"s, which would significantly reduce the possible paths for finding "XMAS", but would be very cumbersome to implement correctly. 🤔

Key Code Snippets:

Read grid and extract rows/columns/diagonals:

def read_letter_grid_from_lines(lines: list[str]) -> np.ndarray:
    char_lines = [list(line.strip()) for line in lines]
    return np.array(char_lines)


def extract_rows_from_grid(grid: np.ndarray) -> list[str]:
    rows = ["".join(row) for row in grid]
    reversed_rows = [row[::-1] for row in rows]
    return rows + reversed_rows


def extract_columns_from_grid(grid: np.ndarray) -> list[str]:
    columns = ["".join(column) for column in grid.T]
    reversed_columns = [column[::-1] for column in columns]
    return columns + reversed_columns


def extract_diagonals_from_grid(grid: np.ndarray) -> list[str]:
    grid_height, grid_width = grid.shape
    diagonals = []
    for k in range(grid_width):
        diagonals.append("".join(np.diag(grid, k)))
    for k in range(1, grid_height):
        diagonals.append("".join(np.diag(grid, -k)))

    flipped_array = np.fliplr(grid)
    flipped_height, flipped_width = flipped_array.shape
    for k in range(flipped_width):
        diagonals.append("".join(np.diag(flipped_array, k)))
    for k in range(1, flipped_height):
        diagonals.append("".join(np.diag(flipped_array, -k)))
    reversed_diagonals = [diagonal[::-1] for diagonal in diagonals]
    return diagonals + reversed_diagonals

Full Solution for Part 1:

This just uses the above extraction and applies the substring search:

def solve_part_1(mode: str = "example"):
    file_lines = read_input_file(day=4, mode=mode)
    letter_grid = read_letter_grid_from_lines(file_lines)

    rows = extract_rows_from_grid(letter_grid)
    columns = extract_columns_from_grid(letter_grid)
    diagonals = extract_diagonals_from_grid(letter_grid)

    target_substring = "XMAS"
    total_count = 0

    for line in rows + columns + diagonals:
        total_count += line.count(target_substring)

    return total_count

Part 2

So this messed up my strategy 90% 😫 Here we need to look for patterns of the following structure:

M.S
.A.
M.S

aka, two "MAS" creating an "X" shape by crossing at the "A"-entry. This means we now need to look at neighbors because we need to know if two "MAS" touch and no longer find them individually.

So my tactic now:

• extract 3x3 blocks from the grid whenever I encounter an "A"
• manually check the neighbors of each "A" to see if they form two "MAS" in the right formation

Read grid and extract rows/columns/diagonals:

def extract_A_blocks_from_grid(grid: np.ndarray) -> list[np.ndarray]:
    blocks = []
    for i, j in np.ndindex(grid.shape):
        if (
            grid[i, j] == "A"
            and i + 1 < grid.shape[0]
            and i - 1 >= 0
            and j + 1 < grid.shape[1]
            and j - 1 >= 0
        ):
            blocks.append(grid[i - 1 : i + 2, j - 1 : j + 2])
    return blocks


def check_block_for_XMAS(block: np.ndarray) -> bool:
    if set([block[0, 0], block[2, 2]]) == set(["M", "S"]) and set(
        [block[0, 2], block[2, 0]]
    ) == set(["M", "S"]):
        return True
    return False

Full Solution for Part 2:

def solve_part_2(mode: str = "example"):
    file_lines = read_input_file(day=4, mode=mode)
    letter_grid = read_letter_grid_from_lines(file_lines)

    a_blocks = extract_A_blocks_from_grid(letter_grid)
    total_count = 0
    for block in a_blocks:
        if check_block_for_XMAS(block):
            total_count += 1
    return total_count

Conclusion

Grid-fun. I did a fairly manual approach, which isn't the most elegant but sometimes we just write code that works and doesn't win an art-award. The most important thing with these grids/arrays is checking boundaries - if the "A" is too close to the edge of the board there will be no 3x3 box to access around it, which could lead to out-of-boundary errors. Thankfully nowadays AI-based autocompletion is fairly good at writing all these repetitive edge-cases for you if you want to. 🤖

I think I read on socials that there are some strategies with rotating the grid/matrix somehow, which sounds intriguing and worth your time if you are looking for a more elegant solution.