O décimo quinto dia do Advent of Code foi ontem 15/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, Dia 9, Dia 10, Dia 11, Dia 12, Dia 13 e Dia 14.

Classifiquei o décimo quinto problema como médio (parte 1) e médio (parte 2).

Dicas#

  • A primeira parte do problema é ler o labirinto (armazém) e os comandos do robô.
  • Utilize as entradas de exemplo para testar a solução.
  • Você precisa detectar na entrada do labirinto, onde estão as paredes, o robô e as caixas.
  • Os comandos estão em várias linhas, fica mais fácil se você concatená-las em uma só string.
  • Você pode implementar as direções do robô (comandos) usando vetores.
  • Vetores também podem ser utilizados para marcar as posições das caixas e paredes.
  • As paredes circundam todo o armazém, você não precisa de preocupar com o robô saindo do armazém.
  • Para verificar se o robô pode se mexer, verifique se a nova posição está livre. Neste caso, mova o robô, atualizando a posição.
  • Se a posição seguinte for ocupada por uma parede, o robô não pode se mexer e fica no mesmo lugar.
  • Para saber se pode mover as caixas, você pode tentar recursivamente todas as caixas a partir da direção do movimento. A cada caixa, verifique se ela pode se mover (espaço em branco na direção do movimento). Caso uma das caixas não possa ser movida, o movimento é cancelado.
  • Lembre-se que o robô pode empurrar várias caixas ao mesmo tempo. Uma função recursiva pode ajudar a resolver este problema.
  • Na parte 1, as caixas são do mesmo tamanho das paredes, ou seja, cada caixa ocupa uma posição. Na parte 2, cada caixa ocupa duas posições.
  • A parte 2 é um pouco mais complexa, pois você pode mover mais que colunas e linhas de caixas, mas partes inteiras do armazém.
  • O movimento horizontal é semelhante ao da parte 1, pois cada caixa tem altura de apenas um caractere, como na parte 1.
  • Cada movimento na parte 2 pode mover até 2 caixas ao mesmo tempo. Mas esse movimento é feito em cascata, logo estas duas caixas podem mover outras 2, 3, ou mais caixas. Cada movimento de caixa pode movimentar a cada passo, zero, uma ou duas caixas, mas pode ocasionar o movimento de muitas outras.
  • Na parte 2, você precisa verificar se o movimento inteiro é válido. Por exemplo, quando as caixas sendo empurradas formam um V ou ficam presas em uma parede, todas tem que parar de se mover. Se você implementar a função de movimento como na parte 1, verá que as caixas vão se mexer em vários pedaços, o que leva a resposta errada.

Quanto de Python você precisa saber?#

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

  • Listas - Capítulo 6
  • Strings - Capítulo 7
  • Funções recursivas - Capítulo 8
  • Classes, herança - Capítulo 10

Resposta#

Aqui o código que resolve o problema. Você verá as cicatrizes no código da troca entre a parte 1 e a parte 2, mas o código funciona relativamente bem.

Você pode de usar as classes Armazém, Caixas, Parede, Robô, Problema e Problema2 para depurar sua solução. Os métodos desenhae prompt podem ajudar a interpretar e desenhar os comandos passo a passo. Embora não sejam chamados na resposta, eles estão no código caso você precise.

import sys
from auxiliares import le_arquivo_sem_linhas_em_branco, Vector2d, Labirinto

ENTRADA_TESTE = """
########
#..O.O.#
##@.O..#
#...O..#
#.#.O..#
#...O..#
#......#
########

<^^>>>vv<v>>v<<
"""

ENTRADA = """
##########
#..O..O.O#
#......O.#
#.OO..O.O#
#..O@..O.#
#O#..O...#
#O..O..O.#
#.OO.O.OO#
#....O...#
##########

<vv>^<v^>v>^vv^v>v<>v^v<v<^vv<<<^><<><>>v<vvv<>^v^>^<<<><<v<<<v^vv^v>^
vvv<<^>^v^^><<>>><>^<<><^vv^^<>vvv<>><^^v>^>vv<>v<<<<v<^v>^<^^>>>^<v<v
><>vv>v^v^<>><>>>><^^>vv>v<^^^>>v^v^<^^>v^^>v^<^v>v<>>v^v^<v>v^^<^^vv<
<<v<^>>^^^^>>>v^<>vvv^><v<<<>^^^vv^<vvv>^>v<^^^^v<>^>vvvv><>>v^<<^^^^^
^><^><>>><>^^<<^^v>>><^<v>^<vv>>v>>>^v><>^v><<<<v>>v<v<v>vvv>^<><<>^><
^>><>^v<><^vvv<^^<><v<<<<<><^v<<<><<<^^<v<^^^><^>>^<v^><<<^>>^v<v^v<v^
>^>>^v>vv>^<<^v<>><<><<v<<v><>v<^vv<<<>^^v^>^^>>><<^v>>v^v><^^>>^<>vv^
<><^^>^^^<><vvvvv^v<v<<>^v<v>v<<^><<><<><<<^^<<<^<<>><<><^^^>^^<>^>v<>
^^>vv<^v^v<vv>^<><v<^v>^^^>>>^^vvv^>vvv<>>>^<^>>>>>^<<^v>^vvv<>^<><<v>
v^^>>><<^^<>>^v^<v^vv<>v^<<>^<^v^v><^<<<><<^<v><v<>vv>>v><v^<vv<>v^<<^
"""


def le_entrada(entrada: str) -> tuple[str, str]:
    labirinto = []
    comandos = []
    for linha in entrada.splitlines():
        if not linha.strip():
            continue
        if linha.startswith("#"):
            labirinto.append(linha)
        else:
            comandos.append(linha)

    return labirinto, comandos


class Vector2dComSimbolo(Vector2d):
    def __init__(self, y, x, símbolo):
        super().__init__(y, x)
        self.símbolo = símbolo

    def __add__(self, other):
        return Vector2dComSimbolo(self.y + other.y, self.x + other.x, self.símbolo)

    def __sub__(self, other):
        return Vector2dComSimbolo(self.y - other.y, self.x - other.x, self.símbolo)


class Caixas(Vector2dComSimbolo):
    def __init__(self, y, x, símbolo="O"):
        super().__init__(y, x, símbolo)


class Parede(Vector2dComSimbolo):
    def __init__(self, y, x):
        super().__init__(y, x, "#")


class Robô(Vector2dComSimbolo):
    def __init__(self, y, x):
        super().__init__(y, x, "@")


class Armazém(Labirinto):
    def inicie_desenho(self, fundo="."):
        self.fundo = fundo
        self.desenho = []
        for _ in range(self.max_y):
            self.desenho.append([fundo] * self.max_x)

    def desenhe(self, objetos: list[Vector2dComSimbolo]):
        for objeto in objetos:
            self.desenho[objeto.y][objeto.x] = objeto.símbolo

    def dump_desenho(self, output=sys.stdout):
        for linha in self.desenho:
            print("".join(linha), file=output)

    def __iter__(self):
        return iter(self.labirinto)


class Problema:
    DIREÇÕES = {
        "<": Vector2d(0, -1),
        "^": Vector2d(-1, 0),
        ">": Vector2d(0, 1),
        "v": Vector2d(1, 0),
    }

    def __init__(self, labirinto: list[str], comandos: list[str]):
        self.comandos = "".join(comandos)
        self.armazém = Armazém(labirinto)
        self.monta()

    def monta(self):
        self.paredes = set()
        self.caixas = dict()
        self.robô = None
        for y, linha in enumerate(self.armazém):
            for x, char in enumerate(linha):
                if char == "#":
                    self.paredes.add(Parede(y, x))
                if char == "O":
                    caixa = Caixas(y, x)
                    self.caixas[caixa] = caixa
                if char == "@":
                    self.robô = Robô(y, x)

    def desenha(self):
        self.armazém.inicie_desenho()
        self.armazém.desenhe(self.paredes)
        self.armazém.desenhe(self.caixas)
        self.armazém.desenhe([self.robô])
        self.armazém.dump_desenho()

    def executa_comandos(self):
        for comando in self.comandos:            
            direção = self.DIREÇÕES[comando]
            nova_posição = self.robô + direção
            if nova_posição in self.caixas:
                if not self.empurra(nova_posição, direção):
                    continue
            elif nova_posição in self.paredes:
                continue
            self.robô += direção

    def empurra(self, posição: Vector2d, direção: Vector2d, executa: bool = True):
        nova_posição = posição + direção
        if nova_posição in self.paredes:
            return False
        if nova_posição in self.caixas:
            pode_empurrar = self.empurra(nova_posição, direção, executa)
            if not pode_empurrar:
                return False
        if executa:
            caixa = self.caixas.pop(posição)
            caixa.y = nova_posição.y
            caixa.x = nova_posição.x
            self.caixas[caixa] = caixa
        return True

    def gps_caixas(self):
        soma = 0
        for caixas in self.caixas:
            soma += caixas.y * 100 + caixas.x
        return soma

    def prompt(self):
        while True:
            self.desenha()
            comandos = input("Comandos: ").lower().strip()
            if not comandos:
                break
            self.comandos = comandos
            self.executa_comandos()



class Problema2(Problema):
    def __init__(self, labirinto: list[str], comandos: list[str]):
        super().__init__(labirinto, comandos)
        self.armazém.max_x *= 2

    def monta(self):
        self.paredes = set()
        self.caixas = dict()
        self.robô = None
        for y, linha in enumerate(self.armazém):
            for x, char in enumerate(linha):
                if char == "#":
                    self.paredes.add(Parede(y, x * 2))
                    self.paredes.add(Parede(y, x * 2 + 1))
                if char == "O":
                    caixa1 = Caixas(y, x * 2, "[")
                    caixa2 = Caixas(y, x * 2 + 1, "]")
                    self.caixas[caixa1] = caixa1
                    self.caixas[caixa2] = caixa2
                if char == "@":
                    self.robô = Robô(y, x * 2)

    def empurra(self, posição: Vector2d, direção: Vector2d, executa: bool = True):
        nova_posição = posição + direção
        if direção in [Vector2d(0, -1), Vector2d(0, 1)] or nova_posição in self.paredes:
            return super().empurra(posição, direção, executa)

        if posição not in self.caixas:
            return True

        caixa1, caixa2 = self.ache_caixa(posição)

        pode_empurrar1 = super().empurra(caixa1, direção, False)
        pode_empurrar2 = super().empurra(caixa2, direção, False)

        if pode_empurrar1 and pode_empurrar2:
            if executa:
                self.empurra_v(caixa1, caixa2, direção)
            return True
        return False

    def ache_caixa(self, posição):
        caixa1 = self.caixas[posição]
        if caixa1.símbolo == "[":
            caixa2 = self.caixas[posição + Vector2d(0, 1)]
        else:
            caixa2 = self.caixas[posição + Vector2d(0, -1)]
        return caixa1, caixa2

    def empurra_v(self, posição1, posição2, direção):
        np1 = posição1 + direção
        np2 = posição2 + direção
        if np1 in self.caixas:
            self.empurra_v(*self.ache_caixa(np1), direção)
        if np2 in self.caixas:
            self.empurra_v(*self.ache_caixa(np2), direção)
        for posição, nova_posição in zip([posição1, posição2], [np1, np2]):
            caixa = self.caixas.pop(posição)
            caixa.y = nova_posição.y
            caixa.x = nova_posição.x
            self.caixas[caixa] = caixa

    def gps_caixas(self):
        soma = 0
        for caixa in self.caixas:
            if caixa.símbolo == "[":
                soma += caixa.y * 100 + caixa.x
        return soma


problema = Problema(*le_entrada(ENTRADA_TESTE))
problema.executa_comandos()
gps = problema.gps_caixas()
print("Parte 1 - teste pequena entrada:", gps)
assert gps == 2028


problema = Problema(*le_entrada(ENTRADA))
problema.executa_comandos()
gps = problema.gps_caixas()
print("Parte 1 - teste entrada grande:", gps)
assert gps == 10092

problema = Problema(*le_entrada(le_arquivo_sem_linhas_em_branco("15/input.txt")))
problema.executa_comandos()
gps = problema.gps_caixas()
print("Parte 1 - entrada grande:", gps)
assert gps == 1552463

# Parte 2

problema = Problema2(*le_entrada(ENTRADA))
problema.executa_comandos()
gps = problema.gps_caixas()
print("Parte 2 - teste entrada grande:", gps)
assert gps == 9021


problema = Problema2(*le_entrada(le_arquivo_sem_linhas_em_branco("15/input.txt")))
problema.executa_comandos()
gps = problema.gps_caixas()
print("Parte 2 - entrada grande:", gps)
assert gps == 1554058