Advent of Code 2021 - Day 9: Smoke Basin

smoke_basin.rs

struct Map {
    points: Vec<Vec<u32>>,
    width: usize,
    height: usize,
}

impl Map {
    fn parse(input: &str) -> Self {
        let width = input.lines().next().unwrap().len();
        let height = input.lines().count();

        let mut points = Vec::with_capacity(height);

        points.push(vec![u32::MAX; width + 2]);

        points.append(
            &mut input
                .lines()
                .map(|l| {
                    once(u32::MAX)
                        .chain(l.chars().map(|c| c.to_digit(10).unwrap()))
                        .chain(once(u32::MAX))
                        .collect()
                })
                .collect(),
        );

        points.push(vec![u32::MAX; width + 2]);

        Self {
            points,
            width,
            height,
        }
    }

    fn low_points(&self) -> u32 {
        let mut total = 0;

        for row in 1..self.height + 1 {
            for col in 1..self.width + 1 {
                let point = self.points[row][col];
                if point < self.points[row - 1][col]
                    && point < self.points[row][col - 1]
                    && point < self.points[row][col + 1]
                    && point < self.points[row + 1][col]
                {
                    total += point + 1;
                }
            }
        }

        total
    }

    fn basins(&self) -> u32 {
        let mut mapped = HashSet::new();
        let mut basins = Vec::new();

        for row in 1..self.height + 1 {
            for col in 1..self.width + 1 {
                if self.points[row][col] < 9 && !mapped.contains(&(row, col)) {
                    basins.push(self.explore_basin(&mut mapped, row, col));
                }
            }
        }

        basins.sort_unstable();
        basins.reverse();

        basins[0] * basins[1] * basins[2]
    }

    fn explore_basin(&self, mapped: &mut HashSet<(usize, usize)>, row: usize, col: usize) -> u32 {
        if self.points[row][col] >= 9 || mapped.contains(&(row, col)) {
            0
        } else {
            mapped.insert((row, col));

            1 + self.explore_basin(mapped, row - 1, col)
                + self.explore_basin(mapped, row, col - 1)
                + self.explore_basin(mapped, row, col + 1)
                + self.explore_basin(mapped, row + 1, col)
        }
    }
}