O sexto dia do Advent of Code foi ontem 06/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, e Dia 5.

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

Dicas#

  • Novamente, um problema com labirinto, onde cada caractere pode ser visto como um elemento em uma matriz.

  • Como você vai precisar constantemente verificar os limites do labirinto, posições válidas e obstáculos, recomendo criar uma classe para representar o labirinto.

  • Na primeira parte da resposta você encontrará uma classe para representar o percurso e o labirinto em si. Você pode usá-las para visualizar o percurso, como mostrado no problema.

  • Uma classe para trabalhar com vetores 2D também simplifica bastante a implementação. Se você visualizar a posição atual como um vetor (y, x), a nova posição pode ser calculada somando-se outro vetor com a direção do movimento (dy, dx)

  • A parte 1 do problema é relativamente fácil, mas exige que você percorra a matriz seguindo instruções bem precisas e guardando o percurso.

  • Você pode implementar a mudança de direção (90 graus) a cada obstáculo usando uma lista de tuplas que representam as direções. Usando as propriedades do módulo, você pode garantir que a posição sempre seja válida na lista.

  • A parte 2 é mais complicada, pois você deve gerar obstáculos e ver como o programa se comporta. Como o objetivo é colocar o guarda em um loop infinito, você precisa detectar quando um ciclo for formado (ou seu programa não terminará!). Em um grafo, um ciclo pode ser visto quando o percurso voltar novamente a visitar um nó já visitado. Como em nosso problema temos um labirinto e que cada posição pode ser visitada em direções diferentes, para detectar um ciclo, você precisa verificar se a posição já foi visitada antes com a mesma direção de passagem.

  • Para gerar os obstáculos, você deve “especular” que um novo obstáculo pode ser gerado a cada posição do caminho normal do guarda, desde que não seja a posição inicial e já não esteja ocupado por um obstáculo.

  • Você pode criar um novo labirinto com o novo obstáculo e verificar se o caminho entra em loop.

  • A complexidade da parte 2 é alta, algo como O(m x n), demorando cerca de 200 segundos para completar no meu computador.

Quanto de Python você precisa saber?#

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

  • Propriedades do resto (módulo) - Capítulo 2
  • Listas, Tuplas, Conjuntos e Dicionários - Capítulo 6
  • Funções recursivas - Capítulo 8
  • Grafos

Resposta# 

from auxiliares import string_para_matriz, le_arquivo_sem_linhas_em_branco, Vector2d

ENTRADA = """
....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...
"""

GUARDA = "^"
OBSTÁCULO = "#"

DIREÇÕES = [Vector2d(*v) for v in [(-1, 0), (0, 1), (1, 0), (0, -1)]]


class Percurso:
    def __init__(self):
        self.percurso = {}

    def __len__(self):
        return len(self.percurso)

    def visitada(self, posição: Vector2d, direção: int) -> bool:
        if posição in self.percurso and direção in self.percurso[posição]:
            return True
        return False

    def adiciona(self, posição: Vector2d, direção: int):
        if posição in self.percurso:
            self.percurso[posição].add(direção)
        else:
            self.percurso[posição] = {direção}


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 acha_guarda(self) -> Vector2d:
        for y, linha in enumerate(self.labirinto):
            if "^" in linha:
                x = linha.index(GUARDA)
                return Vector2d(y, x)
        raise ValueError("Não há guarda no 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 desenha(self, percurso, caractere="X"):
        for posição, direções in percurso.items():
            if direções:
                h = {1, 3} & direções
                v = {0, 2} & direções
                dchar = "+" if h and v else "-" if h else "|"
                self.labirinto[posição.y][posição.x] = dchar
            else:
                self.labirinto[posição.y][posição.x] = caractere

    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 faz_ronda(labirinto: Labirinto) -> tuple[Percurso, bool]:
    percorrido = Percurso()
    direção_atual = 0
    posição = labirinto.acha_guarda()
    while labirinto.posição_válida(nova_posição := posição + DIREÇÕES[direção_atual]):
        percorrido.adiciona(posição, direção_atual)
        if labirinto[nova_posição.y, nova_posição.x] == OBSTÁCULO:
            direção_atual = (direção_atual + 1) % 4
        else:
            posição = nova_posição
            if percorrido.visitada(posição, direção_atual):
                return percorrido, True
            percorrido.adiciona(posição, direção_atual)
    return percorrido, False


def procura_onde_por_obstáculos(labirinto: Labirinto):
    direção_atual = 0
    obstáculos_possíveis = set()
    posição = posição_inicial = labirinto.acha_guarda()
    while labirinto.posição_válida(nova_posição := posição + DIREÇÕES[direção_atual]):
        if labirinto[nova_posição.y, nova_posição.x] == OBSTÁCULO:
            direção_atual = (direção_atual + 1) % 4
        else:
            posição = nova_posição
            if posição != posição_inicial:
                novo_labirinto = labirinto.copy()
                novo_labirinto[posição.y, posição.x] = OBSTÁCULO
                _, ciclo_detectado = faz_ronda(novo_labirinto)
                if ciclo_detectado:
                    obstáculos_possíveis.add(posição)
    return obstáculos_possíveis


# Parte 1
# Vetor de teste
labirinto_teste = string_para_matriz(ENTRADA)

# posição_inicial = acha_guarda(labirinto)
percurso, _ = faz_ronda(Labirinto(labirinto_teste))
print("Posições únicas (teste):", len(percurso))
assert len(percurso) == 41

labirinto_entrada = string_para_matriz(le_arquivo_sem_linhas_em_branco("06/input.txt"))
percurso, _ = faz_ronda(Labirinto(labirinto_entrada))
print("Posições únicas (parte 1):", len(percurso))
assert len(percurso) == 4696

# Parte 2

obstáculos_possíveis = procura_onde_por_obstáculos(Labirinto(labirinto_teste))
print("Obstáculos possíveis (teste parte 2):", len(obstáculos_possíveis))
assert len(obstáculos_possíveis) == 6

obstáculos_possíveis = procura_onde_por_obstáculos(Labirinto(labirinto_entrada))
print("Obstáculos possíveis (parte 2):", len(obstáculos_possíveis))
assert len(obstáculos_possíveis) >= 1443

# Saída
# Posições únicas (teste): 41
#Posições únicas (parte 1): 4696
#Obstáculos possíveis (teste parte 2): 6
#Obstáculos possíveis (parte 2): 1443

Módulo auxiliares.py#

Listagem parcial, a adicionar às outras funções auxiliares publicadas em outros artigos.

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 __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