Advent of Code 2022 - Day 12
Tags: rust, programming, adventofcode
Published: 2022-12-14 02:16:00

---
title: Advent of Code 2022 - Day 12
published: true
date: 2022-12-12 00:00:00 UTC
tags: rust, programming, adventofcode
canonical_url: https://www.ericburden.work/blog/2022/12/12/advent-of-code-2022-day-12/
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fbx1wys8oyot5dboh2n2.png
---

It’s that time of year again! Just like last year, I’ll be posting my solutions to the [Advent of Code](https://adventofcode.com/) puzzles. This year, I’ll be solving the puzzles in [Rust](https://www.rust-lang.org/). I’ll post my solutions and code to [GitHub](https://github.com/ericwburden/advent_of_code_2022) as well. After finishing last year (and 2015-2019) in [Julia](https://julialang.org/), I needed to spend some time with Rust again! If you haven’t given AoC a try, I encourage you to do so along with me!

# Day 12 - Hill Climbing Algorithm

Find the problem description [HERE](https://adventofcode.com/2022/day/12).

## The Input - A Rough Patch

No `nom` parsing for us today! We’re faced with a grid of lowercase letters, so line and character splitting will be plenty. The fun part of input prep today will be converting that grid into a data structure that we can more easily use the inevitable graph algorithms on.

```rust
/// Represents a hill on the map. Wraps the hill height and indicates
/// if it's a start, end, or just plain old hill.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum Hill {
    Start(u8),
    End(u8),
    Hill(u8),
}

/// Convert characters to `Hill`s
impl From<char> for Hill {
    fn from(value: char) -> Self {
        match value {
            'S' => Hill::Start(0),
            'E' => Hill::End(25),
            c if c.is_ascii_lowercase() => Hill::Hill(value as u8 - b'a'),
            _ => unreachable!(),
        }
    }
}

impl Hill {
    // Pull the height from a hill
    fn height(&self) -> u8 {
        match self {
            Hill::Start(h) => *h,
            Hill::End(h) => *h,
            Hill::Hill(h) => *h,
        }
    }

    // Indicate whether the `other` hill can be reached from the
    // current hill, considering elevation only.
    fn can_reach(&self, other: &Hill) -> bool {
        // From the current hill, we can reach hills that are at most one
        // elevation level above the hill we're on.
        other.height().saturating_sub(self.height()) <= 1
    }
}

// Type alias we'll use to refer to hills that can be reached from the current hill
type Neighbors = [Option<(usize, usize)>; 4];

/// Represents a map of all the hills in the area. Includes the two-dimensional
/// listing of hills, the positions of the starting hill and the end hill, and
/// a hashmap that will serve as an adjacency list for hills and the neighbors
/// that can be reached from them.
struct HillMap {
    hills: Vec<Vec<Hill>>,
    graph: HashMap<(usize, usize), Neighbors>,
    start_at: (usize, usize),
    end_at: (usize, usize),
}

/// Convert the input string into a `HillMap`.
impl From<&str> for HillMap {
    fn from(value: &str) -> Self {
        // Start by building up the 2D vector of hills, in the same shape as the
        // characters in the input.
        let hills: Vec<Vec<_>> = value
            .lines()
            .map(|row| row.chars().map(Hill::from).collect())
            .collect();

        // Now we convert the vector of hills into a mapping we can use for a
        // nice graph algorithm (more easily). We'll precompute which neighbors
        // are reachable here to save processing later.
        let mut graph = HashMap::new();

        // Make sure we know the dimensions of the grid
        let last_row = hills.len().saturating_sub(1);
        let last_col = hills
            .first()
            .map(|r| r.len())
            .unwrap_or_default()
            .saturating_sub(1);

        // Prepare to identify the start and end locations
        let mut start_at = (0, 0);
        let mut end_at = (0, 0);

        // For each row and column in our vector of hills...
        for (row_idx, row) in hills.iter().enumerate() {
            for (col_idx, hill) in row.iter().enumerate() {
                // Create and fill in the array of neighbors in order of direction
                // from up, left, down, and right. I'm using arrays here because I
                // believe in my heart that arrays are more efficient that vectors,
                // and I won't be convinced otherwise! (today) We're doing our
                // bounds checking here as well, just to save on possible edge cases
                // later on.
                let mut neighbors = [None; 4];
                if row_idx > 0 && hill.can_reach(&hills[row_idx - 1][col_idx]) {
                    neighbors[0] = Some((row_idx - 1, col_idx));
                }
                if col_idx > 0 && hill.can_reach(&hills[row_idx][col_idx - 1]) {
                    neighbors[1] = Some((row_idx, col_idx - 1));
                }
                if row_idx < last_row && hill.can_reach(&hills[row_idx + 1][col_idx]) {
                    neighbors[2] = Some((row_idx + 1, col_idx));
                }
                if col_idx < last_col && hill.can_reach(&hills[row_idx][col_idx + 1]) {
                    neighbors[3] = Some((row_idx, col_idx + 1));
                }

                // When we encounter the start and end hills, we mark those as special.
                if let Hill::Start(_) = hill {
                    start_at = (row_idx, col_idx);
                }
                if let Hill::End(_) = hill {
                    end_at = (row_idx, col_idx);
                }
                graph.insert((row_idx, col_idx), neighbors);
            }
        }

        // All done!
        HillMap {
            hills,
            graph,
            start_at,
            end_at,
        }
    }
}

const INPUT: &str = include_str!("../../input/12/input.txt");

/// Parse that input!
fn read() -> HillMap {
    HillMap::from(INPUT)
}

```

It still ends up being a good bit of code, but it’s really just re-organizing the grid we get from the input. I like to pre-compute the neighbors when I’m prepping a graph because, inevitably, you end up checking neighbors for at least _some_ of the nodes multiple times. No sense making that harder than it has to be.

## Part One - Two Roads Diverged

Ah-ha! We’ve found it! And, by _it_, I mean the first Advent of Code puzzle that requires a graph traversal algorithm! I can’t poke holes in today’s logic, though, getting to high ground when you’re lost is right sensible. Why, I reckon that tomorrow we’ll be sending up smoke signals or engaging in some other reasonable survival activity and definitely not playing tiddlywinks with a capybara or something. There are a few different graph traversal algorithms we _could_employ here, but Dijkstra’s is my favorite, so we’re going to do that.

```rust
use core::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap};

/// Solve Day 12, Part 1
fn solve(input: &HillMap) -> u32 {
    // Starting at the start hill, count the number of steps to the end hill
    // with an implementation of Dijkstra's algorithm.
    let start_at = input.start_at;
    input.shortest_path_to_summit(start_at).unwrap()
}

impl HillMap {
    /// Dijkstra's Algorithm!!!
    fn shortest_path_to_summit(&self, start_at: (usize, usize)) -> Option<u32> {
        // The 'open set': the hills we know how to travel to, but don't
        // know how to travel _from_ yet. You can think of this like the expanding
        // outer edge of our search space, if that helps. Because it's a binary
        // heap (we're using as a _min_ binary heap), the next hill to be fetched
        // will always be the one with the shortest travel time found so far.
        let mut open = BinaryHeap::from([(Reverse(0), start_at)]);

        // Maintain a listing of the shortest number of steps to each hill we've
        // traveled to. It's the shortest number of steps _so far_, it's possible
        // to update these if a shorter path is found.
        let mut steps = HashMap::from([(start_at, 0)]);

        // So long as there are hills left to climb...
        while let Some((_, pos)) = open.pop() {
            // Check the hill we're currently on. If it's the end, then just return
            // the number of steps it took us to get here.
            let (row, col) = pos;
            if pos == self.end_at {
                return steps.get(&pos).copied();
            }

            // Otherwise, see if this hill has any neighbors we can reach. If not,
            // skip it and move on to the next hill in our 'open set'.
            let Some(neighbors) = self.graph.get(&pos) else { continue; };

            // For each direction where there might be a neighbor...
            for maybe_neighbor in neighbors {
                // If there's no reachable neighbor, try the next direction.
                let Some(neighbor) = maybe_neighbor else { continue; };

                // Otherwise, calculate how many steps it will take to get to that
                // neighbor from the path you're currently on. That is, one more step
                // than it took to get to the current hill.
                let next_steps: u32 = steps.get(&pos).unwrap() + 1;

                // Check how many steps are in the current shortest path to that neighbor
                let curr_steps: u32 = *steps.get(neighbor).unwrap_or(&u32::MAX);

                // If we've already found a shorter way to get there, we can just
                // move on.
                if next_steps >= curr_steps {
                    continue;
                }

                // If we're on the shortest path, then add the neighbor to the open
                // set and record the number of steps
                open.push((Reverse(next_steps), *neighbor));
                steps.insert(*neighbor, next_steps);
            }
        }

        None
    }
}

```

There’s more comment than code to that, but if this is your first time seeing a Dijkstra’s Algorithm implemented in the wild, it can be a bit intimidating. If you’re more of a visual learner, there’s a good [Computerphile video](https://www.youtube.com/watch?v=GazC3A4OQTE) on the topic.

## Part Two - I Like to Hike

Ah, see, here we go, being sensible again. Clearly, picking out the best spot to start a hiking trail _in the middle of the jungle_ is a much better use of our time that getting un-lost or finding food. Seems we bumped our heads in the fall earlier. That or we still haven’t recovered from the stress of chasing down those monkeys. Wait, did we ever actually get our stuff back? I can’t remember…

```rust
use core::cmp::Reverse;
use std::cmp::min;
use std::collections::{BinaryHeap, HashMap};

/// Solve Day 12, Part 2
fn solve(input: &HillMap) -> u32 {
    // Turns out we need to 'invert' our `HillMap` in order to efficiently find the
    // shortest path to _any_ hill with a height of 0.
    let descent_map = DescentMap::from(input);

    // Get the number of steps from the summit to _every_ single hill in
    // the jungle!
    let steps_to_short_hills = descent_map.shortest_paths_from_summit();

    // Check each hill to see if it's a short hill, and if it is, check to see if
    // it's the shortest path to a short hill found so far. If so, record it!
    let mut shortest_path = u32::MAX;
    for (pos, steps_to_pos) in steps_to_short_hills.iter() {
        let (row, col) = *pos;
        let Hill::Hill(0) = descent_map.hills[row][col] else { continue; };
        shortest_path = min(shortest_path, *steps_to_pos);
    }

    // Return the shortest path to a short hill
    shortest_path
}

// Type alias we'll use here to refer to the hills that can reach the current hill
type Neighbors = [Option<(usize, usize)>; 4];

// Very much like the `HillMap`. The biggest difference is that now `graph` represents
// relationships between hills that can be moved _to_ and the hills that can reach
// them (the reverse of the relationship for `HillMap`).
struct DescentMap {
    hills: Vec<Vec<Hill>>,
    graph: HashMap<(usize, usize), Neighbors>,
    summit: (usize, usize),
}

// Produce a `DescentMap` from a reference to a `HillMap`.
impl From<&HillMap> for DescentMap {
    fn from(hill_map: &HillMap) -> Self {
        // We need to invert the graph, so that we can essentially walk backwards
        // starting from the summit (our previous end point) down to all those
        // short hills.
        let mut graph: HashMap<(usize, usize), Neighbors> = HashMap::new();

        // For each entry in the `HillMap`s graph...
        for (pos, neighbors) in hill_map.graph.iter() {
            // For each neighbor in the entry's list of neighbors (skipping the empty
            // spaces in the neighbor array)
            for neighbor in neighbors.iter().flatten() {
                // Yeah, this is a bit of a gnarly iterator chain. Here's what's going
                // on: We're checking the entry in our inverted `graph` where the
                // neighbor is the key, creating an entry with an empty set of
                // neighbors if the neighbor doesn't have an entry yet. Then, for each
                // slot in the value array for `neighbor`, find the first index that
                // doesn't have a value yet and put `pos` there. This 'inverts' the
                // relationships by making `neighbor` the key and adding `pos` as one
                // of the positions from which `neighbor` can be reached.
                graph
                    .entry(*neighbor)
                    .or_default()
                    .iter_mut()
                    .filter(|slot| slot.is_none())
                    .take(1)
                    .for_each(|slot| *slot = Some(*pos));
            }
        }

        // Copy the `hills` and `end_at` fields from the `HillMap`
        let hills = hill_map.hills.to_vec();
        let summit = hill_map.end_at;

        // Return the new `DescentMap` with the inverted graph.
        DescentMap {
            hills,
            graph,
            summit,
        }
    }
}

impl DescentMap {
    /// Identify and return the minimum number of steps every other hill is from
    /// the summit as a HashMap where the keys are hill positions and the values
    /// are the number of steps from the summit.
    fn shortest_paths_from_summit(&self) -> HashMap<(usize, usize), u32> {
        // The procedure here is the same Dijkstra's algorithm from part one, just
        // walking down from the summit instead of up from the start space.
        let start_at = self.summit;
        let mut open = BinaryHeap::from([(Reverse(0), start_at)]);
        let mut steps = HashMap::from([(start_at, 0)]);

        // While there are still hills to explore...
        while let Some((_, pos)) = open.pop() {
            // No need for an early return here, we want to find a path to _all_ the
            // other hills.

            // As before, we check all the neighbors and any time we're able to
            // reach that neighbor by the shortest path found so far, we add that
            // neighbor to the open set.
            let Some(neighbors) = self.graph.get(&pos) else { continue; };
            for maybe_neighbor in neighbors {
                let Some(neighbor) = maybe_neighbor else { continue; };
                let next_steps: u32 = steps.get(&pos).unwrap() + 1;
                let curr_steps: u32 = *steps.get(neighbor).unwrap_or(&u32::MAX);
                if next_steps >= curr_steps {
                    continue;
                }
                open.push((Reverse(next_steps), *neighbor));
                steps.insert(*neighbor, next_steps);
            }
        }

        // Returns a mapping of the fewest steps to every hill from the summit
        steps
    }
}

```

Well, at least all we needed to do was flip our map inside-out to find the perfect hiking trail. Makes sense. You _could_ always just use the same code from part one and just check the distance starting with every hill represented by ‘a’. I _definitely_ don’t know from experience that that approach runs about 100x slower than the “map-inverting” method shown here, though. Nope, definitely didn’t do that first and run those benchmarks…

## Wrap Up

Yay! I really do enjoy the graph algorithm days. I can’t wait for the first puzzle to require an A\* algorithm this year. I don’t know that I did anything particularly clever today, but I had fun doing it. We’re almost half-way through Advent of Code by now, so it’s probably an appropriate time to stop and opine about just how great of an experience doing these puzzles every year is. For me, Advent of Code has become more than a set of exercises, it’s become a yearly opportunity to engage with an entire world-wide community around a common activity. I get to share tips, learn from others, gripe about common pitfalls, and celebrate successes with folks I already know and new faces alike. For this, I am extremely grateful. If you’re following along and enjoying Advent of Code too, I’d encourage you to consider [supporting](https://adventofcode.com/2022/support) Eric Wastl and the Advent of Code project if you’re able. I won’t get anything out of it other than a better chance to do this again next year, which is plenty. Even if you can’t support the project financially, consider supporting this event by participating and encouraging others to participate with you. I thank _you_for reading along with me this year, and I hope you’ll stick with me until the 25th.