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
|
use std::collections::{HashMap, VecDeque};
fn in_bounds(pos: (i32, i32), grid: &Vec<&[u8]>) -> bool {
let row = grid.len() as i32;
let col = grid[0].len() as i32;
pos.0 >= 0 && pos.0 < row && pos.1 >= 0 && pos.1 < col
}
fn is_valid(cur_char: u8, nxt_char: u8) -> bool {
let mut cur = cur_char as i32;
let mut nxt = nxt_char as i32;
if cur == ('S' as i32) {
cur = 'a' as i32;
}
if nxt == ('E' as i32) {
nxt = 'z' as i32;
}
nxt - cur <= 1
}
fn bfs(
grid: &Vec<&[u8]>,
target: u8,
start: (i32, i32),
path: &mut HashMap<(usize, usize), (usize, usize)>,
) -> (usize, usize) {
let mut queue: VecDeque<(i32, i32)> = VecDeque::new();
let row = grid.len();
let col = grid[0].len();
let dx: [i32; 4] = [1, 0, -1, 0];
let dy: [i32; 4] = [0, -1, 0, 1];
queue.push_front(start);
let mut vis: Vec<Vec<bool>> = vec![vec![false; col]; row];
while !queue.is_empty() {
let (x, y) = queue.pop_front().unwrap();
for i in 0..4 {
let nx = x + dx[i];
let ny = y + dy[i];
if in_bounds((nx, ny), &grid)
&& is_valid(grid[x as usize][y as usize], grid[nx as usize][ny as usize])
&& grid[nx as usize][ny as usize] == target
{
queue.clear();
path.insert((nx as usize, ny as usize), (x as usize, y as usize));
return (nx as usize, ny as usize);
}
if in_bounds((nx, ny), &grid)
&& is_valid(grid[x as usize][y as usize], grid[nx as usize][ny as usize])
&& !vis[nx as usize][ny as usize]
{
queue.push_back((nx, ny));
vis[nx as usize][ny as usize] = true;
path.insert((nx as usize, ny as usize), (x as usize, y as usize));
}
}
}
(0, 0)
}
fn get_starting_node(grid: &Vec<&[u8]>) -> (i32, i32) {
for i in 0..grid.len() {
for j in 0..grid[0].len() {
if grid[i][j] == 'S' as u8 {
return (i as i32, j as i32);
}
}
}
unreachable!()
}
fn get_nodes_with_elevation_a(grid: &Vec<&[u8]>) -> Vec<(i32, i32)> {
let mut ret = vec![];
for i in 0..grid.len() {
for j in 0..grid[0].len() {
if grid[i][j] == 'S' as u8 || grid[i][j] == 'a' as u8 {
ret.push((i as i32, j as i32));
}
}
}
ret
}
fn solve_part_one(data: &str) -> usize {
let grid: Vec<_> = data.lines().map(|s| s.as_bytes()).collect();
let start = get_starting_node(&grid);
// path that has the child as a key and the value as its parent
let mut path: HashMap<(usize, usize), (usize, usize)> = HashMap::new();
let mut cur_pos = bfs(&grid, 'E' as u8, start, &mut path);
let mut path_length = 0;
while *path.get(&cur_pos).unwrap() != (start.0 as usize, start.1 as usize) {
path_length += 1;
cur_pos = *path.get(&cur_pos).unwrap();
}
path_length + 1
}
fn solve_part_two(data: &str) -> usize {
let grid: Vec<_> = data.lines().map(|s| s.as_bytes()).collect();
let nodes_with_elevation_a = get_nodes_with_elevation_a(&grid);
let mut mn = usize::MAX;
for node in nodes_with_elevation_a {
// path that has the child as a key and the value as its parent
let mut path: HashMap<(usize, usize), (usize, usize)> = HashMap::new();
let mut cur_pos = bfs(&grid, 'E' as u8, node, &mut path);
let mut path_length = 0;
if path.get(&cur_pos).is_some() {
while *path.get(&cur_pos).unwrap() != (node.0 as usize, node.1 as usize) {
path_length += 1;
cur_pos = *path.get(&cur_pos).unwrap();
}
mn = std::cmp::min(mn, path_length + 1);
}
}
mn
}
fn main() {
let test = include_str!("../input/day12.test");
let prod = include_str!("../input/day12.prod");
println!("part1: test {:?}", solve_part_one(test));
println!("part1: prod {:?}", solve_part_one(prod));
println!("part2: test {:?}", solve_part_two(test));
println!("part2: prod {:?}", solve_part_two(prod));
}
|
