Advent of Code 2024 Day 10

Parsing

The input is in the form of a grid of numbers, with each position in the grid being a number between 0 and 9. I parse this by first iterating over lines and then over the characters in each line, using the enumerate method on iterators to get the row and column indices. I create a Point struct to represent the coordinates on our grid. I represent the grid with a hashmap, with points as the keys and the numbers as the values.

fn parse_input(input: String) -> HashMap<Point, u8> {
    input
        .trim()
        .lines()
        .enumerate()
        .flat_map(|(row, line)| {
            line.chars().enumerate().map(move |(col, ch)| {
                (
                    (Point::new(row as i32, col as i32)),
                    ch.to_digit(10).unwrap() as u8,
                )
            })
        })
        .collect()
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Point {
    row: i32,
    col: i32,
}

impl Point {
    fn new(row: i32, col: i32) -> Self {
        Point { row: row, col: col }
    }
}

Part One

Our input represents a topographical map with each digit on the grid being a height from 0 to 9. We need to find the sum of the scores of each trailhead that exists on our map. A trailhead is simply a 0 on the grid and its score is the number of 9 positions that can be reached from it. While calculating the path from a 0 to a 9, we must also ensure that the difference between the next height and the current height is always 1.

I start by iterating over all the 0s in the grid and finding the score of each one. To find the score of a trailhead, I maintain a queue of current points which initially contains just the start point. This queue represents the points that we need to visit next. I also keep track of the points that I have already visited so that I don’t visit them again. Then, for each element that I visit (by removing it from the front of the queue), I add all of its unvisited neighbors that are valid to the back of the queue. This loop stops when I visit all the places we can go to from our trailhead and our queue becomes empty. When a neighbor of the current point has value 9, I increment the score and mark it as visited so that we don’t visit it again.

This algorithm of having a expanding queue of current points is called a breadth-first search. For a better and more in-depth explanation of BFS, I recommend reading this excellent article on the topic.

fn part1(input: &HashMap<Point, u8>) -> usize {
    input
        .iter()
        .filter(|&(_, &n)| n == 0)
        .map(|(&point, _)| find_score(point, &input))
        .sum()
}

fn find_score(point: Point, grid: &HashMap<Point, u8>) -> usize {
    let mut score = 0;
    let mut seen = HashSet::new();
    let mut current_points = VecDeque::new();
    current_points.push_back(point);
    while !current_points.is_empty() {
        let current = current_points.pop_front().unwrap();
        seen.insert(current);
        for neighbor in current.neighbors() {
            if !seen.contains(&neighbor) {
                match grid.get(&neighbor) {
                    Some(&n) if n.checked_sub(grid[&current]) == Some(1) => {
                        if n == 9 {
                            score += 1;
                            seen.insert(neighbor);
                        } else {
                            current_points.push_back(neighbor);
                        }
                    }
                    _ => {}
                }
            }
        }
    }

    score
}

impl Point {
    fn neighbors(self) -> impl Iterator<Item = Self> {
        let neighbors = vec![
            Point::new(1, 0),
            Point::new(0, 1),
            Point::new(-1, 0),
            Point::new(0, -1),
        ];

        neighbors.into_iter().map(move |diff| self + diff)
    }
}

impl Add for Point {
    type Output = Self;
    fn add(self, other: Point) -> Point {
        Point {
            row: self.row + other.row,
            col: self.col + other.col,
        }
    }
}

Part Two

Now, we need to find the rating of each trailhead instead of its score. The rating of a trailhead is the number of valid paths that reach a 9.

The solution for this is very similar to the part 1 solution with only a single line changing in our breadth-first search. Now, when I find a 9, I don’t mark it as visited to let the different paths to the same 9 be found. Interestingly, my initial solution to part 1 mistakenly did this, making part 2 extremely trivial for me.

fn part2(input: &HashMap<Point, u8>) -> usize {
    input
        .iter()
        .filter(|&(_, &n)| n == 0)
        .map(|(&point, _)| find_rating(point, &input))
        .sum()
}

fn find_rating(point: Point, grid: &HashMap<Point, u8>) -> usize {
    let mut rating = 0;
    let mut seen = HashSet::new();
    let mut current_points = VecDeque::new();
    current_points.push_back(point);
    while !current_points.is_empty() {
        let current = current_points.pop_front().unwrap();
        seen.insert(current);
        for neighbor in current.neighbors() {
            if !seen.contains(&neighbor) {
                match grid.get(&neighbor) {
                    Some(&n) if n.checked_sub(grid[&current]) == Some(1) => {
                        if n == 9 {
                            rating += 1;
                        } else {
                            current_points.push_back(neighbor);
                        }
                    }
                    _ => {}
                }
            }
        }
    }

    rating
}