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

#adventofcode #challenge

Five more days! Five more days! Five more days!

The Puzzle

In today’s puzzle, we're looking for Nessie! Well, we're rotating, flipping, and reassembling tiles of pixels on the off-chance that we actually see something in what can only be described as a complexity nightmare. I'm not really sure how this one is going to get done without ridiculous amounts of looping, but that's why we get paid the big bucks!

The Leaderboards

As always, this is the spot where I’ll plug any leaderboard codes shared from the community.

Ryan's Leaderboard: 224198-25048a19

If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.

Yesterday’s Languages

Updated 07:33AM 12/20/2020 PST.

Language	Count
Haskell	2
JavaScript	1
Ruby	1
Python	1
Rust	1

Merry Coding!

Top comments (4)

Yuan Gao • Dec 21 '20 • Edited

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)

Neil Gall • Dec 22 '20

I got part 1 done but it took me ages to get the insight that it only needs the edge tiles arranged. Even then it takes 39 seconds to run which is too long and will never work for part 2. I must be missing some fundamental insight that makes the search space smaller.

github.com/neilgall/advent-of-code...