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)
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
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...
I found the algorithmic problem and it now arranges all the tiles in about one second. The code is simpler too!
huh today was hard! Here is my video walkthrough as usual, although it's only for part 1 ;)