1use utils::grid;
2use utils::prelude::*;
3
4#[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 pub fn part2(&self) -> u32 {
79 let mut total = 0;
80 let mut cache = vec![None; self.grid.len()];
81 for r in 0..self.rows {
82 for c in 0..self.cols {
83 if self.grid[r * self.cols + c] != 0 {
84 continue;
85 }
86 total += self.count_trails(r, c, 1, &mut cache);
87 }
88 }
89 total
90 }
91
92 fn count_trails(&self, r: usize, c: usize, next: u8, cache: &mut [Option<u32>]) -> u32 {
93 let index = r * self.cols + c;
94 if let Some(cache) = cache[index] {
95 return cache;
96 }
97
98 if next == 10 {
99 cache[index] = Some(1);
100 return 1;
101 }
102
103 let mut total = 0;
104 if r > 0 && self.grid[index - self.cols] == next {
105 total += self.count_trails(r - 1, c, next + 1, cache);
106 }
107 if r < self.rows - 1 && self.grid[index + self.cols] == next {
108 total += self.count_trails(r + 1, c, next + 1, cache);
109 }
110 if c > 0 && self.grid[index - 1] == next {
111 total += self.count_trails(r, c - 1, next + 1, cache);
112 }
113 if c < self.cols - 1 && self.grid[index + 1] == next {
114 total += self.count_trails(r, c + 1, next + 1, cache);
115 }
116
117 cache[index] = Some(total);
118 total
119 }
120}
121
122examples!(Day10 -> (u32, u32) [
123 {file: "day10_example0.txt", part1: 36, part2: 81},
124]);