Advent of code 2024 - Dia 15 de 25
Conteúdo
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 desenha
e 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