Day12 done in rust

5 files changed, 196 insertions, 381 deletions

diff --git a/2022/Rust/.vscode/launch.json b/2022/Rust/.vscode/launch.json
deleted file mode 100644
index 4b4567c..0000000
--- a/2022/Rust/.vscode/launch.json
+++ /dev/null
@@ -1,380 +0,0 @@
-{
-    // Use IntelliSense to learn about possible attributes.
-    // Hover to view descriptions of existing attributes.
-    // For more information, visit: https://go.microsoft.com/fwlink/?linkid=830387
-    "version": "0.2.0",
-    "configurations": [
-        
-
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug executable 'day1'",
-            "cargo": {
-                "args": [
-                    "build",
-                    "--bin=day1",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day1",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug unit tests in executable 'day1'",
-            "cargo": {
-                "args": [
-                    "test",
-                    "--no-run",
-                    "--bin=day1",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day1",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug executable 'day2'",
-            "cargo": {
-                "args": [
-                    "build",
-                    "--bin=day2",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day2",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug unit tests in executable 'day2'",
-            "cargo": {
-                "args": [
-                    "test",
-                    "--no-run",
-                    "--bin=day2",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day2",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug executable 'day3'",
-            "cargo": {
-                "args": [
-                    "build",
-                    "--bin=day3",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day3",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug unit tests in executable 'day3'",
-            "cargo": {
-                "args": [
-                    "test",
-                    "--no-run",
-                    "--bin=day3",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day3",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug executable 'day4'",
-            "cargo": {
-                "args": [
-                    "build",
-                    "--bin=day4",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day4",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug unit tests in executable 'day4'",
-            "cargo": {
-                "args": [
-                    "test",
-                    "--no-run",
-                    "--bin=day4",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day4",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug executable 'day5'",
-            "cargo": {
-                "args": [
-                    "build",
-                    "--bin=day5",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day5",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug unit tests in executable 'day5'",
-            "cargo": {
-                "args": [
-                    "test",
-                    "--no-run",
-                    "--bin=day5",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day5",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug executable 'day6'",
-            "cargo": {
-                "args": [
-                    "build",
-                    "--bin=day6",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day6",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug unit tests in executable 'day6'",
-            "cargo": {
-                "args": [
-                    "test",
-                    "--no-run",
-                    "--bin=day6",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day6",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug executable 'day7'",
-            "cargo": {
-                "args": [
-                    "build",
-                    "--bin=day7",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day7",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug unit tests in executable 'day7'",
-            "cargo": {
-                "args": [
-                    "test",
-                    "--no-run",
-                    "--bin=day7",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day7",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug executable 'day8'",
-            "cargo": {
-                "args": [
-                    "build",
-                    "--bin=day8",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day8",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug unit tests in executable 'day8'",
-            "cargo": {
-                "args": [
-                    "test",
-                    "--no-run",
-                    "--bin=day8",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day8",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug executable 'day9'",
-            "cargo": {
-                "args": [
-                    "build",
-                    "--bin=day9",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day9",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug unit tests in executable 'day9'",
-            "cargo": {
-                "args": [
-                    "test",
-                    "--no-run",
-                    "--bin=day9",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day9",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug executable 'day10'",
-            "cargo": {
-                "args": [
-                    "build",
-                    "--bin=day10",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day10",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        },
-        {
-            "type": "lldb",
-            "request": "launch",
-            "name": "Debug unit tests in executable 'day10'",
-            "cargo": {
-                "args": [
-                    "test",
-                    "--no-run",
-                    "--bin=day10",
-                    "--package=Rust"
-                ],
-                "filter": {
-                    "name": "day10",
-                    "kind": "bin"
-                }
-            },
-            "args": [],
-            "cwd": "${workspaceFolder}"
-        }
-    ]
-}
\ No newline at end of file
diff --git a/2022/Rust/Cargo.toml b/2022/Rust/Cargo.toml
index f1b5c75..58d611d 100755
--- a/2022/Rust/Cargo.toml
+++ b/2022/Rust/Cargo.toml
@@ -24,7 +24,6 @@ path = "src/day3.rs"
 name = "day4"
 path = "src/day4.rs"
 
-
 [[bin]]
 name = "day5"
 path = "src/day5.rs"
@@ -52,3 +51,27 @@ path = "src/day10.rs"
 [[bin]]
 name = "day11"
 path = "src/day11.rs"
+
+[[bin]]
+name = "day12"
+path = "src/day12.rs"
+
+[[bin]]
+name = "day13"
+path = "src/day13.rs"
+
+[[bin]]
+name = "day14"
+path = "src/day14.rs"
+
+[[bin]]
+name = "day15"
+path = "src/day15.rs"
+
+[[bin]]
+name = "day16"
+path = "src/day16.rs"
+
+[[bin]]
+name = "day17"
+path = "src/day17.rs"
diff --git a/2022/Rust/input/day12.prod b/2022/Rust/input/day12.prod
new file mode 100644
index 0000000..bac8753
--- /dev/null
+++ b/2022/Rust/input/day12.prod
@@ -0,0 +1,41 @@
+abccccccccccccccccccaaaaaaaaacccccccccccccccccccccccccccccccccccccaaaa
+abcccccccccccccccaaaaaaaaaaacccccccccccccccccccccccccccccccccccccaaaaa
+abcaaccaacccccccccaaaaaaaaaacccccccccccccccccccccaaacccccccccccccaaaaa
+abcaaaaaaccccccccaaaaaaaaaaaaacccccccccccccccccccaacccccccccccccaaaaaa
+abcaaaaaacccaaacccccaaaaaaaaaaaccccccccccccccccccaaaccccccccccccccccaa
+abaaaaaaacccaaaaccccaaaaaacaaaacccccccccccaaaacjjjacccccccccccccccccca
+abaaaaaaaaccaaaaccccaaaaaaccccccaccccccccccaajjjjjkkcccccccccccccccccc
+abaaaaaaaaccaaacccccccaaaccccccaaccccccccccajjjjjjkkkaaacccaaaccaccccc
+abccaaacccccccccccccccaaccccaaaaaaaacccccccjjjjoookkkkaacccaaaaaaccccc
+abcccaacccccccccccccccccccccaaaaaaaaccccccjjjjoooookkkkcccccaaaaaccccc
+abcccccccaacccccccccccccccccccaaaacccccccijjjoooooookkkkccaaaaaaaccccc
+abccaaccaaaccccccccccccccccccaaaaacccccciijjooouuuoppkkkkkaaaaaaaacccc
+abccaaaaaaaccccccccccaaaaacccaacaaaccciiiiiooouuuuupppkkklllaaaaaacccc
+abccaaaaaacccccccccccaaaaacccacccaaciiiiiiqooouuuuuupppkllllllacaccccc
+abcccaaaaaaaacccccccaaaaaaccccaacaiiiiiqqqqoouuuxuuupppppplllllccccccc
+abccaaaaaaaaaccaaaccaaaaaaccccaaaaiiiiqqqqqqttuxxxuuuppppppplllccccccc
+abccaaaaaaaacccaaaaaaaaaaacccaaaahiiiqqqttttttuxxxxuuuvvpppplllccccccc
+abcaaaaaaacccaaaaaaaaaaacccccaaaahhhqqqqtttttttxxxxuuvvvvvqqlllccccccc
+abcccccaaaccaaaaaaaaaccccccccacaahhhqqqttttxxxxxxxyyyyyvvvqqlllccccccc
+abcccccaaaccaaaaaaaacccccccccccaahhhqqqtttxxxxxxxyyyyyyvvqqqlllccccccc
+SbcccccccccccaaaaaaaaaccccccccccchhhqqqtttxxxxEzzzyyyyvvvqqqmmlccccccc
+abcccccccccccaaaaaaaacccaacccccccchhhppptttxxxxyyyyyvvvvqqqmmmcccccccc
+abccccccccccaaaaaaaaaaccaacccccccchhhpppptttsxxyyyyyvvvqqqmmmccccccccc
+abcaacccccccaaaaaaacaaaaaaccccccccchhhppppsswwyyyyyyyvvqqmmmmccccccccc
+abaaaacccccccaccaaaccaaaaaaacccccccchhhpppsswwyywwyyyvvqqmmmddcccccccc
+abaaaaccccccccccaaaccaaaaaaacccccccchhhpppsswwwwwwwwwvvqqqmmdddccccccc
+abaaaacccccccccaaaccaaaaaaccccccccccgggpppsswwwwrrwwwwvrqqmmdddccccccc
+abccccccaaaaaccaaaacaaaaaaccccccaacccggpppssswwsrrrwwwvrrqmmdddacccccc
+abccccccaaaaaccaaaacccccaaccccaaaaaacggpppssssssrrrrrrrrrnmmdddaaccccc
+abcccccaaaaaaccaaaccccccccccccaaaaaacggppossssssoorrrrrrrnnmdddacccccc
+abcccccaaaaaaccccccccaaaaccccccaaaaacgggoooossoooonnnrrnnnnmddaaaacccc
+abccccccaaaaaccccccccaaaacccccaaaaaccgggoooooooooonnnnnnnnndddaaaacccc
+abccccccaaaccccccccccaaaacccccaaaaacccgggoooooooffennnnnnnedddaaaacccc
+abcccccccccccccccccccaaacccccccaacccccggggffffffffeeeeeeeeeedaaacccccc
+abccccccccccccccccccaaacccccaccaaccccccggfffffffffeeeeeeeeeecaaacccccc
+abccccccccccccccccccaaaacccaaaaaaaaaccccfffffffaaaaaeeeeeecccccccccccc
+abccccccccaacaaccccaaaaaacaaaaaaaaaaccccccccccaaaccaaaaccccccccccccccc
+abccccccccaaaaacccaaaaaaaaaaacaaaaccccccccccccaaaccccaaccccccccccaaaca
+abcccccccaaaaaccccaaaaaaaaaaacaaaaacccccccccccaaaccccccccccccccccaaaaa
+abcccccccaaaaaacccaaaaaaaaaacaaaaaacccccccccccaaccccccccccccccccccaaaa
+abcccccccccaaaaccaaaaaaaaaaaaaaccaaccccccccccccccccccccccccccccccaaaaa
diff --git a/2022/Rust/input/day12.test b/2022/Rust/input/day12.test
new file mode 100644
index 0000000..86e9cac
--- /dev/null
+++ b/2022/Rust/input/day12.test
@@ -0,0 +1,5 @@
+Sabqponm
+abcryxxl
+accszExk
+acctuvwj
+abdefghi
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));
+}