Advent of Code 2024 Day 4

Setup

inp = open("input.txt", "r").read()
sample1 = """MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX
"""
sample2 = """..X...
.SAMX.
.A..A.
XMAS.S
.X....
......
"""
print(f"Part 1: {part1(inp)}")
print(f"Part 2: {part2(inp)}")

I read the input file, copy some of the sample inputs and then run both part 1 and part 2. For some reason, I chose to parse inside the function for each part. Also, this is at the bottom of the file after function declarations since Python doesn’t have a main function.

Parsing

def parse_input(inp):
    inp = inp.strip()

    grid = {}
    row = 0
    for line in inp.splitlines():
        col = 0
        for char in line:
            grid[(row, col)] = char
            col += 1
        row += 1
    width = col
    height = row
    return grid, width, height

The input is in the form of a grid of characters, which I parse into a dictionary with (row, col) tuples as the keys and length-1 strings as the values. I also find out and return the width and the height of the grid.

Part One

We need to do a word search on our grid of characters, looking for all instances of XMAS, horizontally, vertically, diagonally, forwards and backwards.

I did this by first finding all the spots on the grid that contain "X". Then, for all eight directions, I check if going in that direction gives us M, A, and S in that order. Note how I use the .get method in the helper function to deal with going out of the grid bounds. For each match in a direction, I increment the answer.

def part1(inp):
    grid, width, height = parse_input(inp)
    ans = 0

    for row in range(0, height):
        for col in range(0, width):
            if grid[(row, col)] == "X":
                ans += search_for_xmas(grid, row, col)
    return ans


def search_for_xmas(grid, row, col):
    neighbor_offsets = [
        [1, 0],
        [0, 1],
        [-1, 0],
        [0, -1],
        [1, 1],
        [1, -1],
        [-1, 1],
        [-1, -1],
    ]
    count = 0
    for neighbor in neighbor_offsets:
        current = [row, col]
        for i in range(1, 4):
            current[0] += neighbor[0]
            current[1] += neighbor[1]
            current_value = grid.get(tuple(current))
            if current_value == "M" and i == 1:
                pass
            elif current_value == "A" and i == 2:
                pass
            elif current_value == "S" and i == 3:
                count += 1
            else:
                break
    return count

Part Two

Now, it turns out, we needed to find all the X-MASs and not all the XMASs. An X-MAS is the letters MAS arranged in a cross.

M.S
.A.
M.S

To find all the X-MASs, my approach is very similar to part 1. I first find all the As in the grid, then for each such grid position, I see if both its diagonals give us the letters M and S.

def part2(inp):
    grid, width, height = parse_input(inp)
    ans = 0
    for row in range(0, height):
        for col in range(0, width):
            if grid[(row, col)] == "A":
                ans += search_for_cross_mas(grid, row, col)
    return ans


def search_for_cross_mas(grid, row, col):
    diagonals_1 = [[1, 1], [-1, -1]]
    diagonals_2 = [[-1, 1], [1, -1]]
    diagonals_1_values = [
        grid.get((row + offset[0], col + offset[1])) for offset in diagonals_1
    ]
    diagonals_2_values = [
        grid.get((row + offset[0], col + offset[1])) for offset in diagonals_2
    ]
    if (diagonals_1_values == ["S", "M"] or diagonals_1_values == ["M", "S"]) and (
        diagonals_2_values == ["S", "M"] or diagonals_2_values == ["M", "S"]
    ):
        return 1
    else:
        return 0