Advent of code 2024 - Dia 12 de 25
Conteúdo
O décimo segundo dia do Advent of Code foi ontem 12/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 e Dia 11.
Classifiquei o décimo segundo problema como fácil (parte 1) e médio (parte 2).
Dicas#
- Outro problema com labirintos ou mapas de caracteres.
- Você pode construir uma zona, procurando por elementos idênticos nas posições acima, abaixo, a esquerda e a direita do nó corrente.
- Tente visualizar o mapa de caracteres como uma matriz. Agora imagine cada elemento como um nó de um grafo, conectado aos seus vizinhos.
- Lembre-se de marcar os nós já visitados
- Você pode construir uma cerca sempre que o elemento na direção sendo explorada for diferente do elemento atual.
- Na parte 1, a área é igual a quantidade de elementos na mesma zona. Para calcular o perímetro, você precisa saber quantas barreiras colocou em cada posição.
- A parte 2 traz uma forma diferente de calcular o preço, mas o problema é bem parecido com a parte 1. Agora, você precisa olhar todas as barreiras da zona e verificar quantas são linhas e colunas contíguas.
- Você pode organizar as linhas pela coordenada y de suas cercas. Linhas contíguas terão o mesmo valor na coordenada y. Se ordenadas adequadamente, o segmento seguinte será o próximo com uma posição em x apenas 1 elemento maior que a anterior. Desta forma, você consegue contar as linhas contíguas.
- As colunas seguem o mesmo princípio, mas agora você precisa ordenar as cercas pela coordenada x. Da mesma forma, uma coluna é contígua se o próximo segmento está na linha seguinte.
- É mais fácil organizar os dados se as cercas horizontais e verticais estiverem separadas.
Quanto de Python você precisa saber?#
Os capítulos se referem ao meu livro Introdução à Programação com Python.
- Listas, dicionários - Capítulo 6
- Strings - Capítulo 7
- Funções recursivas - Capítulo 8
- Classes - Capítulo 10
- A parte 2 exige um pouco de criatividade para detectar as linhas e colunas contíguas.
Resposta#
A resposta da parte 1 pode ser calculada pala classe Jardim. A parte 2 é implementada pela classe JardimParte2, que é muito semelhante a primeira classe, mas adiciona a complexidade de saber a direção das cercas, contar linhas e colunas. Com um pouco de esforço, você poderia usar a classe JardimParte2 para resolver ambas partes, mas creio ser mais interessante mostrar uma solução simples e depois uma mais complexa.
Várias funções de desenho e dump do labirinto foram implementadas, você pode gravar o resultado das zonas com as barreiras em disco se quiser.
import sys
import math
from auxiliares import (
string_para_lista,
Vector2d,
Labirinto,
le_arquivo_sem_linhas_em_branco,
)
ENTRADA = """
AAAA
BBCD
BBCC
EEEC
"""
ENTRADA_TESTE_2 = """
OOOOO
OXOXO
OOOOO
OXOXO
OOOOO
"""
ENTRADA_TESTE_3 = """
RRRRIICCFF
RRRRIICCCF
VVRRRCCFFF
VVRCCCJFFF
VVVVCJJCFE
VVIVCCJJEE
VVIIICJJEE
MIIIIIJJEE
MIIISIJEEE
MMMISSJEEE
"""
ENTRADA_TESTE_PARTE_2_1 = """
EEEEE
EXXXX
EEEEE
EXXXX
EEEEE
"""
ENTRADA_TESTE_PARTE_2_2 = """
AAAAAA
AAABBA
AAABBA
ABBAAA
ABBAAA
AAAAAA
"""
class Jardim(Labirinto):
DIREÇÕES = [Vector2d(0, 1), Vector2d(1, 0), Vector2d(0, -1), Vector2d(-1, 0)]
def cria_zonas(self):
visitados = set()
preço = 0
for y, linha in enumerate(self.labirinto):
for x, valor in enumerate(linha):
if (corrente := Vector2d(y, x)) in visitados:
continue
visitados.add(corrente)
área_perímetro = Vector2d(1, 0)
for direção in self.DIREÇÕES:
área_perímetro += self.visita(
valor,
corrente + direção,
visitados,
)
preço += área_perímetro.x * área_perímetro.y
return preço
def visita(
self, zona: str, posição: Vector2d, visitados: set[Vector2d]
) -> Vector2d:
área_perímetro = Vector2d(0, 0)
válida = self.posição_válida(posição)
if not válida or self[posição] != zona:
área_perímetro += Vector2d(0, 1)
elif válida and self[posição] == zona and posição not in visitados:
área_perímetro += Vector2d(1, 0)
visitados.add(posição)
for direção in self.DIREÇÕES:
área_perímetro += self.visita(
zona,
posição + direção,
visitados,
)
return área_perímetro
class Cerca:
def __init__(self, posição: Vector2d, direção: Vector2d):
self.posição = posição
self.direção = direção
def __hash__(self):
return hash(
f"{self.posição.x},{self.posição.y},{self.direção.x},{self.direção.y}"
)
def __str__(self):
return f"{self.posição} D:{self.direção}"
def __repr__(self):
return f"<Cerca {self}>"
def sort_key_x(self, max):
return f"{self.direção.x:0{max}}{self.direção.y:0{max}}{self.posição.x:0{max}}{self.posição.y:0{max}}"
def sort_key_y(self, max):
return f"{self.direção.x:0{max}}{self.direção.y:0{max}}{self.posição.y:0{max}}{self.posição.x:0{max}}"
class JardimParte2(Jardim):
def __init__(self, labirinto: list[str]):
super().__init__(labirinto)
self.max = int(math.log10(max(self.max_x, self.max_y))) + 2
def linhas(self, cercas_horizontais: set[Vector2d]):
linhas = 1
cercas = sorted(list(cercas_horizontais), key=lambda c: c.sort_key_y(self.max))
linha = cercas[0]
for i in range(1, len(cercas)):
if (
cercas[i].posição.y != linha.posição.y
or cercas[i].posição.x - linha.posição.x > 1
or linha.direção != cercas[i].direção
):
linhas += 1
linha = cercas[i]
return linhas
def colunas(self, cercas_verticais: set[Vector2d]):
colunas = 1
cercas = sorted(
list(cercas_verticais),
key=lambda c: c.sort_key_x(self.max),
)
coluna = cercas[0]
for i in range(1, len(cercas)):
if (
cercas[i].posição.x != coluna.posição.x
or cercas[i].posição.y - coluna.posição.y > 1
or coluna.direção != cercas[i].direção
):
colunas += 1
coluna = cercas[i]
return colunas
def cria_zonas(self):
visitados = set()
preço = 0
for y, linha in enumerate(self.labirinto):
for x, valor in enumerate(linha):
if (corrente := Vector2d(y, x)) in visitados:
continue
visitados.add(corrente)
cercas_horizontais = set()
cercas_verticais = set()
área_perímetro = Vector2d(1, 0)
for direção in self.DIREÇÕES:
área_perímetro += self.visita(
valor,
corrente + direção,
visitados,
cercas_horizontais,
cercas_verticais,
direção,
)
preço += área_perímetro.y * (
self.colunas(cercas_verticais) + self.linhas(cercas_horizontais)
)
return preço
def visita(
self,
zona: str,
posição: Vector2d,
visitados: set[Vector2d],
cercas_horizontais: set[Vector2d],
cercas_verticais: set[Vector2d],
direção: Vector2d,
) -> Vector2d:
área_perímetro = Vector2d(0, 0)
válida = self.posição_válida(posição)
if not válida or self[posição] != zona:
área_perímetro += Vector2d(0, 1)
if direção in [Vector2d(0, 1), Vector2d(0, -1)]:
cercas_verticais.add(Cerca(posição, direção))
else:
cercas_horizontais.add(Cerca(posição, direção))
elif válida and self[posição] == zona and posição not in visitados:
área_perímetro += Vector2d(1, 0)
visitados.add(posição)
for direção in self.DIREÇÕES:
área_perímetro += self.visita(
zona,
posição + direção,
visitados,
cercas_horizontais,
cercas_verticais,
direção,
)
return área_perímetro
def desenhe(self):
self.my = 3
self.mx = 3
self.desenho = []
for _ in range(self.my * (self.max_y)):
self.desenho.append([" "] * (self.mx * (self.max_x)))
for y, linha in enumerate(self.labirinto):
for x, valor in enumerate(linha):
self.desenho[y * self.my + 1][x * self.mx + 1] = valor
def desenhe_cercas(self, cercas: set[Cerca]):
for cerca in cercas:
py = cerca.posição.y - cerca.direção.y
px = cerca.posição.x - cerca.direção.x
cx = (px * self.mx + 1) + cerca.direção.x
cy = (py * self.my + 1) + cerca.direção.y
self.desenho[cy][cx] = (
"|" if cerca.direção in [Vector2d(0, 1), Vector2d(0, -1)] else "―"
)
def dump_desenho(self, output=sys.stdout):
for linha in self.desenho:
print("".join(linha), file=output)
jardim = Jardim(string_para_lista(ENTRADA))
preço = jardim.cria_zonas()
print("Preço - entrada parte 1 - teste 1:", preço)
assert preço == 140
jardim = Jardim(string_para_lista(ENTRADA_TESTE_2))
preço = jardim.cria_zonas()
print("Preço - entrada parte 1 - teste 2:", preço)
assert preço == 772
jardim = Jardim(string_para_lista(ENTRADA_TESTE_3))
preço = jardim.cria_zonas()
print("Preço - entrada parte 1 - teste 3:", preço)
assert preço == 1930
entrada_parte_1 = le_arquivo_sem_linhas_em_branco("12/input.txt")
jardim = Jardim(string_para_lista(entrada_parte_1))
preço = jardim.cria_zonas()
print("Preço - entrada parte 1:", preço)
assert preço == 1396298
# Parte 2
print()
jardim = JardimParte2(string_para_lista(ENTRADA))
preço = jardim.cria_zonas()
print("Preço - entrada - parte 2 - teste 1:", preço)
assert preço == 80
jardim = JardimParte2(string_para_lista(ENTRADA_TESTE_2))
preço = jardim.cria_zonas()
print("Preço - entrada - parte 2 - teste 2:", preço)
assert preço == 436
jardim = JardimParte2(string_para_lista(ENTRADA_TESTE_PARTE_2_1))
preço = jardim.cria_zonas()
print("Preço - entrada - parte 2 - teste 2_1:", preço)
assert preço == 236
jardim = JardimParte2(string_para_lista(ENTRADA_TESTE_PARTE_2_2))
preço = jardim.cria_zonas()
print("Preço - entrada - parte 2 - teste 2_2:", preço)
assert preço == 368
jardim = JardimParte2(string_para_lista(ENTRADA_TESTE_3))
preço = jardim.cria_zonas()
print("Preço - entrada - parte 2 - teste 3:", preço)
assert preço == 1206
jardim = JardimParte2(string_para_lista(entrada_parte_1))
preço = jardim.cria_zonas()
print("Preço - entrada - parte 2:", preço)
assert preço == 853588
Módulo Auxiliar#
As partes que não mudaram foram omitidas.
from .arquivos import uma_lista_por_linha, le_arquivo_sem_linhas_em_branco
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
]
@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