Advent of Code 2024: Day 10

Code for solutions available on GitHub.

Hoof It

Another grid day! This time the grid looks like this:

0123
1234
8765
9876

Each tile in the grid represents a height. We want to find paths that start at 0 and end at 9, but which only increment by 1 each step. Also, no diagonals.

Once again, I bust out the old Point struct. I also create a newtype around Vec<Vec<u8>> that I call Grid. I really should make a library shared across all days for common things like this, but oh well.

For Point, is once again implement in_bounds from day 08, along with a little helper method called neighbors:

impl Point {
    fn neighbors(&self) -> Vec<Point> {
        let mut neighbors = Vec::new();
        if self.x > 0 {
            neighbors.push(Point {
                x: self.x - 1,
                y: self.y,
            });
        }
        neighbors.push(Point {
            x: self.x + 1,
            y: self.y,
        });
        if self.y > 0 {
            neighbors.push(Point {
                x: self.x,
                y: self.y - 1,
            });
        }
        neighbors.push(Point {
            x: self.x,
            y: self.y + 1,
        });
        neighbors
    }
}

Does exactly what it says on the box. Returns a Vec<Point> of all neighboring points in the orthogonal directions. I also implement Index<Point> for Grid. This simply lets me index into the grid like this:

let point = Point { x: 12, y: 34 };
let grid = //...

// Get the element at row 34, column 12
grid[point]

We want to score each 0 by how many 9s it’s possible to reach from it by only stepping orthogonally, and only in increments of 1. This is solved pretty easily by a depth-first search. But we can’t just search the neighbors directly. We also have to filter them by their value relative a starting point:

fn get_next_higher(grid: &Grid, point: Point) -> Vec<Point> {
    let mut step_ups = Vec::new();
    for neighbor in point
        .neighbors()
        .into_iter()
        .filter(|n| n.in_bounds(grid.0[0].len(), grid.0.len()))
    {
        if grid[neighbor] == grid[point] + 1 {
            step_ups.push(neighbor);
        }
    }
    step_ups
}

Simple. Now when searching from a specific 0, we can keep track of how many unique 9s you can reach by storing them in a HashSet<Point>. Then at the end, just count the number of points in the hash set. Now we can score each 0 using depth-first search and recursion:

fn score_zero(grid: &Grid, zero: Point) -> usize {
    let mut reached_nines = HashSet::new();
    dfs(grid, &mut reached_nines, zero);
    reached_nines.len()
}

fn dfs(grid: &Grid, reached_nines: &mut HashSet<Point>, point: Point) {
    if grid[point] == 9 {
        reached_nines.insert(point);
        return;
    }

    let step_ups = get_next_higher(grid, point);
    for step_up in step_ups {
        dfs(grid, &mut reached_nines, step_up);
    }
}

By saving the positions of all zeroes during the parsing step, running score_zero on each of them, and summing their scores, we get the answer.

Part 2

Knowing how many 9s can be reached from each 0 is all well and good, but how many unique paths are there to any 9 for each 0? Well, part 1 was solved by depth-first search. This one can be solved by a simple breadth-first search. We essentially have a directed graph, and each 0 is a root node. Instead of returning the goal node when we reach a 9, we simply increment the number of paths to a 9 and keep searching. Implementing the pseudo-code from Wikipedia wholesale:

fn bfs(grid: &Grid, zero: Point) -> usize {
    let mut queue = VecDeque::new();
    queue.push_back(zero);
    let mut num_paths = 0;

    while let Some(point) = queue.pop_front() {
        if grid[point] == 9 {
            num_paths += 1;
            continue;
        }
        for neighbor in get_next_higher(grid, point) {
            queue.push_back(neighbor);
        }
    }

    num_paths
}

And applying this in the same way as depth-first was applied in part 1, we’re done :)