aoc/year2024/
day10.rs

1//! # Hoof It
2//!
3//! [Depth first search](https://en.wikipedia.org/wiki/Depth-first_search) for both parts.
4//! Part two is simpler than part one as we don't need to keep track of already visited points.
5//! Reverse search was slightly faster as my input contained fewer peaks `9` than valleys `0`.
6use crate::util::grid::*;
7use crate::util::point::*;
8
9pub fn parse(input: &str) -> Grid<u8> {
10    Grid::parse(input)
11}
12
13pub fn part1(grid: &Grid<u8>) -> u32 {
14    solve(grid, false)
15}
16
17pub fn part2(grid: &Grid<u8>) -> u32 {
18    solve(grid, true)
19}
20
21fn solve(grid: &Grid<u8>, distinct: bool) -> u32 {
22    let mut result = 0;
23    let mut seen = grid.same_size_with(-1);
24
25    for y in 0..grid.height {
26        for x in 0..grid.width {
27            let point = Point::new(x, y);
28            if grid[point] == b'9' {
29                let id = y * grid.width + x;
30                result += dfs(grid, distinct, &mut seen, id, point);
31            }
32        }
33    }
34
35    result
36}
37
38fn dfs(grid: &Grid<u8>, distinct: bool, seen: &mut Grid<i32>, id: i32, point: Point) -> u32 {
39    let mut result = 0;
40
41    for next in ORTHOGONAL.map(|o| point + o) {
42        if grid.contains(next) && grid[next] + 1 == grid[point] && (distinct || seen[next] != id) {
43            seen[next] = id;
44
45            if grid[next] == b'0' {
46                result += 1;
47            } else {
48                result += dfs(grid, distinct, seen, id, next);
49            }
50        }
51    }
52
53    result
54}
aoc/year2024/day10.rs

aoc/year2024/
day10.rs
