Advent of code 2024 - Dia 14 de 25
Conteúdo
O décimo quarto dia do Advent of Code foi ontem 14/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 e Dia 13.
Classifiquei o décimo quarto problema como médio (parte 1) e médio (parte 2).
Dicas#
- Mais um problema com labirinto :-D É muito bom ter uma classe como a Labirinto.
- Este problema também utiliza vetores, a classe Vector2d será bem útil.
- Você pode utilizar uma expressão regular para extrair os dados da entrada.
- Organizar o código em classes é uma boa prática. Neste caso, cada robô é claramente um objeto.
- Lembre da divisão inteira para calcular a coluna e linhas do meio.
- Cada robô tem uma posição e um vetor velocidade.
- Quando o robô se move para uma posição fora do labirinto (Zona), ela pode ser corrigida usando o operador módulo (ver capítulo 2, propriedades do resto da divisão).
- Você pode ver o avanço do tempo como uma simulação.
- Utilize os valores de teste para verificar se sua solução responde ao problema. Comece por testar a movimentação dos robôs e depois a teleportação que ocorre quando eles se movem fora da Zona.
- A Parte 2 é um pouco diferente das demais. Precisamos encontrar um padrão de natal na posição dos robôs.
- Depois de observar a resposta, avançando a simulação manualmente, pois o enunciado não deixa claro; podemos ver que o segundo da simulação quando os robôs formam a figura de natal é o primeiro em que não há sobreposição de robôs, ou seja, não há dois robôs na mesma posição.
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
- Reduce - Capítulo 8
- Classes, herança - Capítulo 10
- Expressões regulares - Capítulo 12
Resposta#
import sys
import re
from functools import reduce
from auxiliares import (
Vector2d,
Labirinto,
string_para_lista,
le_arquivo_sem_linhas_em_branco,
)
E_REGEX = r"p=(\-*\d+),(\-*\d+) v=(\-*\d+),(\-*\d+)"
linha_robô = re.compile(E_REGEX)
ENTRADA = """
p=0,4 v=3,-3
p=6,3 v=-1,-3
p=10,3 v=-1,2
p=2,0 v=2,-1
p=0,0 v=1,3
p=3,0 v=-2,-2
p=7,6 v=-1,-3
p=3,0 v=-1,-2
p=9,3 v=2,3
p=7,3 v=-1,2
p=2,4 v=2,-3
p=9,5 v=-3,-3
"""
class Robô:
def __init__(self, posição: Vector2d, velocidade: Vector2d):
self.posição = posição
self.velocidade = velocidade
def mova(self, limites: Vector2d):
self.posição.x = (self.posição.x + self.velocidade.x) % limites.x
self.posição.y = (self.posição.y + self.velocidade.y) % limites.y
def __repr__(self):
return f"Robô(posição={self.posição}, velocidade={self.velocidade})"
def pega_entrada(entrada: str) -> list[Robô]:
robôs = []
for linha in entrada:
robô = [int(x) for x in linha_robô.findall(linha)[0]]
robôs.append(Robô(Vector2d(robô[1], robô[0]), Vector2d(robô[3], robô[2])))
return robôs
class Zona(Labirinto):
def __init__(self, largura, altura):
labirinto = [" " * largura for _ in range(altura)]
super().__init__(labirinto)
def desenhe(self, fundo="."):
self.fundo = fundo
self.desenho = []
for _ in range(self.max_y):
self.desenho.append([fundo] * self.max_x)
def desenhe_robôs(self, robôs: list[Robô]):
for robô in robôs:
atual = self.desenho[robô.posição.y][robô.posição.x]
novo = chr(ord(atual) + 1) if atual != self.fundo else "1"
self.desenho[robô.posição.y][robô.posição.x] = novo
def dump_desenho(self, output=sys.stdout):
for linha in self.desenho:
print("".join(linha), file=output)
class Problema:
def __init__(self, entrada: str, largura: int, altura: int):
self.robôs = pega_entrada(string_para_lista(entrada))
self.zona = Zona(largura, altura)
def desenhe(self):
self.zona.desenhe()
self.zona.desenhe_robôs(self.robôs)
self.zona.dump_desenho()
def mova(self):
for robô in self.robôs:
robô.mova(Vector2d(self.zona.max_y, self.zona.max_x))
def calcula_fator_de_segurança(self):
quadrantes = [0, 0, 0, 0]
meio = Vector2d(self.zona.max_y // 2, self.zona.max_x // 2)
for robô in self.robôs:
if robô.posição.x == meio.x or robô.posição.y == meio.y:
continue
qx = 1 if robô.posição.x > meio.x else 0
qy = 1 if robô.posição.y > meio.y else 0
quadrantes[qx + qy * 2] += 1
return reduce(lambda x, y: x * y, quadrantes, 1)
def verifica_sobreposição(self):
ocupados = set()
for robô in self.robôs:
if robô.posição in ocupados:
return True
ocupados.add(robô.posição)
return False
# Parte 1 - Teste
problema = Problema(ENTRADA, largura=11, altura=7)
for i in range(100):
problema.mova()
fator_de_segurança = problema.calcula_fator_de_segurança()
print("Fator de segurança - Parte 1 - Teste:", fator_de_segurança)
assert fator_de_segurança == 12
# Parte 1
problema = Problema(
le_arquivo_sem_linhas_em_branco("14/input.txt"), largura=101, altura=103
)
for i in range(100):
problema.mova()
fator_de_segurança = problema.calcula_fator_de_segurança()
print("Fator de segurança - Parte 1:", fator_de_segurança)
assert fator_de_segurança == 221655456
# Parte 2 - Procurando o motivo de natal
problema = Problema(
le_arquivo_sem_linhas_em_branco("14/input.txt"), largura=101, altura=103
)
for i in range(1, 100000):
problema.mova()
if not problema.verifica_sobreposição():
problema.desenhe()
print(f"Parte 2 - Sobreposição não encontrada no segundo {i}")
break
# Saída:
# Fator de segurança - Parte 1 - Teste: 12
# Fator de segurança - Parte 1: 221655456
# 1........11..................1.......................................................................
# .................................................................................................1...
# .............................................1.......................................................
# ................1................11..................1....................1..........................
# .......1.............................................................................................
# ........................................................................1............................
# .....................................................................................................
# .....................................................................................................
# .........................................1...........................................................
# ..............1..............................................1.......................................
# .....................................................................................................
# ...................................................1..................................1..............
# ...................................................................1.................................
# ........1...........................................................................1................
# .................................1...................................................................
# ..1.................1................................................................................
# .............1..................1.....................................1..............................
# ...................1......................................................................1..........
# ................1..................1..............................1..................................
# .......1.............................................................................................
# .............................................11.....................1..............1.................
# ............................................................................1........................
# .............1.......................................................................................
# ...................................................1.................................................
# .................1...................................................................................
# ........................................................1............................................
# ...................1.................................................................................
# .................1.................................................................................1.
# ................................1...........1..................................................1.....
# ...................1.............................................................1...................
# ..................................................1.............................1.1.............1....
# .....................................................................................................
# .............................................................................1.......................
# ..................................................................1..................................
# .....................................................1...............1...............................
# 1...............................................................................1............1.......
# ...........................................................................................1.........
# ..................................................1..........................................1.......
# ...................1......................................................................1..........
# .......................................................................1........................1....
# ......................1..........................................................................1...
# .............................................1.......................................................
# ..........................................................................................1..........
# ............1.............................................................................1..........
# ...................................1111111111111111111111111111111...................................
# ...................................1.............................1..........1........................
# ...................................1.............................1...................................
# ...................................1.............................1...................................
# ...................................1.............................1...................................
# ...................................1..............1..............1.....................1.............
# ...................................1.............111.............1...................................
# ....1..............................1............11111............1...................................
# ...................................1...........1111111...........1...................................
# ..............................1....1..........111111111..........1...................................
# ...................................1............11111............1...................1...............
# ................1..................1...........1111111...........1...................................
# ...................................1..........111111111..........1...................................
# ....................1..............1.........11111111111.........1...................................
# ...................................1........1111111111111........1...................................
# ..1..........1..........1..........1..........111111111..........1......................1............
# ...................................1.........11111111111.........1...............1...................
# ...................................1........1111111111111........1...................................
# ...................................1.......111111111111111.......1..............1....................
# ...................................1......11111111111111111......1..................1.............1..
# ...............................1...1........1111111111111........1..1................................
# ........................1..........1.......111111111111111.......1......1............................
# .................1.....1...........1......11111111111111111......1...................................
# ...................................1.....1111111111111111111.....1......1............................
# ...............1...................1....111111111111111111111....1..........1........................
# .....................1.....1.......1.............111.............1.........................1.........
# ..........................1........1.............111.............1...................................
# ...................................1.............111.............1...................................
# ...................................1.............................1...................................
# ...................................1.............................1.....................1.............
# .....1.............................1.............................1...................................
# ...................................1.............................1............1........1.............
# ...................................1111111111111111111111111111111...................................
# .....................................................................................................
# .....................................................................................................
# ..................1.........................................1....................................1...
# .....................................................................................................
# 1.................................................................................................1..
# .......................................1...............1.............................................
# ...............................................1.....................................................
# .....................................................................................1...............
# ..........................................11................1........................................
# ....1................................................................................................
# 1...1.........................................1...........................1.....1....................
# .............................1.....1...........................................1.....................
# .1..................................................1............................................1...
# ...............1...........................................1...........................1.......1.....
# .....................................................................................................
# .......1.............................................................................................
# .....................................................................................................
# ...........................................1..................................1......................
# .....................1.............................................................................1.
# .................................................................1...................................
# .....................................................................................................
# ...1..1.....1........................................................................................
# .....................................................................................................
# ............................1........................................................................
# ......................................................1......................1.......................
# .........................................1...........................................................
# Parte 2 - Sobreposição não encontrada no segundo 7858
Módulo auxiliar#
from functools import total_ordering
def signal(x: int) -> int:
return 1 if x > 0 else -1 if x < 0 else 0
def string_para_lista(entrada: str) -> list[str]:
return [linha.strip() for linha in entrada.splitlines() if linha]
def string_para_matriz(entrada: str) -> list[list[str]]:
return [list(linha.strip()) for linha in entrada.splitlines() if linha]
def string_para_matriz_int(entrada: str, separador=" ") -> list[list[int]]:
return [
[int(l) for l in linha.split(separador)]
for linha in entrada.splitlines()
if linha
]
def le_arquivo(nome_arquivo: str) -> str:
with open(nome_arquivo, "r") as f:
return f.read()
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
)
def uma_lista_por_linha(nome_arquivo: str, separador=None) -> list[str]:
return [
[int(l) for l in linha.split(separador)]
for linha in le_arquivo_sem_linhas_em_branco(nome_arquivo).splitlines()
]
@total_ordering
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
def __le__(self, other):
return self.y < other.y or (self.y == other.y and self.x < other.x)
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):
if type(yx) is Vector2d:
return self.labirinto[yx.y][yx.x]
return self.labirinto[yx[0]][yx[1]]
Ler outros posts