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
|
fn accessible_adjescent_cells(to: (usize,usize), grid: &Vec<Vec<char>>) -> Vec<(usize,usize)>{
let height = grid.len();
let width = grid[0].len();
let mut adjescent: Vec<(usize,usize)> = vec![];
if to.0 > 0 {
adjescent.push((to.0-1,to.1));
}
if to.0 < (height-1) {
adjescent.push((to.0+1, to.1));
}
if to.1 > 0 {
adjescent.push((to.0,to.1-1));
}
if to.1 < (width-1) {
adjescent.push((to.0,to.1+1));
}
adjescent.into_iter().filter(|from| {
let ch_to = grid[to.0][to.1] as u32;
let ch_from = grid[from.0][from.1] as u32;
ch_to <= ch_from + 1
}).collect()
}
pub fn run(input: String) {
let mut grid: Vec<Vec<char>> = input.lines().map(|line| {line.chars().collect()}).collect();
let mut maybe_start: Option<(usize,usize)> = None;
let mut maybe_end: Option<(usize,usize)> = None;
let height = grid.len();
let width = grid[0].len();
for i in 0..height {
for j in 0..width {
let ch = grid[i][j];
if ch == 'S' {
maybe_start = Some((i,j));
} else if ch == 'E' {
maybe_end = Some((i,j));
}
}
}
let start = maybe_start.expect("couldn't find start!");
let end = maybe_end.expect("couldn't find end!");
// Update the grid with heights for start and end
grid[start.0][start.1] = 'a';
grid[end.0][end.1] = 'z';
// Deliberately doing this from end to start, 'cos that's what part 2 will re-use most of.
let mut scores: Vec<Vec<i32>> = (0..height).map(|_| {[-1].repeat(width)}).collect();
scores[end.0][end.1] = 0;
// 'foo: while scores[start.0][start.1] == -1 {
'foo: loop {
let mut blocked = true;
// Iterate out a round
for i in 0..height {
for j in 0..width {
let cell_score = scores[i][j];
// For every currently visited cell
if cell_score != -1 {
// Check if surrounding cells are accessible
let ac = accessible_adjescent_cells((i,j), &grid);
for c in ac {
// If they weren't reached yet, mark them with the new score
if scores[c.0][c.1] == -1 {
blocked = false;
scores[c.0][c.1] = cell_score + 1;
}
// Short circuit while looking for a specific square
// if (c.0,c.1) == start {
// println!("breaking early, found the start");
// break 'foo; // No point continuing calculations if we got to the start already!
// }
}
}
}
}
// If we went a whole round without finding any more accessible cells then we've covered the whole map already
if blocked {
// println!("we're done here");
break 'foo;
}
}
// Debugging...
// for i in 0..height {
// for j in 0..width {
// print!("{}", grid[i][j]);
// print!("{:04} ", scores[i][j]);
// }
// print!("\n");
// }
// let minpath = scores[start.0][start.1];
// println!("Day 12: {}", minpath);
let mut min_path_to_a:i32 = i32::MAX;
for i in 0..height {
for j in 0..width {
if grid[i][j] == 'a' && scores[i][j] != -1 { // consider only accessible ones, perhaps I shouldn't have used -1 to indicate inaccessible.
min_path_to_a = min_path_to_a.min(scores[i][j]);
}
}
}
println!("Day 12: {}", min_path_to_a);
}
|
