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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
mod utils;
use std::collections::BinaryHeap;
use utils::read_input;
fn main() {
let input = read_input();
let width = input.lines().next().unwrap().len();
let height = input.lines().count();
let mut heights = vec![0; width * height];
let mut start = (0, 0);
let mut end = (0, 0);
for (y, line) in input.lines().enumerate() {
for (x, c) in line.chars().enumerate() {
let val = if c == 'S' {
start = (x as isize, y as isize);
0
} else if c == 'E' {
end = (x as isize, y as isize);
25
} else {
c.to_ascii_lowercase() as isize - 97
};
heights[(y * width) + x] = val;
}
}
let cost = pathfind(&heights, width, end);
println!("Part 1: {:?}", cost[pos_to_index(&start, width)]);
println!(
"Part 2: {:?}",
(0..height as isize)
.map(|y| (0..width as isize)
.map(|x| pos_to_index(&(x, y), width))
.filter(|idx| heights[*idx] == 0)
.map(|idx| cost[idx])
.min()
.unwrap())
.min()
.unwrap()
)
}
type HeightMap = Vec<isize>;
type Pos = (isize, isize);
fn pathfind(heights: &HeightMap, width: usize, end: Pos) -> Vec<usize> {
let mut min_cost = vec![usize::MAX; heights.len()];
let mut frontier: BinaryHeap<GraphPos> = BinaryHeap::new();
frontier.push(GraphPos { pos: end, moves: 0 });
while let Some(curr) = frontier.pop() {
let idx = pos_to_index(&curr.pos, width);
if curr.moves >= min_cost[idx] {
continue;
} else {
min_cost[idx] = curr.moves;
}
for neighbour in CanReach::new(heights, width, curr.pos) {
frontier.push(GraphPos {
pos: neighbour,
moves: curr.moves + 1,
})
}
}
min_cost
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct GraphPos {
pos: Pos,
moves: usize,
}
impl PartialOrd for GraphPos {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
self.moves.partial_cmp(&other.moves).map(|x| x.reverse())
}
}
impl Ord for GraphPos {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.moves.cmp(&other.moves).reverse()
}
}
struct CanReach<'a> {
heights: &'a HeightMap,
curr: Pos,
step: usize,
width: usize,
}
impl<'a> CanReach<'a> {
fn new(heights: &'a HeightMap, width: usize, pos: Pos) -> Self {
CanReach {
heights,
curr: pos,
step: 0,
width,
}
}
}
impl Iterator for CanReach<'_> {
type Item = Pos;
fn next(&mut self) -> Option<Self::Item> {
let (curr_x, curr_y) = self.curr;
loop {
let (x, y) = match self.step {
0 => (curr_x + 1, curr_y),
1 => (curr_x - 1, curr_y),
2 => (curr_x, curr_y + 1),
3 => (curr_x, curr_y - 1),
_ => break,
};
self.step += 1;
if (x >= 0
&& x < self.width as isize
&& y >= 0
&& y < (self.heights.len() / self.width) as isize)
&& self.heights[pos_to_index(&(x, y), self.width)]
>= self.heights[pos_to_index(&(curr_x, curr_y), self.width)] - 1
{
return Some((x, y));
}
}
None
}
}
#[inline(always)]
fn pos_to_index(pos: &Pos, width: usize) -> usize {
((pos.1 * width as isize) + pos.0) as usize
}
|
