O quarto dia do Advent of Code foi ontem 04/12/2024! Se você caiu aqui hoje pela primeira vez, não deixe de ler os posts sobre o Dia 1, Dia 2 e Dia 3!

Classifiquei o quarto problema como médio (parte 1) e difícil (parte 2).

Dicas#

  • Se você visualizar as entradas como uma matriz, a solução fica mais natural.

  • Considere que cada caractere ocupa uma posição y, x na matriz, onde y é a linha e x a coluna.

  • Na parte 1, você pode começar a busca quando o primeiro caractere da palavra for encontrado.

  • Na parte 2, você pode começar a busca quando o caractere “A” for encontrado.

  • Parte 1: Médio - exige um pouco de criatividade para implementar a busca recursiva, mantendo a direção da busca.

  • Parte 2: Difícil - exige mais experiência para aplicar algumas heurísticas

Quanto de Python você precisa saber?#

Os capítulos se referem ao meu livro Introdução à Programação com Python.

  • Listas - Capítulo 6
  • Funções recursivas - Capítulo 8
  • Classes - Capítulo 10

Resposta# 

from auxiliares.arquivos import le_arquivo_sem_linhas_em_branco
from auxiliares import string_para_matriz

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

PALAVRA = "XMAS"


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

    def valida_posição(self, y, x):
        return 0 <= y < self.y_max and 0 <= x < self.x_max


class Problema(MatrixString):
    DIREÇÕES = (
        (1, 0),
        (1, 1),
        (1, -1),
        (0, 1),
        (0, -1),
        (-1, 0),
        (-1, -1),
        (-1, +1),
    )

    def __init__(self, matriz: list[list[str]], palavra: str):
        self.palavra = palavra
        self.t_palavra = len(palavra)
        super().__init__(matriz)

    def visita(self, y, x, posição_palavra, iy=0, ix=0):
        if (
            not self.valida_posição(y, x)
            or self.matriz[y][x] != self.palavra[posição_palavra]
        ):
            return 0
        if (
            self.matriz[y][x] == self.palavra[posição_palavra]
            and posição_palavra == self.t_palavra - 1
        ):
            return 1
        a_visitar = self.DIREÇÕES if iy == 0 and ix == 0 else ((iy, ix),)
        achadas = 0
        for ny, nx in a_visitar:
            if self.visita(y + ny, x + nx, posição_palavra + 1, ny, nx) > 0:
                achadas += 1
        return achadas

    def conta_palavras(self):
        palavras_encontradas = 0
        for y, linha in enumerate(self.matriz):
            for x in range(len(linha)):
                palavras_encontradas += self.visita(y, x, 0)
        return palavras_encontradas


class ProblemaParte2(MatrixString):

    def pega_letra(self, y, x):
        if self.valida_posição(y, x):
            return self.matriz[y][x]
        return None

    def visita_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.pega_letra(ny, nx)
            if v[i] is None:
                return 0
        return 1 if "".join(v) in ["MMSS", "MSMS", "SMSM", "SSMM"] else 0

    def conta_xmas(self):
        xmas_encontrados = 0
        for y, linha in enumerate(self.matriz):
            for x, letra in enumerate(linha):
                if letra == "A":
                    if achados := self.visita_xmas(y, x):
                        xmas_encontrados += achados
        return xmas_encontrados


# Parte 1 - Teste da primeira parte
p_teste = Problema(string_para_matriz(ENTRADA), PALAVRA)
r_teste = p_teste.conta_palavras()
print("Resultado do teste (parte 1):", r_teste)
assert r_teste == 18

# Parte 1 - Problema
p_parte1 = Problema(
    string_para_matriz(le_arquivo_sem_linhas_em_branco("04/input1.txt")), PALAVRA
)
r_parte1 = p_parte1.conta_palavras()
print("Resultado do problema (parte 1):", r_parte1)
assert r_parte1 == 2530

# Parte 2 - Teste da segunda parte
teste_parte2 = ProblemaParte2(string_para_matriz(ENTRADA))
r_teste_p2 = teste_parte2.conta_xmas()
print("Resultado do teste (parte 2):", r_teste_p2)
assert r_teste_p2 == 9

# Parte 2 - Problema
teste_parte2 = ProblemaParte2(
    string_para_matriz(le_arquivo_sem_linhas_em_branco("04/input1.txt"))
)
r_p2 = teste_parte2.conta_xmas()
print("Resultado do problema (parte 2):", r_p2)
assert r_p2 == 1921

# Saída
# Resultado do teste (parte 1): 18
# Resultado do problema (parte 1): 2530
# Resultado do teste (parte 2): 9
# Resultado do problema (parte 2): 1921