Discussion on: Advent of Code 2020 Solution Megathread - Day 20: Jurassic Jigsaw

View post

Tough one today, I explain my solution more over at my blog post

I gave up trying to come up with a smart way to correctly orient the tiles. It's doable, you place one tile down, and then for each subsequent tile place down, you select one that is connected to one of the ones placed down (graph traversal), you just need to find the correct offset location, rotation, and flip given known edge match, but also take into consideration the absolute global rotation/flip of the tile that was placed into the grid. It should be a short function to take in the known edge match and orientation of the previous tile, it's similar to how you can chain affine transformation matrices, I just can't wrap my head around it right now.

Instead, I just brute-force the 32 possible positions each subsequent tile could be in relative to its pair which we just placed on the board (4 positions, each position 4 rotations 2 flip; still O(n) with number of tiles though, so still computes pretty much instantly). The rest is cross-correlation, as provided by scipy

import numpy as np
import networkx as nx
from itertools import product
from math import prod, sqrt
import re
from scipy.ndimage import correlate

data = open("input.txt").read().splitlines()
tiles = {int(re.sub(r"Tile (\d+):", r"\1", k)): np.array(v).view('U1').reshape(10, 10) for k, *v, _ in  np.array(data).reshape(-1, 12)}

edges = (
    (..., -1 ),
    (0  , ...),
    (...,  0 ),
    (-1 , ...),
)

borders = {}
graph = nx.Graph()
for tile_name, tile in tiles.items():
    for (i, j), f in product(edges, (1, -1)):
        border_id = "".join(tile[i, j][::f])

        if border_id in borders:
            graph.add_edge(borders[border_id], tile_name)
        else:
            borders[border_id] = tile_name

def orient(tile):
    for i in range(4):
        yield np.rot90(tile, i)
        yield np.fliplr(np.rot90(tile, i))

flip = {
    ...: ...,
    -1 :  0 ,
     0 : -1 ,
}

dire = {
    ...:  0 ,
    -1 :  1 ,
     0 : -1 ,
}

dim = int(sqrt(len(tiles)))

first_tile = next(iter(tiles))
result = np.full([2*dim+1, 2*dim+1, 10, 10], "")
result[dim][dim] = tiles[first_tile]
location = {first_tile: np.array([dim, dim])}

for left, right in nx.dfs_edges(graph, first_tile):
    if left in location:
        old, new = left, right
    else:
        old, new = right, left

    old_loc = location[old]
    old_tile = result[old_loc[0], old_loc[1]]
    for i, j in edges:
        for oriented_tile in orient(tiles[new]):
            if str(old_tile[i, j]) == str(oriented_tile[flip[i], flip[j]]):
                new_loc = old_loc + np.array([dire[i], dire[j]])
                result[new_loc[0], new_loc[1]] = oriented_tile
                location[new] = new_loc
                break

flat = np.swapaxes(result[:,:,1:-1,1:-1], 1, 2).reshape((2*dim+1)*8, -1)
flat_filtered  = flat[~(flat == '')].reshape(dim*8, -1)
image = (flat_filtered == "#").astype(int)

monster = (np.array(open("monster.txt").read().splitlines()).view('U1') == "#").reshape((3, -1)).astype(int)
monster_value = monster.sum()

total_monsters = sum((correlate(image, oriented_monster, mode="constant") == monster_value).sum() for oriented_monster in orient(monster))

print("remaining", image.sum() - total_monsters*monster_value)