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

year2024/
day10.rs
