The fourth day of Advent of Code was yesterday 12/04/2024! If you’re here for the first time today, don’t forget to read the posts about Day 1, Day 2 and Day 3!

I classified the fourth problem as medium (part 1) and hard (part 2).

Tips#

  • If you visualize the inputs as a matrix, the solution becomes more natural.

  • Consider that each character occupies a position y, x in the matrix, where y is the row and x is the column.

  • In part 1, you can start the search when the first character of the word is found.

  • In part 2, you can start the search when the character “A” is found.

  • Part 1: Medium - requires some creativity to implement recursive search, maintaining the search direction.

  • Part 2: Hard - requires more experience to apply some heuristics

How much Python do you need to know?#

The chapters refer to my book Introduction to Programming with Python.

  • Lists - Chapter 6
  • Recursive Functions - Chapter 8
  • Classes - Chapter 10

Answer# 

from auxiliares.arquivos import read_file_without_blank_lines
from auxiliares import string_to_matrix

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

WORD = "XMAS"


class MatrixString:
    def __init__(self, matrix: list[list[str]]):
        self.matrix = matrix
        self.y_max = len(matrix)
        self.x_max = len(matrix[0])

    def validate_position(self, y, x):
        return 0 <= y < self.y_max and 0 <= x < self.x_max


class Problem(MatrixString):
    DIRECTIONS = (
        (1, 0),
        (1, 1),
        (1, -1),
        (0, 1),
        (0, -1),
        (-1, 0),
        (-1, -1),
        (-1, +1),
    )

    def __init__(self, matrix: list[list[str]], word: str):
        self.word = word
        self.word_length = len(word)
        super().__init__(matrix)

    def visit(self, y, x, word_position, iy=0, ix=0):
        if (
            not self.validate_position(y, x)
            or self.matrix[y][x] != self.word[word_position]
        ):
            return 0
        if (
            self.matrix[y][x] == self.word[word_position]
            and word_position == self.word_length - 1
        ):
            return 1
        to_visit = self.DIRECTIONS if iy == 0 and ix == 0 else ((iy, ix),)
        found = 0
        for ny, nx in to_visit:
            if self.visit(y + ny, x + nx, word_position + 1, ny, nx) > 0:
                found += 1
        return found

    def count_words(self):
        words_found = 0
        for y, line in enumerate(self.matrix):
            for x in range(len(line)):
                words_found += self.visit(y, x, 0)
        return words_found


class ProblemPart2(MatrixString):

    def get_letter(self, y, x):
        if self.validate_position(y, x):
            return self.matrix[y][x]
        return None

    def visit_xmas(self, y, x):
        v = [None, None, None, None]
        for i, (ny, nx) in enumerate(
            ((y - 1, x - 1), (y - 1, x + 1), (y + 1, x - 1), (y + 1, x + 1))
        ):
            v[i] = self.get_letter(ny, nx)
            if v[i] is None:
                return 0
        return 1 if "".join(v) in ["MMSS", "MSMS", "SMSM", "SSMM"] else 0

    def count_xmas(self):
        xmas_found = 0
        for y, line in enumerate(self.matrix):
            for x, letter in enumerate(line):
                if letter == "A":
                    if found := self.visit_xmas(y, x):
                        xmas_found += found
        return xmas_found


# Part 1 - Test of the first part
test_p = Problem(string_to_matrix(INPUT), WORD)
test_r = test_p.count_words()
print("Test result (part 1):", test_r)
assert test_r == 18

# Part 1 - Problem
part1_p = Problem(
    string_to_matrix(read_file_without_blank_lines("04/input1.txt")), WORD
)
part1_r = part1_p.count_words()
print("Problem result (part 1):", part1_r)
assert part1_r == 2530

# Part 2 - Test of the second part
test_part2 = ProblemPart2(string_to_matrix(INPUT))
test_r_p2 = test_part2.count_xmas()
print("Test result (part 2):", test_r_p2)
assert test_r_p2 == 9

# Part 2 - Problem
test_part2 = ProblemPart2(
    string_to_matrix(read_file_without_blank_lines("04/input1.txt"))
)
r_p2 = test_part2.count_xmas()
print("Problem result (part 2):", r_p2)
assert r_p2 == 1921

# Output
# Test result (part 1): 18
# Problem result (part 1): 2530
# Test result (part 2): 9
# Problem result (part 2): 1921