Nik from the Wolfram Institute did a full series for AoC on our YouTube channel! You can watch it here: https://www.youtube.com/playlist?list=PLM_MgbAF1uYJ3ewejaW9XQHi4ZJmi8mWV

I'm not that interested in the problems, it was probably a mistake to mention the application. I'm more interested in discovering why WL has pathological performance issues with adding weighted edges to only moderately large graphs.

But since you ask the problem is Day 16. I'm aware this is far from a great way to solve it, but I build a grid-graph from the input. I then delete all the vertices representing # (walls). Then in order to account for the cost of turning I identify all the vertices where a turn might take place, delete those and reconnect their neighbours with weighted edges at account for the costs appropriately. It does produce the correct answer since I did run it long enough to complete one time. Sadly I didn't realise part 2 of Day 16 would require me to regenerate the graph in order to answer another question about it.

I can upload a notebook with a test case but it'll take a little time prepare a minimal test case so that'll have to wait until tomorrow now.

Thank you for providing your code. I ran it with my data and it finds the correct answer and completes almost instantaneously. Bravo!

I mentioned before that in attempting to find a solution that ran in a sensible amount of time I had changed my code so that rather than adding the new edges and then setting their edge weights one by one I instead: Extract the existing edges into a list, and add my new edges specified thus Annotation[UndirectedEdge[v1,v2],EdgeWeight->1002] and then build a new graph using the combined set of edges. So I have something like:-

newGraph = Graph[Join[EdgeList[oldGraph], newEdges /. {e,w}->Annotation[e,EdgeWeight->w] ]

That was still taking a super-long time even though it was then only 1 function call.

So I compared my program with yours. The only thing I changed was that I supplied the edge weights for my added edges using the other way of doing it:

ew = newEdges /. {e,w}-> e->w; newGraph = Graph[Join[EdgeList[oldGraph], newEdges[[All,1]] ], EdgeWeight -> ew];

And do you know what.... This runs almost as fast as your solution.

Why should two different ways of creating a graph with weighted edges take vastly different times to run? The documentation indicates that both approaches to specifying edge weights are equally valid and doesn't mention anything about runtime costs. I should probably report this as a bug, but I only have a Home Edition licence so I don't have support access.