Advent of Code 2020 Day 20

I’m still playing catchup…

Part 1

I can characterize the edges by converting them into binary, e.g. “#..#” -> “1001” -> 9, and doing the same with the reverse. There’s 2^10 = 1024 possible edges, so I’d expect some false matches with the 12x12 (=144, with reverses =288) problem, but maybe we can narrow that down a bit:

1. All inside tiles need to have at least one other match for every edge.
2. According to the problem statement, “the outermost edges won’t line up with any other tiles.”

Well wait, statement 2 is all we need for part 1: find the four tiles that only have two matching edges. So after reading in all the tiles and characterizing the edges, I’ll combine the edges into a single list:

    edges = reduce(append!, [[x.edges;x.redges] for x in tiles])

Then we just need to count the number of matches for each edge (note that we don’t need to check the reverse edges, since the result is the same forward or reverse - we’d just end up with a flipped image in one case). If there’s two edges with no other matches, then it’s a corner tile.

    for t in tiles
        matches = [count(x->x==e, edges) for e in t.edges]
        if count(x->x==1, matches) == 2
            push!(corners,t.id)
        end
    end

Part 2

Unsurprisingly, now we do need to actually combine the tiles. As with a jigsaw puzzle, we can start by anchoring the corners, except unlike a puzzle, our tiles can be upside-down.

to be continued…

I’ll start by adding the tile itself to the Struct, as a 8x8 BitArray.