year2024/
day10.rs

1use utils::grid;
2use utils::prelude::*;
3
4/// Counting increasing paths through a grid.
5#[derive(Clone, Debug)]
6pub struct Day10 {
7    rows: usize,
8    cols: usize,
9    grid: Vec<u32>,
10}
11
12impl Day10 {
13    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
14        let (rows, cols, grid) = grid::from_str(input, |b| match b {
15            b'0'..=b'9' => Some((b - b'0') as u32),
16            _ => None,
17        })?;
18
19        Ok(Self { rows, cols, grid })
20    }
21
22    #[must_use]
23    pub fn part1(&self) -> u32 {
24        let mut total = 0;
25        let mut visited = vec![usize::MAX; self.grid.len()];
26        for r in 0..self.rows {
27            for c in 0..self.cols {
28                if self.grid[r * self.cols + c] != 0 {
29                    continue;
30                }
31                total += self.trailhead_score(r, c, 1, &mut visited, r * self.cols + c);
32            }
33        }
34        total
35    }
36
37    fn trailhead_score(
38        &self,
39        r: usize,
40        c: usize,
41        next: u32,
42        visited: &mut [usize],
43        visited_key: usize,
44    ) -> u32 {
45        let index = r * self.cols + c;
46        visited[index] = visited_key;
47        if next == 10 {
48            return 1;
49        }
50
51        let mut total = 0;
52        if r > 0
53            && self.grid[index - self.cols] == next
54            && visited[index - self.cols] != visited_key
55        {
56            total += self.trailhead_score(r - 1, c, next + 1, visited, visited_key);
57        }
58        if r < self.rows - 1
59            && self.grid[index + self.cols] == next
60            && visited[index + self.cols] != visited_key
61        {
62            total += self.trailhead_score(r + 1, c, next + 1, visited, visited_key);
63        }
64        if c > 0 && self.grid[index - 1] == next && visited[index - 1] != visited_key {
65            total += self.trailhead_score(r, c - 1, next + 1, visited, visited_key);
66        }
67        if c < self.cols - 1 && self.grid[index + 1] == next && visited[index + 1] != visited_key {
68            total += self.trailhead_score(r, c + 1, next + 1, visited, visited_key);
69        }
70
71        total
72    }
73
74    pub fn part2(&self) -> u32 {
75        let mut total = 0;
76        let mut cache = vec![None; self.grid.len()];
77        for r in 0..self.rows {
78            for c in 0..self.cols {
79                if self.grid[r * self.cols + c] != 0 {
80                    continue;
81                }
82                total += self.count_trails(r, c, 1, &mut cache);
83            }
84        }
85        total
86    }
87
88    fn count_trails(&self, r: usize, c: usize, next: u32, cache: &mut [Option<u32>]) -> u32 {
89        let index = r * self.cols + c;
90        if let Some(cache) = cache[index] {
91            return cache;
92        }
93
94        if next == 10 {
95            cache[index] = Some(1);
96            return 1;
97        }
98
99        let mut total = 0;
100        if r > 0 && self.grid[index - self.cols] == next {
101            total += self.count_trails(r - 1, c, next + 1, cache);
102        }
103        if r < self.rows - 1 && self.grid[index + self.cols] == next {
104            total += self.count_trails(r + 1, c, next + 1, cache);
105        }
106        if c > 0 && self.grid[index - 1] == next {
107            total += self.count_trails(r, c - 1, next + 1, cache);
108        }
109        if c < self.cols - 1 && self.grid[index + 1] == next {
110            total += self.count_trails(r, c + 1, next + 1, cache);
111        }
112
113        cache[index] = Some(total);
114        total
115    }
116}
117
118examples!(Day10 -> (u32, u32) [
119    {file: "day10_example0.txt", part1: 36, part2: 81},
120]);
year2024/day10.rs

year2024/
day10.rs
