AoC 2020 - Day 20: Jurassic Jigsaw

OK, this was a marathon.
I spent a huge amount of time on it: to get it, then to make it faster, and finally to make it better.

My initial assumption was to solve everything in one go: find the connected pieces, and rotate/flip them in the correct position.
That was wrong. Eventually, I got it working, but it took a huge amount of time, and the algorithm was very slow. Not only: since positioning on the first part was not reliable, I had to introduce a “fixing” phase – but it was all just by accretion, and not really maintainable.

Interestingly enough, once I had a working solution, I realized a much better approach. It was simpler to implement, with less code, less debugging, and less time.
In this new approach, I follow two steps: first, connect the pieces, and then flip/rotate them. Essentially, very similar to what was done before, but explicit. This led to various simplifications (especially in the first part), and a substantial increase in readability and performance.

More in detail, the first parts have two moments:

  • Connect all tiles
  • Corners are the only tiles with two neighbors

As well, the second part: The idea for the second part:

  • Generate the image starting from the corner
  • The corner must be aligned so that it’s top-right
  • Move in a “serpentine” pattern and rotate/flip each tile so that it fits the previous one and the one above (it looks like we need two tiles to block all degrees of freedom)
  • Use set inclusion to check the dragon presence (the set of the translate dragon dots must be contained in the hash dots)

I have still an unknown: why do I have to rotate/flip the first tile, to be in that position? If I do not do that, I get a map that looks valid, but does not yield results. I suspect I had some bug in determining the direction for scrolling the map; anyhow, the current approach (fixed directions) seems to bypass that issue, without side effects.

Anyways, I have already spent enough some time to refine the code and improve its quality. I am not 100% satisfied with the code as it is now, and its unknowns; however, it is also important to set a limit – it works for my input, it seems be already readable enough, so be it.