Advent of Code, día 20
Parte 1
Varias HORAS y un par de callejones sin salida me costó la primera parte de este reto. Empecé con una aproximación “clásica”: generar combinaciones y validarlas para montar el puzzle de “tiles”.
Parecía que el número de tiles era razonable (9 en el ejemplo 12x12 en la entrada). Parecía que — con algunas optimizaciones — sería factible comprobar las combinaciones. Parece razonable, ¿no?
NO
Con 3x3 tiles, el número de permutaciones posibles de las 9 piezas es 9! = 362.880. Pero además cada pieza se puede rotar (entre 0 y 3 veces) y voltear, por lo que tenemos 4x2=8 variaciones… por cada pieza, es decir, 8⁹ combinaciones. El total de opciones a comprobar — solo para el ejemplo reducido del enunciado sería de 48.704.929.136.640
La entrada real tiene 12 x 12 = 144 tiles. 144! es 5550293832739304789551054660550388117999982337982762871343070903773209740507907044212761943998894132603029642967578724274573160149321818341878907651093495984407926316593053871805976798524658790357488383743402086236160000000000000000000000000000000000 y eso sin multiplicar por 8¹⁴⁴
NOTA: Mas arriba he dicho que el número de variaciones por pieza es de 8, considerando 4 rotaciones y un volteo, pero en el enunciado nos habla de dos flips (x e y). En realidad flip-y es igual a flip-x + 2 rotaciones, por lo que el total de variaciones por cada tile es de 8. Un pequeño alivio.
Como decía, mi primer intento de resolver este reto fue por la aproximación clásica. Ya imaginaba que habría muchas combinaciones y que debía:
- optimizar la representación para poder evaluar las combinaciones muy rápidamente
- reducir el número de combinaciones a comprobar
Al parsear las tiles, decidí descartar todos los pixels de cada tile y quedarme simplemente con un número que representara cada uno de los 4 bordes, convirtiendo a decimal el número binario resultante de convertir los # en 1 y los . en 0. Mis tiles para la parte 1 tienen esta definición:
Tile = namedtuple('Tile', 'id borders')Y el código de parseo es este:
def border_to_int(border):
return int(border.replace('.', '0').replace('#', '1'), 2)def parse_tile(tile_src):
tile_lines = [
line.strip()
for line in tile_src.strip().split('\n')
]
id = int(re.match(r'Tile (\d+):', tile_lines[0]).group(1))
top_border = border_to_int(tile_lines[1])
bottom_border = border_to_int(tile_lines[-1])
left_border = border_to_int(
''.join(tile_lines[i][0] for i in range(1, len(tile_lines)))
)
right_border = border_to_int(
''.join(tile_lines[i][-1] for i in range(1, len(tile_lines)))
)
tile = Tile(
id,
(top_border, right_border, bottom_border, left_border)
)
return tile
Para generar todas las posibles ordenaciones de tiles, podríamos usar la funciónitertools.permutations() para hacer algo así:
for arrangement in permutations(tiles):
# check this arrangementPero para cada posible ordenación de tiles, tendríamos que probar las 8 posibles variaciones de cada tile, contra todas las demás (podemos recurrir a itertools.product()):
def gen_tile_variations(tile):
for i in range(4):
yield tile
yield flipx(tile)
tile = rotate(tile)def gen_tiles_variations(tiles):
return product(*[gen_tile_variations(tile) for tile in tiles])
Para generar todas las posibilidades, sería algo así:
for arrangement in permutations(tiles):
for variation in gen_tiles_variations(arrangement):
# check if variation is a valid puzzle arrangementPero no… por ahí no van los tiros. Después de un rato intentando optimizar saliendo de los bucles lo antes posible para probar menos combinaciones, la solución seguía siendo impracticablemente lenta.
Así que tocaba volver a pensar… lo dejé un rato, tenía invitados a comer… no podía sacar el dichoso reto de mi cabeza… ¿me pasas la ensalada? … llevamos unos días haciendo con las niñas un puzzle de 1000 piezas de Harry Potter… ¿queréis un café?… ¿habrá algún atajo? … las piezas de las esquinas … solo piden las 4 esquinas… ¡qué bueno está este turrón!… ¿podría encontrar las esquinas sin montar el puzzle? ¿podría identificar los bordes exteriores? ¿me servirá de algo la idea de convertir los bordes a números? … ¿ya os marcháis!?
Así que tras unas horas de maduración, me replanteé el problema. Tal vez no tenía que generar todas las combinaciones, ni siquiera encontrar la ordenación correcta del puzzle. ¿Serán únicos los números de bordes de cada pieza? Si lo fueran, podría meter todos los números que representan los bordes de las piezas en una lista y contar cuantas veces aparece cada número: los bordes interiores deberían aparecer 2 veces (una vez en cada una de las dos piezas que se unen en ese borde) y los bordes exteriores deberían aparecer 1 sola vez…. mmmm suena bien … pero… hay que tener en cuenta los volteos. Un borde 0001000111 que es el 71, si lo volteamos es 1110001000 que es el 904. Bueno, puedo simplemente considerar todos los bordes y sus volteados.
all_borders = (
[
border
for tile in tiles for border in tile.borders
] + [
flipped_side(border)
for tile in tiles for border in tile.borders
]
)Usando estas funciones auxiliares:
def pad(s):
return '0' * (10 - len(s)) + s
def flipped_side(n):
return int(pad(bin(n)[2:])[::-1], 2)bin(71) nos devuelve 0b1000111 así que tenemos que quitarle el 0b (con [2:]) y rellenar con 0 (pad) antes de darle la vuelta [::-1] y volver a convertirlo a decimal (int(n, 2))
Debemos comprobar que la suposición clave (los bordes no se repiten) es cierta:
assert len(all_borders) - len(set(all_borders)) == \
2 * (image_size * 4)Si tenemos 9 tiles, tendremos 9 x 4 = 36 bordes. Los bordes interiores se repiten (creemos) 2 veces, y los bordes exteriores solo deberían aparecer una vez:
len(all_borders) == 36 (4 por cada tile)
len(set(all_borders)) (pensamos que 12 + 12 repetidos = 24)
image_size * 4 == 12 (los bordes exteriores)36 - 24 debería ser = 12NOTA: multiplicamos * 2 porque estamos considerando los bordes y los volteados
La suposición resulta ser correcta para el ejemplo y para mi entrada: ¡SUFICIENTE! Encontrar las esquinas es tan sencillo como encontrar aquellas piezas que tienen dos bordes que solo aparecen una sola vez:
border_count = Counter(all_borders)
outer_borders = [
border for border, count in border_count.items() if count == 1
]# one tile is a corner if it has 2 outer borders
corners = [
tile.id
for tile in tiles
if 2 == len([
border
for border in tile.borders
if border in outer_borders
])
]
Y el resultado es el producto de los corners
return math.prod(corners)Ufff!!!! Unas cuantas horas de “maduración” mental hasta llegar a una solución practicable… ¿que nos espera en la parte 2?
Parte 2
A primera vista, más asequible, pero a la larga más trabajosa.
Se divide en 2 fases:
- Montar el puzzle
- Buscar el monstruo en el puzzle montado
Basándome en los hallazgos de la parte 1 y sabiendo que los bordes son únicos, montar el puzzle es relativamente sencillo:
- elegimos una esquina cualquiera
- miramos su borde derecho y buscamos la pieza que tiene el mismo borde (o su volteado). Solo debería haber una pieza y solo encaja en una posición
- vamos poniendo piezas a continuación siguiendo la misma técnica
- para empezar una nueva fila, miramos el borde inferior de la primera pieza de la fila anterior y buscamos una pieza con el borde coincidente
El código:
def arrange_puzzle(tiles, first_corner, outer_borders, image_size): # rotate first corner until outer borders are LEFT & TOP
while first_corner.borders[TOP] not in outer_borders or \
first_corner.borders[LEFT] not in outer_borders:
first_corner = rotate(first_corner) puzzle = [first_corner]
tiles.pop(first_corner.id) while tiles:
if len(puzzle) % image_size == 0: # beginning of row border_above = puzzle[-image_size].borders[BOTTOM]
next_tile = find_tile(tiles.values(), TOP, border_above) else: ## middle of row
border_left = puzzle[-1].borders[RIGHT]
next_tile = find_tile(tiles.values(), LEFT, border_left) puzzle.append(next_tile)
tiles.pop(next_tile.id)
return [
puzzle[i:i + image_size]
for i in range(0, len(puzzle), image_size)
]
Para encontrar la pieza correcta:
def find_tile(tiles, side, matching_border):
flipped_matching_border = flipped_side(matching_border)
for next_tile in tiles:
if matching_border not in next_tile.borders and \
flipped_matching_border not in next_tile.borders:
continue
for i in range(4):
if next_tile.borders[side] == matching_border:
return next_tile
next_tile = rotate(next_tile)
next_tile = flipx(next_tile)
for i in range(4):
if next_tile.borders[side] == matching_border:
return next_tile
next_tile = rotate(next_tile) assert False, 'not found'
Simplemente buscamos una pieza que contenga el borde que necesitamos emparejar… sabemos que hay una y solo una: buscamos tanto ese borde como su correspondiente volteado. Una vez encontrada, tenemos que encontrar la posición correcta. De nuevo sabemos que solo hay una. Probamos las 8 posiciones (4 rotaciones, y otras 4 rotaciones después de voltear) y la que coincida la devolvemos.
En esta función es importante registrar las transformaciones que aplicamos a las piezas. Recordemos que estamos trabajando con una representación simplificada (id, bordes) pero luego tendremos que aplicar la misma secuencia de transformaciones a los “pixels” de la pieza para reconstruir la “imagen”. Para esto he añadido un nuevo campo ops a las Tile, que vamos manteniendo en las funciones rotate() y flipx().
Tile = namedtuple('Tile', 'id borders ops')def rotate(tile):
return Tile(
tile.id,
(
tile.borders[RIGHT],
flipped_side(tile.borders[BOTTOM]),
tile.borders[LEFT],
flipped_side(tile.borders[TOP])
),
tile.ops + ('rotate',),
)
assert rotate(Tile(1, (1, 2, 3, 4), ops=tuple())) == \
Tile(1, (2, 768, 4, 512), ops=('rotate',))
def flipx(tile):
return Tile(
tile.id,
(
flipped_side(tile.borders[TOP]),
tile.borders[LEFT],
flipped_side(tile.borders[BOTTOM]),
tile.borders[RIGHT]
),
tile.ops + ('flipx',),
)
assert flipx(Tile(1, (1, 2, 3, 4), ops=tuple())) == \
Tile(
1,
(int('1000000000', 2), 4, int('1100000000', 2), 2),
ops=('flipx',)
)
Con esto ya sabemos la posición de cada pieza en el puzzle y su orientación. Para el ejemplo tendríamos algo así (en negrita el id de la pieza y con el número de borde)
564 | 231 | 702
587 1951 318 | 318 2311 616 | 616 3079 264
710 | 210 | 184
----------------------+----------------------+--------------------
710 | 210 | 184
962 2729 9 | 9 1427 348 | 348 2473 481
85 | 948 | 399
----------------------+----------------------+--------------------
85 | 948 | 399
78 2971 689 | 689 1489 288 | 288 1171 902
161 | 848 | 96 Ahora, construimos la imagen tomando los 8x8 pixels centrales de cada pieza y aplicando las mismas transformaciones que hemos registrado al “montar el puzzle”:
def parse_tile_pixels(tile_src, tiles):
tile_lines = [
line.strip() for line in tile_src.strip().split('\n')
]
id = int(re.match(r'Tile (\d+):', tile_lines[0]).group(1))
rows = tile_lines[1:]
rows = [row[1:-1] for row in rows[1:-1]]
for op in tiles[id].ops:
if op == 'rotate':
rows = pixels_rotate(rows)
elif op == 'flipx':
rows = pixels_flipx(rows)
return (id, rows)Las funciones pixels_rotate() y pixels_flipx() aplican la transformación a todos los “pixels” de la imagen:
def pixels_flipx(rows):
return [row[::-1] for row in rows]
assert pixels_flipx([
'123',
'456',
'789'
]) == [
'321',
'654',
'987'
]
def pixels_rotate(rows):
return [
''.join(new_row)
for new_row in zip(*pixels_flipx(rows))
]
assert pixels_rotate([
'123',
'456',
'789'
]) == [
'369',
'258',
'147'
]Montamos todas las piezas transformadas en una matriz “gigante”:
pixels = []
for tile_row in puzzle:
for pixel_rows in zip(*(
tiles_pixels[tile.id]
for tile in tile_row
)):
pixels.append([
pixel
for row in pixel_rows for pixel in row
])Y buscamos el monstruo. En lugar de girar y voltear la imagen, podemos girar y voltear el monstruo (las mismas 8 variaciones):
monsters = [
MONSTER,
pixels_rotate(MONSTER),
pixels_rotate(pixels_rotate(MONSTER)),
pixels_rotate(pixels_rotate(pixels_rotate(MONSTER)))
]
monsters += [pixels_flipx(monster) for monster in monsters]Buscamos y reemplazamos el monstruo:
for monster in monsters:
found_monsters = replace_monster(pixels, monster)
if found_monsters:
breakUsando estas funciones auxiliares:
def replace_one_monster(pixels, i, j, monster,
monster_height, monster_width):
for k in range(0, monster_height):
for l in range(0, monster_width):
if monster[k][l] == '#':
if pixels[i + k][j + l] != '#':
return 0
# we found one, let's replace it
print(f'found monster on {i}, {j}')
for k in range(0, monster_height):
for l in range(0, monster_width):
if monster[k][l] == '#':
pixels[i + k][j + l] = 'O'
return 1
def replace_monster(pixels, monster):
monster_height = len(monster)
monster_width = len(monster[0])
found_monsters = 0
for i in range(0, len(pixels) - monster_height):
for j in range(0, len(pixels[i]) - monster_width):
found_monsters += replace_one_monster(
pixels, i, j,
monster, monster_height, monster_width
)
return found_monstersY… por fin… podemos contar los ‘#’ que quedan en la imagen para obtener la respuesta que nos piden…
return ''.join(''.join(row) for row in pixels).count('#')Resumiendo… una primera parte de “idea feliz” y poco código y una segunda parte de mucho código — no demasiado complicado — pero largo largo.
El código completo (+ de 275 líneas) aquí: https://github.com/jabadia/adventOfCode2020/blob/main/d20/d20p2.py
