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
I think you’re adding too many neighbours to the prev_nodes here potentially. At the time you explore the edge, you’re not yet sure if the path to the edge’s target via the current node will be the cheapest.
Good catch! IIRC, only when a node is selected from the min heap can we guarantee that the cost to that node will not go any lower. This definitely seems like a bug, but I still got the correct answer for the samples and my input somehow ¯\_(ツ)_/¯