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
78
79
|
use crate::prelude::*;
fn dijkstra(map: &Grid<u8>) -> i64 {
let mut to_visit: priority_queue::PriorityQueue<_, _> = (0..map.rows().0)
.flat_map(|row| {
(0..map.cols().0).map(move |col| (Row(row), Col(col)))
})
.map(|pos| {
(
pos,
std::cmp::Reverse(if pos == (Row(0), Col(0)) {
0
} else {
i64::max_value()
}),
)
})
.collect();
while let Some(((row, col), std::cmp::Reverse(distance))) = to_visit.pop()
{
if row == Row(map.rows().0 - 1) && col == Col(map.cols().0 - 1) {
return distance;
}
for neighbor in map.adjacent(row, col, false) {
if to_visit.get(&neighbor).is_some() {
let new_distance =
distance + i64::from(map[neighbor.0][neighbor.1]);
if new_distance < to_visit.get_priority(&neighbor).unwrap().0
{
to_visit.change_priority(
&neighbor,
std::cmp::Reverse(new_distance),
);
}
}
}
}
unreachable!()
}
pub fn parse(fh: File) -> Result<Grid<u8>> {
Ok(parse::digit_grid(parse::lines(fh)))
}
pub fn part1(grid: Grid<u8>) -> Result<i64> {
Ok(dijkstra(&grid))
}
pub fn part2(grid: Grid<u8>) -> Result<i64> {
let mut large_grid = Grid::default();
large_grid.grow(Row(grid.rows().0 * 5), Col(grid.cols().0 * 5));
for lrow in 0..5 {
for lcol in 0..5 {
for ((Row(row), Col(col)), val) in grid.indexed_cells() {
let mut val = val + lrow + lcol;
while val > 9 {
val -= 9;
}
large_grid[Row(usize::from(lrow) * grid.rows().0 + row)]
[Col(usize::from(lcol) * grid.cols().0 + col)] = val;
}
}
}
Ok(dijkstra(&large_grid))
}
#[test]
fn test() {
assert_eq!(
part1(parse(parse::data(2021, 15).unwrap()).unwrap()).unwrap(),
441
);
assert_eq!(
part2(parse(parse::data(2021, 15).unwrap()).unwrap()).unwrap(),
2849
);
}
|
