pub fn y22d12(input: &str, part: u32) -> Option<u32>Expand description
The solution for the day twelve challenge.
We start by parsing the input which is provided as a string. The second
argument determines if we are looking for a solution from the start to the
end (part 1) or if we’re looking for the shortest valid starting position
(height a/0) to the end (part 2). To actually parse the input we
enumerate each character in each line to use as the coordinates. Based on
the character found we also assign the height: S, and a have height
0, E, and z have height 25, and every other letter has its height
in between. Additionally, we do some special handing for the S, E, and
a characters. When we find S and we’re on part 1 then we also need
to initialize the starting position; if we’re on part 2 then we instead
need to add it as a valid ending position. Similarly, when we find E on
part 1 we need to assign it as (the only) end position while in part 2
it gets assigned as the starting position. Finally, when we encounter a
during part 2 we need to add it as a valid ending position.
Once we have initialized our grid, we need to determine determine to which
nodes it’s possible to traverse from every other node. Keeping in mind the
trick above for part 2, we essentially look at every node in the grid.
Then we look in each of the four directions (unless we’re on the top or
left edge in which case we skip those two directions since we can’t have a
negative usize in rust) and if a node exists (meaning that we’re also not
on the other edge) then we check its height. In part one we check to see
if the height is less than or equal to the height of the current node plus
one. Using the trick above for part two we check if the height is greater
than or equal to the current node minus one. Any other nodes that are valid
paths from the original node get added to the original node’s edge list.
One last step as we are analyzing all of the nodes to determine the valid
neighbors: we check to see if we’re on the starting node or not. If we are
then we initialize the distances hash with 0 (Some(0)), if we are not
then we initialize the distance as None.
Finally, it’s time to actually perform the search. We use a
std::collections::VecDeque to keep track of the nodes that we need to
visit as it allows us to visit them in order that they are seen
(breadth-first) using the push_back() and pop_front() methods. While
there are still nodes left to visit we get the current distance associated
with the node that we are inspecting. If the node is in the list of end
positions then we’re done, just return the distance. Otherwise, if we
haven’t yet visited the node then we add it to our set of visited nodes and
then inspect all of its edges. If we also haven’t visited the edge then
we update the distances hash for the edge with the current distance plus
one and then add the edge to the list of nodes to visit. If we get through
all of the nodes reachable from the start and never find a valid ending
node then we instead need to return None.
§Example
// probably read this from the input file...
let mut input = "Sbcdef\nlkjihg\nmnopqr\nxwvuts\nyEzzzz\nzzzzza";
assert_eq!(y22d12(input, 1), Some(25));
assert_eq!(y22d12(input, 2), Some(25));