pathfinding 4.15.0

Pathfinding, flow, and graph algorithms
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

use pathfinding::{directed::dijkstra::dijkstra, matrix::Matrix};

static TEST_INPUT: &str = "
2413432311323
3215453535623
3255245654254
3446585845452
4546657867536
1438598798454
4457876987766
3637877979653
4654967986887
4564679986453
1224686865563
2546548887735
4322674655533
";

static TEST_INPUT_2: &str = "
111111111111
999999999991
999999999991
999999999991
999999999991
";

fn part1(input: &str) -> u32 {
    part(input, 1, 3)
}

fn part2(input: &str) -> u32 {
    part(input, 4, 10)
}

fn part(input: &str, min_move: usize, max_move: usize) -> u32 {
    let grid = Matrix::from_rows(
        input
            .trim()
            .lines()
            .map(|l| l.chars().filter_map(|c| c.to_digit(10))),
    )
    .unwrap();
    dijkstra(
        &((0, 0), (0, 0), 0),
        |&(pos, (dr, dc), l)| {
            let mut next = Vec::with_capacity(3);
            let mut e = |dir, l| {
                next.extend(
                    &grid
                        .move_in_direction(pos, dir)
                        .map(|t| ((t, dir, l), grid[t])),
                );
            };
            if l < max_move {
                e((dr, dc), l + 1);
            }
            if l >= min_move {
                e((-dc, -dr), 1);
                e((dc, dr), 1);
            } else if l == 0 {
                e((1, 0), 1);
                e((0, 1), 1);
            }
            next
        },
        |&(pos, _, l)| pos == (grid.rows - 1, grid.columns - 1) && l >= min_move,
    )
    .unwrap()
    .1
}

#[test]
fn aoc_2023_17() {
    assert_eq!(102, part1(TEST_INPUT));
    assert_eq!(94, part2(TEST_INPUT));
    assert_eq!(71, part2(TEST_INPUT_2));
}