Day 16: Reindeer Maze
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
Javascript
So my friend tells me my solution is close to Dijkstra but honestly I just tried what made sense until it worked. I originally wanted to just bruteforce it and get every single possible path explored but uh… Yeah that wasn’t gonna work, I terminated that one after 1B operations.
I created a class to store the state of the current path being explored, and basically just clone it, sending it in each direction (forward, 90 degrees, -90 degrees), then queue it up if it didn’t fail. Using a priority queue (array based) to store them, I inverted it for the second answer to reduce the memory footprint (though ultimately once I fixed the issue with the algorithm, which turned out to just be a less than or equal to that should have been a less than, I didn’t really need this).
Part two “only” took 45 seconds to run on my Thinkpad P14 Gen1.
My code was too powerful for Lemmy (or verbose): https://blocks.programming.dev/Zikeji/ae06ca1ca88649c99581eefce97a708e