Advent of Code 2021 - Day 15: Chiton

chiton.rs

#[derive(Copy, Clone)]
struct Point {
    x: usize,
    y: usize,
}

impl Point {
    fn new(x: usize, y: usize) -> Self {
        Self { x, y }
    }
}

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

impl From<&str> for Map {
    fn from(value: &str) -> Self {
        let risks = value
            .lines()
            .map(|l| l.chars().map(|c| c.to_digit(10).unwrap()).collect())
            .collect::<Vec<Vec<_>>>();

        let width = risks[0].len();
        let height = risks.len();

        Self {
            risks,
            width,
            height,
        }
    }
}

impl Map {
    fn scale(&mut self, scale: usize) {
        let width = self.width * scale;
        let height = self.height * scale;

        let mut risks: Vec<Vec<u32>> = vec![vec![0; width]; height];

        risks.iter_mut().enumerate().for_each(|(y, row)| {
            row.iter_mut().enumerate().for_each(|(x, value)| {
                let risk = self.risks[y % self.height][x % self.width] + (y / self.height + x / self.width) as u32;
                *value = (risk - 1) % 9 + 1;
            })
        });

        self.width = width;
        self.height = height;
        self.risks = risks;
    }

    fn neighbours(&self, point: Point) -> Vec<Point> {
        let mut neighbours = Vec::new();

        if point.x < self.width - 1 {
            neighbours.push(Point::new(point.x + 1, point.y));
        }

        if point.y < self.height - 1 {
            neighbours.push(Point::new(point.x, point.y + 1));
        }

        if point.x > 0 {
            neighbours.push(Point::new(point.x - 1, point.y));
        }

        if point.y > 0 {
            neighbours.push(Point::new(point.x, point.y - 1))
        }

        neighbours
    }

    fn navigate(&self) -> u32 {
        let mut risk_totals = vec![vec![u32::MAX; self.width]; self.height];
        let mut queue = VecDeque::new();

        risk_totals[0][0] = 0;
        queue.push_back(Point::new(0, 0));

        while let Some(current) = queue.pop_front() {
            for neighbour in self.neighbours(current) {
                if risk_totals[neighbour.y][neighbour.x]
                    <= risk_totals[current.y][current.x] + self.risks[neighbour.y][neighbour.x]
                {
                    continue;
                }

                risk_totals[neighbour.y][neighbour.x] =
                    risk_totals[current.y][current.x] + self.risks[neighbour.y][neighbour.x];

                queue.push_back(neighbour);
            }
        }

        risk_totals[self.width - 1][self.height - 1]
    }
}