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    // A newline border allows us to avoid boundary checks.
11    Grid::parse_with_border(input)
12}
13
14pub fn part1(grid: &Grid<u8>) -> u32 {
15    solve(grid, false)
16}
17
18pub fn part2(grid: &Grid<u8>) -> u32 {
19    solve(grid, true)
20}
21
22fn solve(grid: &Grid<u8>, distinct: bool) -> u32 {
23    let mut result = 0;
24    let mut seen = grid.same_size_with(-1);
25
26    // Iterate over every point, skipping the border.
27    for y in 1..grid.height - 1 {
28        for x in 1..grid.width {
29            let point = Point::new(x, y);
30            if grid[point] == b'9' {
31                let id = y * grid.width + x;
32                result += dfs(grid, distinct, &mut seen, id, point);
33            }
34        }
35    }
36
37    result
38}
39
40fn dfs(grid: &Grid<u8>, distinct: bool, seen: &mut Grid<i32>, id: i32, point: Point) -> u32 {
41    let mut result = 0;
42
43    for next in ORTHOGONAL.map(|o| point + o) {
44        if grid[next] + 1 == grid[point] && (distinct || seen[next] != id) {
45            seen[next] = id;
46
47            if grid[next] == b'0' {
48                result += 1;
49            } else {
50                result += dfs(grid, distinct, seen, id, next);
51            }
52        }
53    }
54
55    result
56}
aoc/year2024/day10.rs

aoc/year2024/
day10.rs
