O décimo dia do Advent of Code foi ontem 10/12/2024! Se você caiu aqui hoje pela primeira vez, não deixe de ler os posts sobre o Dia 1, Dia 2, Dia 3, Dia 4, Dia 5, Dia 6, Dia 7, Dia 8 e Dia 9.

Classifiquei o décimo problema como fácil (parte 1) e fácil (parte 2). O problema é bem parecido com o dia 4.

Dicas#

  • Você pode começar a procurar os caminhos quando encontrar o ‘0’ no labirinto.

  • O problema define que o caminho pode ser feito em 4 direções: para cima, para baixo, esquerda e direita. Diagonais não são permitidas.

  • Assim como fizemos em outros problemas, você pode usar vetores para representar as direções do caminho.

  • Para cada direção possível, você deve verificar se a coordenada é válida e se o valor corresponde ao passo seguinte do caminho. Esta pesquisa se repete até que você encontre o ‘9’.

  • O problema fornece vários vetores de teste. Use-os para validar suas funções.

  • Para a parte 1, você precisa apenas contar quantos ‘9’ únicos você conseguiu alcançar a partir o ‘0’ de partida. Para saber se o ‘9’ encontrado é único, você pode usar um dicionário ou conjunto e a coordenada do ‘9’ como chave/elemento.

  • Você deve considerar que cada caminho pode atingir o mesmo destinho mais de uma vez, pois pode mudar de direção no próximo passo, mas chegar no mesmo lugar. Para a parte 2, você precisará saber quantos caminhos de 0 a 9 foram feitos.

Quanto de Python você precisa saber?#

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

  • Listas, tuplas - Capítulo 6
  • Strings - Capítulo 7
  • Funções recursivas - Capítulo 8

Resposta# 

from auxiliares import (
    Labirinto,
    string_para_matriz,
    Vector2d,
    le_arquivo_sem_linhas_em_branco,
)


class Ilha(Labirinto):
    DIREÇÕES = (
        Vector2d(1, 0),
        Vector2d(0, 1),
        Vector2d(0, -1),
        Vector2d(-1, 0),
    )

    def inicio_trilhas(self):
        cabeça_trilha = []
        for y, linha in enumerate(self.labirinto):
            for x, c in enumerate(linha):
                if c == "0":
                    cabeça_trilha.append(Vector2d(y, x))
        return cabeça_trilha
    

    def procura_trilha(self, inicio, corrente="0"):
        cabeças = {}
        if (atual := self.labirinto[inicio.y][inicio.x]) != corrente:
            return None
        elif atual == "9":
            return {inicio: 1}
        for direção in self.DIREÇÕES:
            proximo = inicio + direção
            if self.posição_válida(proximo):
                achadas = self.procura_trilha(proximo, str(int(corrente) + 1))
                if achadas:
                    for cabeça in achadas:
                        cabeças[cabeça] = (
                            cabeças.setdefault(cabeça, 0) + achadas[cabeça]
                        )
        return cabeças


def acha_trilhas(entrada):
    ilha = Ilha(string_para_matriz(entrada))
    parte1, parte2 = 0, 0
    for inicio in ilha.inicio_trilhas():
        cabeças = ilha.procura_trilha(inicio)
        parte1 += len(cabeças)
        parte2 += sum(cabeças.values())
    return parte1, parte2


ENTRADA = """
0123
1234
8765
9876
"""

ENTRADA2 = """
...0...
...1...
...2...
6543456
7.....7
8.....8
9.....9
"""

ENTRADA3 = """
..90..9
...1.98
...2..7
6543456
765.987
876....
987....
"""
ENTRADA4 = """
10..9..
2...8..
3...7..
4567654
...8..3
...9..2
.....01
"""

ENTRADA5 = """
89010123
78121874
87430965
96549874
45678903
32019012
01329801
10456732
"""


achadas, _ = acha_trilhas(ENTRADA)
print("Teste 1 - parte 1:", achadas)
assert achadas == 1
achadas, _ = acha_trilhas(ENTRADA2)
print("Teste 2 - parte 1:", achadas)
assert achadas == 2
achadas, _ = acha_trilhas(ENTRADA3)
print("Teste 3 - parte 1:", achadas)
assert achadas == 4
achadas, _ = acha_trilhas(ENTRADA4)
print("Teste 4 - parte 1:", achadas)
assert achadas == 3
achadas, _ = acha_trilhas(ENTRADA5)
print("Teste 5 - parte 1:", achadas)
assert achadas == 36

ENTRADA_PARTE_1 = le_arquivo_sem_linhas_em_branco("10/input.txt")
achadas, _ = acha_trilhas(ENTRADA_PARTE_1)
print("Entrada - parte 1:", achadas)
assert achadas == 667

# Parte 2

ENTRADA_PARTE_2_1 = """
.....0.
..4321.
..5..2.
..6543.
..7..4.
..8765.
..9....
"""

ENTRADA_PARTE_2_2 = """
..90..9
...1.98
...2..7
6543456
765.987
876....
987....
"""

ENTRADA_PARTE_2_3 = """
012345
123456
234567
345678
4.6789
56789.
"""

ENTRADA_PARTE_2_4 = """
89010123
78121874
87430965
96549874
45678903
32019012
01329801
10456732
"""

_, achadas = acha_trilhas(ENTRADA_PARTE_2_1)
print("Teste 1 - parte 2:", achadas)
assert achadas == 3

_, achadas = acha_trilhas(ENTRADA_PARTE_2_2)
print("Teste 2 - parte 2:", achadas)
assert achadas == 13

_, achadas = acha_trilhas(ENTRADA_PARTE_2_3)
print("Teste 3 - parte 2:", achadas)
assert achadas == 227

_, achadas = acha_trilhas(ENTRADA_PARTE_2_4)
print("Teste 4 - parte 2:", achadas)
assert achadas == 81

_, achadas = acha_trilhas(ENTRADA_PARTE_1)
print("Entrada - Parte 2:", achadas)
assert achadas == 1344

# Saída
# Teste 1 - parte 1: 1
# Teste 2 - parte 1: 2
# Teste 3 - parte 1: 4
# Teste 4 - parte 1: 3
# Teste 5 - parte 1: 36
# Entrada - parte 1: 667
# Teste 1 - parte 2: 3
# Teste 2 - parte 2: 13
# Teste 3 - parte 2: 227
# Teste 4 - parte 2: 81
# Entrada - Parte 2: 1344

Módulo auxiliares# 

class Vector2d:
    def __init__(self, y, x):
        self.x = x
        self.y = y

    def copy(self):
        return Vector2d(self.y, self.x)

    def __add__(self, other):
        return Vector2d(self.y + other.y, self.x + other.x)

    def __sub__(self, other):
        return Vector2d(self.y - other.y, self.x - other.x)

    def __str__(self):
        return f"({self.y}, {self.x})"

    def __repr__(self):
        return f"Vector2d({self.y}, {self.x})"

    def __hash__(self):
        return hash(f"({self.y}, {self.x})")

    def __eq__(self, other):
        if isinstance(other, Vector2d):
            return self.x == other.x and self.y == other.y
        return False


class Labirinto:
    def __init__(self, labirinto):
        self.max_y = len(labirinto)
        self.max_x = len(labirinto[0])
        self.orig_labirinto = labirinto
        self.labirinto = [list(linha) for linha in labirinto]

    def copy(self):
        return Labirinto(self.orig_labirinto)

    def posição_válida(self, posição: Vector2d) -> bool:
        return 0 <= posição.y < self.max_y and 0 <= posição.x < self.max_x

    def __str__(self):
        return "\n".join(["".join(linha) for linha in self.labirinto])

    def __setitem__(self, yx, value):
        self.labirinto[yx[0]][yx[1]] = value

    def __getitem__(self, yx):
        return self.labirinto[yx[0]][yx[1]]


def le_arquivo_sem_linhas_em_branco(nome_arquivo: str) -> str:
    return "\n".join(
        zz
        for linha in le_arquivo(nome_arquivo).splitlines()
        if len(zz := linha.strip()) > 0