Sean McLemon | Advent of Code

2024-12-04 - Ceres Search

(original .ipynb)

Day 4 puzzle input is grid of letters, mine is here). Part 1 involves finding the text "XMAS" vertically/horizontally/diagonally both forwards/backwards and up/down. Part 2 involves finding the letter "A" flanked by two "M"s and and "S" in an "X" formation - again forwards/backwards/up/down.

puzzle_input_str = open("./puzzle_input/day4.txt").read()
test_input_str = """MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX"""


def parse_input(input_str):
    return input_str.splitlines()


def rotate(l):
    new_l = list(reversed(list(zip(*l))))
    return ["".join(row) for row in new_l]


def get_all_directions(grid):
    for _ in range(4):
        grid = rotate(grid)
        yield from grid

        max_r = len(grid)
        for start_r in range(len(grid)):
            line = [grid[start_r+r][r] for r in range(0, max_r-start_r)]
            yield "".join(line)

            if start_r != 0:
                line = [grid[r][start_r+r] for r in range(0, max_r-start_r)]
                yield "".join(line)

                
def find_xmas_count(line):
    xmas_index = 0    
    count = 0
    while xmas_index < len(line):
        xmas_index = line.find("XMAS", xmas_index)
        if xmas_index < 0:
            return count
        count += 1
        xmas_index += 1
    return count
    

def part_one(input_str):
    input_lines = parse_input(input_str)
    all_directions = list(get_all_directions(input_lines))

    total_xmas_count = sum(find_xmas_count(line) for line in all_directions)

    return total_xmas_count

assert 18 == part_one(test_input_str)


print("part one:", part_one(puzzle_input_str))

part one: 2507

def is_xmas(grid, r, c):
    max_r = len(grid) - 1
    max_c = len(grid[0]) - 1
    if r-1 < 0 or r+1 > max_r or c-1 < 0 or c+1 > max_c:
        return False
    
    mas_grid = (
        ("M", (-1, -1)),
        ("M", ( 1, -1)),
        ("S", (-1,  1)),
        ("S", ( 1,  1))
    )

    return grid[r][c] == "A" and all(grid[r+dr][c+dc] == s for (s, (dr,dc)) in mas_grid)


def find_xmas_count(grid):
    count = 0
    for _ in range(4):
        grid = rotate(grid)
        for r in range(len(grid)):
            for c in range(len(grid)):
                if is_xmas(grid, r, c):
                    count += 1
    return count

def part_two(input_str):
    input_lines = parse_input(input_str)
    result = find_xmas_count(input_lines)
    return result
    
    
assert 9 == part_two(test_input_str)

print("part two:", part_two(puzzle_input_str))

part two: 1969