Expand description
Advent of Code 2022 Day 12: https://adventofcode.com/2022/day/12
When first reading the challenge prompt I saw “find the shortest path” and
immediately thought of Dijkstra’s
algorithm but as I
was re-familiarizing myself with it I got confused by the weights in the
algorithm because the challenge prompt essentially defines that the weight
of all edges are 1. So, I instead started implementing a brute-force
depth-first search that worked for the small sample input that was
provided, but took way too long to run on the actual input. I decided to
take another look at Dijkstra’s algorithm because I must have been missing
something. After rewriting my mess, I was able to solve part one in a
reasonable amount of time, but the additional challenge in part two took
my solution more than five minutes to run even if it ultimately returned
the correct answer. This caused me to do some reading on the Advent of Code
subreddit, and I discovered two things: firstly, that because all of the
weights were equal a simple breadth-first
search would be
sufficient to solve the problem, and secondly, that a neat trick to solve
part two was to start at the end and search backwards to find a suitable
start point (as opposed to looping through all of the valid starting points
and computing the shortest path to the end for all of them and then taking
the shortest of those as I was currently doing). I switched my solution to
use these two strategies and now it runs significantly faster.
Functions§
- The solution for the day twelve challenge.