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
|
use std::collections::HashMap;
static DAY: u8 = 12;
fn main() {
let input = advent::read_lines(DAY);
println!("{DAY}a: {}", steps_required_start(&input));
println!("{DAY}b: {}", steps_required_any_a(&input));
}
#[derive(PartialEq,Eq,Hash,Clone,Copy)]
struct Position {
x: isize,
y: isize,
}
fn parse_map(input: &[String]) -> (HashMap<Position,u32>, Position, Position) {
let mut map = HashMap::new();
let mut start = Position { x: 0, y: 0};
let mut end = Position { x: 0, y: 0};
for (y, line) in input.iter().enumerate() {
for (x, c) in line.chars().enumerate() {
let pos = Position { x: x as isize, y: y as isize };
let elevation = match c {
'S' => { start = pos; 'a' }
'E' => { end = pos; 'z' }
e => e,
};
let elevation = elevation.to_digit(36).unwrap();
map.insert(pos, elevation);
}
}
(map, start, end)
}
fn steps_required(map: &HashMap<Position,u32>, end: &Position, found_position: impl Fn(&Position, u32) -> bool) -> u32 {
let mut distances = HashMap::new();
distances.insert(*end, 0);
loop {
let positions = distances.keys().cloned().collect::<Vec<_>>();
for pos in positions {
let next_dist = distances[&pos] + 1;
let neighbors = [
Position { x: pos.x + 1, y: pos.y },
Position { x: pos.x, y: pos.y + 1 },
Position { x: pos.x - 1, y: pos.y },
Position { x: pos.x, y: pos.y - 1 },
];
for neighbor in neighbors {
if distances.contains_key(&neighbor) || !map.contains_key(&neighbor){
continue;
}
if map[&pos] <= map[&neighbor] || map[&pos] == map[&neighbor] + 1 {
distances.insert(neighbor, next_dist);
if found_position(&neighbor, map[&neighbor]) {
return next_dist;
}
}
}
}
}
}
fn steps_required_start(input: &[String]) -> u32 {
let (map, start, end) = parse_map(input);
let found_position = |pos: &Position, _ele: u32| -> bool {
/* looking for the starting position */
*pos == start
};
steps_required(&map, &end, found_position)
}
fn steps_required_any_a(input: &[String]) -> u32 {
let (map, _, end) = parse_map(input);
let found_position = |_pos: &Position, ele: u32| -> bool {
/* looking for any location with elevation 'a' */
ele == 'a'.to_digit(36).unwrap()
};
steps_required(&map, &end, found_position)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test() {
let input = [
"Sabqponm",
"abcryxxl",
"accszExk",
"acctuvwj",
"abdefghi",
].iter().map(|&x| String::from(x)).collect::<Vec<_>>();
assert_eq!(steps_required_start(&input), 31);
assert_eq!(steps_required_any_a(&input), 29);
}
}
|
