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.