My priority queue comes in handy, although I modified it to be a bit quicker.

This one allowed me to break out my custom Priority Queue. And to make it a bit faster!

Go does provide a heap, but it's "general" but not "generic". Software developers know what I mean. But general would mean that it can be used on whatever you need it to, generic in most cases means the types can be defined at compile time, and there would be no casting necessary, since the generic type is replaced by the actual type. So it's better. :)

My old priority queue would insert items linearly. So it would get the value for the item being inserted, then loops through all the items starting from the front, and find when the new value is larger than the item in the array. It would then insert the new item there.

Priority queue is all about keeping the queue sorted, and the value is the priority. Typically high priority should take precedence, but in my implementation, the lower value takes precedence. For day 17 of advent of code, we wanted to prioritize the lower value anyway, so it worked out. If we want to prioritize the higher value, there are ways to do that, like multiple it by -1. Software is never finished so I could easily change it to reverse the values when the queue is created. But anyway, back to my optimization.

So of course, the good inexpensive way to insert an item into a sorted list (keeping it sorted), is a binary search. You start at the mid point of the array and compare the value to the value in the middle. If it's lower than that value, then you search the lower half of the array, doing the same thing. Repeat until you find one index it fits in.

The benefit of this is, if there's 1000 items, if you're inserting an item that's like 2 less than the last value in the array, the linear approach takes 998 iterations, while the binary search takes like 10 steps. log2(N) or 9.96578428466 for 1000 items. I've forgotten all the math but I manually counted it out and wanted to double check. Having a computer science degree, I of course have known about "Big O Notation" for about 24 years, but all the math is gone. Constant time lookup is the best, but if you can get to log time, you're doing ok.

This problem takes a bit longer to run. I am not narrowing the problem space enough. But the logic is correct. The update did cut the time down from 30 seconds to 26 seconds. The linear insert wasn't the bottleneck, but it certainly wasn't helping. I will continue to look for the bottleneck, but I at least know that it won't be in the priority queue now.

Happy Coding!