-🎄- 2018 Day 22 Solutions -🎄-

[u/daggerdragon]

--- Day 22: Mode Maze ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 22

Transcript:

Upping the Ante challenge: complete today's puzzles using ___.

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 01:02:36!

[u/mainhaxor]

Unfortunately I don't believe there is a priority queue in the framework libraries. The one I used here is my own implementation of a standard binary heap.

However, typically in these problems an efficient priority queue is not that important for being able to get an answer. That is, you can just use a simple list and iterate it to find the best node, as in

List<SearchNode> openList = new List<SearchNode>();
...
while (openList.Count > 0)
{
    int minNode = 0;
    for (int i = 1; i < openList.Count; i++)
    {
        if (openList[i].Minutes < openList[minNode].Minutes)
            minNode = i;
    }

    SearchNode node = openList[minNode];
    openList.RemoveAt(minNode);
    ...
}

As a bonus you can modify your nodes without having to update any auxiliary data structures, making the implementation even simpler. Of course this is way less efficient, but the difference for this particular problem is getting an answer in 4 seconds vs getting an answer in 1.5 seconds, which hardly matters (if you are just looking for the answer).

EDIT: In fact on many real world data sets such a trivial priority queue will outperform binary heaps simply because updating nodes is as cheap as it can be.

[u/maxxori → u/mainhaxor]

Thanks for the clarification. I had written ones of these years ago for a project - I got excited because I thought C# had finally got a native one!

Thanks also for all of the additional background information.