Day12 done in rust

1 files changed, 126 insertions, 0 deletions

diff --git a/2022/Rust/src/day12.rs b/2022/Rust/src/day12.rs
new file mode 100644
index 0000000..26dc7ac
--- /dev/null
+++ b/2022/Rust/src/day12.rs
@@ -0,0 +1,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));
+}