Advent of Code 2022 Day 12 Solve

Recording of me solving day 12 of Advent of Code 2022 in Python. Finished rank #23 and #29 for each part. Finally up to date on uploads!

Finish times:
Part 1: 5:08
Part 2: 6:54 (+1:46)

Finally a day where I leaderboarded on both parts again! Was a little worried I had lost my touch recently. Definitely going to be a grind to get anywhere near my previous global leaderboard rank though :P

Today was a standard-ish grid BFS, where part 2's twist was that any one of multiple starting locations was valid. IMO, the "typical" thing to do there would be to reverse the direction of the search, but I decided to just re-run the search from every possible starting location instead because I thought it'd be faster to write. I still think this is probably true? There is *another* solution though, where you just start the search simultaneously from all starting locations. When I TA'd for an algorithms course in college I liked to explain this as creating a new starting node and connecting it with 0-weight edges to all the simultaneous starting nodes to simulate that, but in code for this question it's much easier since we can just add all starting locations to the BFS queue - probably would've seen some rank improvement if I did that instead, since I actually think in hindsight that would've been the fastest to write too.

I mentioned it at the end of the video (around 21:10), but I've kinda been slacking on properly explaining things after the question since from analytics it didn't look like many people were watching it. If it'd be helpful to hear explanations (especially for the harder days) let me know in the comments and I can start doing them again.

0:00 - Part 1
5:14 - Part 2
7:00 - Explanation

[Olegtnt]

could you please explain the deque class and what's going on? thanks!

I solved both Part 1 and Part 2 backwards myself (starting from S), but didn't get the forward solution

[stevepoper]

I do have a question. In your

_if (cx, cy) == (tx, ty)_

line 39. How do you know that it will give the lowest distance. Wouldn't you have to explore all the points to know if there's a path with a lower distance?

[alaminsakib]

Could we have done this using DFS? If so, how would you implement it?