Python Solution for 2021 Advent of Code - Day 15 - Part 1 - Chiton

Solution to only part one of 2021's Advent of Code's Day 15's problem. Not a great solution by any means, but I got the answer and am learning Python better practices in the meantime.

Bradley Sward is currently an Associate Professor at the College of DuPage in suburban Chicago, Illinois. He has earned a Masters degree in Software Engineering from DePaul University, a Masters degree in Computer Science from the University of Illinois at Springfield, and two Bachelors degrees in Computer Science and Molecular Biology from Benedictine University. Prior to teaching, Bradley worked for five years in the field of casino gaming on a variety of video slot machine and poker games. The Village People have been permanently etched into his brain.

[chookingvid]

The traditional implementation of Dijkstra's algorithm does not require storing multiple paths. It only involves storing each point's neighbor that must be passed through to get to it via the lowest cost route. This enables reconstructing the whole route if you need it, but it's not needed at all for either part of this exercise. A proper implementation takes only about 2 or 3 seconds to run for part 2.

[sem]

You can definitely speed thing up if you don't keep track of the paths (we only want one path with the lowest risk anyway).
(you do not need to deep copy the path if you don't keep track of it :) )
Also, take a look at heapq or priorityqueue, those data types are always sorted (if you use uses tuples inside it will first sort based on the first value, then the second, etc.).
You could also use something like a* if you're really stuck (adding the estimated future risks to the actual risk really helped my solution).
If you're curious my solution (in Python) to the first part takes around a second, and the second part around 5 seconds (there is probably some even faster way though).
(btw there is a typo in the video title)