commit 1ce671e08a6511e52ac4bad02a4e49af4906a0c5
parent 4f5e25bf1cb56099850e056dd397f7fce89b4ba4
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Mon, 12 Dec 2022 20:24:28 -0500
Add 2022 day 12
Diffstat:
3 files changed, 188 insertions(+), 0 deletions(-)
diff --git a/2022/day12/Cargo.toml b/2022/day12/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "day12"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
diff --git a/2022/day12/input.txt b/2022/day12/input.txt
@@ -0,0 +1,41 @@
+abccccaaacaccccaaaaacccccccaaccccccccaaaaaaccccccaaaaaccccccccccaaaaaaaaacccccccaaaaaaaaaaaaaaccaaaaaccccccccccccaccacccccccccccccccccccccccccccccccccccccccaaaaaa
+abccaacaaaaaccaaaaacccccaaaaaccccccccaaaaaaccccccaaaaaacccccccccaaaaaaaaaaaaacccaaaaaaaaaaaaaaaaaaaaaccccccccccccaaaacccccccccccccccccccccccccccccccccccccccaaaaaa
+abccaaaaaaaaccaaaaaacccccaaaaaccccccaaaaaaaacccccaaaaaaccccccccccaaaaaaaaaaaacccaaaaaacaaaaaacaaaaaaaaccccccccccaaaaacccccaccccccccccccccccccaaacccccccccccccaaaaa
+abcccaaaaaccccccaaaacccccaaaaacccccaaaaaaaaaaccccaaaaaacccccccccaaaaaaaaaaaaaacaaaaaaaaaaaaaacaaaaaaaaccccccccccaaaaaacccaaacccccccccccccccccaaaccccccccccccccaaaa
+abaaacaaaaacccccacccccccaaaaaccccccaaaaaaaaaaccccccaaaccccccccccaaaaaaaaacaaaaaaaaaaaaaaaaaaacccaaacaccaaaccccccaaaaaaaacaaacccccccccccaaccccaaacccccccccccccccaac
+abaaacaacaaaaccccccccccccccaaccccccacaaaaacccccaacccccccccccccccaaaacaaaaaaaaaacccaacccaaacaacccaaccccaaaaccccccccaacaaaaaaaaaaccccccccaaaaccaaaccccccccccccccaaac
+abaaccaaccaaacacccccccccccccccccccccccaaaacccaaaaaaccaaaccccccccccaacaaaaaaaaaacccaaccccccccccccccccccaaaaccccccccccccaaaaaaaaaccccccciiiiiaaaaacccccccccccccccccc
+abaaccccaaaaaaaacccccccccccccccccccccccaaccccaaaaaaccaaaaaccccacccaaccaaacaaaaacccccccccccccccaacccccccaaaccccccccccccccaaaaacccccccciiiiiiiiaaaaaccccccaaaccccccc
+abaaacccaaaaaaaacccccccccccccccccccccccccccccaaaaaacaaaaaccccaaaaaaaccaaccaaacccccccaaaaacacccaaccccccccccaacccccccccccaaaaaaccccccciiiiiiiiijjaaaaaccccaaacaccccc
+abaaaccccaaaaaaccccccccccccccccccccaaccccccccaaaaaccaaaaacccccaaaaaaaaccccccccccccccaaaaaaaaaaaaccccccccccaaacaaccccccaaaaaaaccccccciiinnnnoijjjjjjjjjjaaaaaaacccc
+abccccccccaaaaacccccaacccccccccccaaaacccccccccaaaacccaaaaaccccaaaaaaaaacccccccccccccaaaaaaaaaaaaaaccccccccaaaaaacccaacaaacaaacccccchhinnnnnoojjjjjjjjjkkaaaaaacccc
+abcccccccaaaaaacaaacaacccccccccccaaaaaaccccccccccccccaacccccccaaaaaaaaacaaccccccccccaaaaaaaaaaaaaaacccccaaaaaaacccaaaaccccccacaaccchhinnnnnoooojjjjjjkkkkaaaaccccc
+abaacccaccaaaccccaaaaaccccccccccccaaaaccccccccccccccccccccccccaaaaaaaacaaaaaaaccccccaaaaaaaaaaaaaaacccccaaaaaaacccaaaaccccaaacaaachhhnnntttuooooooooppkkkaaaaccccc
+abaacccaaaaaaaccccaaaaaacccccccccaaaaaccccccccccccccccccccccccaaaaaaacccaaaaacccccccccaaacaaaaaaaaccccccccaaaaacccaaaacccccaaaaacchhhnnnttttuooooooppppkkkaaaccccc
+abaacccaaaaaaccccaaaaaaacccccccccaacaaccccccccccccccccccccccaaaccaaaccaaaaaaacccccccccccccaaaaaaaccccccaacaacaaacccccccccccaaaaaahhhhnntttttuuouuuuupppkkkcccccccc
+abaaaacaaaaaaaaaaaaaaacccccccccccccccccccccccccccccccccccccaaaacccaaacaaaaaaaaccccccccccccaccaaaccccccaaacaaccccccccccccccaaaaaahhhhnnntttxxxuuuuuuupppkkkcccccccc
+abaaaacaaaaaaaaaaacaaacccaaacccccccccccccccccccccacccccccccaaaacccccccaaaaaaaaccccccccccccccccaaacccccaaacaaacccccccccccccaaaaaahhhhmnnttxxxxuuyuuuuuppkkkcccccccc
+abaaaccaaaaaaaaccccaaaccccaaaccacccccccccccaaaaaaaaccccccccaaaacccccccccaaacaacccccccccccccccccccccaaaaaaaaaacccccacccccccaacaghhhmmmmtttxxxxxxyyyuupppkkccccccccc
+abaaccaaaaaaaccccccccccccaaaaaaaacccccccccccaaaaaaccccccccccccccccccccccaaccccccaacccccccccccccccccaaaaaaaaacccccaaccccccccccagggmmmmttttxxxxxyyyyvvppkkkccccccccc
+abaacccaccaaacccccccccccaaaaaaaaccccccccccccaaaaaaccccccccccccccccccccccccccaaacaaaccccccccccccccccccaaaaaccccaaaaacaacccccccgggmmmmttttxxxxxyyyyvvpppiiiccccccccc
+SbaaaaaccccaaccccccccccaaaaaaaaacacccccccccaaaaaaaacccccccccccccccaacccccccccaaaaaccccccccccaaaacccccaaaaaacccaaaaaaaaccaaaccgggmmmsssxxxEzzzzyyvvvpppiiiccccccccc
+abaaaaaccccccccccccccccaaaaaaaaaaaaaaaaaccaaaaaaaaaacccccccccccaaaaacccccccccaaaaaaaccccccccaaaaaccccaaaaaaaccccaaaaacccaaaaagggmmmsssxxxxxyyyyyyvvqqqiiiccccccccc
+abaaaaacccccccccccccccccaaaaaaaacaaaaaacccaaaaaaaaaaccccccccccccaaaaacccccccaaaaaaaacccccccaaaaaaccccaaacaaacccaaaaacccaaaaaagggmmmssswwwwwyyyyyyyvvqqqiiicccccccc
+abaaaaccccccccccccccccccccaaaaaaaaaaaaacccacacaaacccccccccccccccaaaaacccccccaaaaaaaacccccccaaaaaaccccacccccccccaacaaaccaaaaaagggmmmsssswwwwyyyyyyyvvvqqiiicccccccc
+abaaaaacccccccccccccccccccaacccaaaaaaaaaccccccaaaccccccccccccccaaaaaccccccccaacaaacccccccccaaaaaacccccccccccccccccaaccccaaaaagggmmmmssssswwyywwvvvvvvqqiiicccccccc
+abaaaaaccccccccccccccccccaaacccaaaaaaaaaacccccaaaccccccaacccccccccaaccaaccccccaaaacaccccaacccaacccccccccccccccccccccccccaaaaccggglllllssswwwywwwvvvvqqqiiicccccccc
+abaccccccccccccccccccccccccccccaaaaaaaaaaccccaaaacccaaaacccccccccccccaaaccccccaaaaaaaaaaaacccccccccccccccccccccccccccccccccccccffffllllsswwwwwwrrqvqqqqiiicccccccc
+abccccccccccccccccccccccccccccccccaaacacaccccaaaacccaaaaaacccccccccaaaaaaaaccccaaaaaaaaaaaacccccccccccccccccccccccccccccccccccccfffflllssrwwwwrrrqqqqqqjjicccccccc
+abcccccccaaaccccccccaaccccccccccccaaacccccccccaaaccccaaaaacccccccccaaaaaaaaccaaaaaaacaaaaaaacccccccccccccccccccccccccccccccccccccfffflllrrwwwrrrrqqqqjjjjjcccccccc
+abaaaccaaaaacccccccaaacaaccccccccccaacccccccccccccccaaaaacccccccccccaaaaaacccaaaaaaaaaaaaaaaccccccccccccccccccccccccccccccccccccccffffllrrrrrrrkjjjjjjjjjcccaccccc
+abaaaccaaaaaacccccccaaaaacaacaaccccccccccccccccccccccccaacccccccccccaaaaaacccaaaaaaaaaaaaacccccccccccccccccccccccccccccccccccccccccfffllrrrrrrkkjjjjjjjcccccaccccc
+abaaaccaaaaaacccccaaaaaaccaaaaacccccccccccccccccccccccccccccccccccccaaaaaacccccaaacaaaaaaacccccccccccccccccccccccccccccccccccccccccfffllkkrrrkkkjjddcccccccaaacccc
+abaaaccaaaaaccccccaaaaaaaacaaaaaccccccccccccccccccccccccccccccccccccaaacaacccccaaaccccccaaaaccccaaaccccccccccccccccaaaccccccccccccccfeekkkkkkkkkdddddccccaaaaacccc
+abaaacccaaaaccccccaacaaaaaaaaaaaccccccccccccccccccccccccccccccccccccccaacaacccccccccccccccaaccccaaaacccccccccccccccaaaacccccccccccccceeekkkkkkdddddddcccaaacaccccc
+abaccccccccccccccccccaacccaaaaccccccccccccccccccccccccccccaaccaaccaacccaaaaccccccccccccaaaaaaaacaaaacccccccccccccccaaaacccaaaaacccccceeeekkkkdddddaaccccaacccccccc
+abccccccccccccccccccaaccccccaaccccccccccccaaacccccccccccccaaaaaaccaaaacaaaaacccccccccccaaaaaaaacaaaccccccccccccccccaaaacccaaaaaccccccceeeeeeedddcacacccccccccccccc
+abccccccccccccccccccccccccccccccccccccccccaaaacaacccccccccaaaaacccaaaaaaaaaaccccccccccccaaaaaacccccccccccccccccccccccccccaaaaaacccccccaeeeeeeddcccccccccccccccaaac
+abccccccccccccccccccccccccccccccccccccccccaaaaaaacccccccccaaaaaaccaaaaaaaacaccccccaaacaaaaaaaacccccccccccccccccccccccccccaaaaaacccccccccceeeeaaccccccccccccccccaaa
+abcccccccccccccccccccccccccccccccccccccccccaaaaaaccccccccaaaaaaaaccaaaaaaaccccccccaaaaaaaaaaaacccccccccccccccccccccccccccaaaaaacccccccccccccaaaccccccccccccccccaaa
+abccccccccccccccccccccccccccccccccccccccaaaaaaaaccccaaaccaaaaaaaacaaaaaaaaaacccccccaaaaaaaccaacccccccccccccccccccccccccccccaacccccccccccccccaaaccccccccccccccaaaaa
+abccccccccccccccccccccccccccccccccccccccaaaaaaaaacccaaaaccccaaccaaaaaaaaaaaaaccccaaaaaaaaaacccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccaaaaaa
diff --git a/2022/day12/src/main.rs b/2022/day12/src/main.rs
@@ -0,0 +1,139 @@
+use std::collections::{HashMap, VecDeque};
+
+#[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)]
+struct Coord(usize, usize);
+
+fn main() {
+ let input = std::fs::read_to_string("input.txt")
+ .unwrap()
+ .trim()
+ .split('\n')
+ .map(|s| s.chars().collect())
+ .collect();
+ // 437
+ println!("Part 1: {}", part_1(&input).unwrap());
+ // 430
+ println!("Part 2: {}", part_2(&input).unwrap());
+}
+
+fn reachable(a: char, b: char) -> bool {
+ let a = match a {
+ 'S' => 'a',
+ 'E' => 'z',
+ c => c,
+ };
+ let b = match b {
+ 'S' => 'a',
+ 'E' => 'z',
+ c => c,
+ };
+ b as u8 <= a as u8 + 1
+}
+
+fn part_1(input: &Vec<Vec<char>>) -> Option<usize> {
+ let x_max = input.len() - 1;
+ let y_max = input[0].len() - 1;
+ let (start, end) = {
+ let mut start = None;
+ let mut end = None;
+ for x in 0..input.len() {
+ for y in 0..input[0].len() {
+ if input[x][y] == 'S' {
+ start = Some(Coord(x, y));
+ } else if input[x][y] == 'E' {
+ end = Some(Coord(x, y));
+ }
+ }
+ }
+ (start.unwrap(), end.unwrap())
+ };
+ let mut steps = HashMap::new();
+ let mut queue = VecDeque::new();
+ steps.insert(start, 0);
+ queue.push_back((start, 0));
+ 'mainloop: while let Some((curr, step_count)) = queue.pop_front() {
+ let mut neighbors = Vec::new();
+ if curr.0 != x_max {
+ neighbors.push(Coord(curr.0 + 1, curr.1));
+ }
+ if curr.0 != 0 {
+ neighbors.push(Coord(curr.0 - 1, curr.1));
+ }
+ if curr.1 != y_max {
+ neighbors.push(Coord(curr.0, curr.1 + 1));
+ }
+ if curr.1 != 0 {
+ neighbors.push(Coord(curr.0, curr.1 - 1));
+ }
+ for next in neighbors {
+ let step_count_next = step_count + 1;
+ let next_elev = input[next.0][next.1];
+ if reachable(input[curr.0][curr.1], next_elev) {
+ let record = steps.get(&next);
+ if record.is_none() {
+ steps.insert(next.clone(), step_count_next);
+ if next_elev == 'E' {
+ break 'mainloop;
+ } else {
+ queue.push_back((next, step_count_next));
+ }
+ }
+ }
+ }
+ }
+ steps.get(&end).copied()
+}
+
+fn part_2(input: &Vec<Vec<char>>) -> Option<usize> {
+ let x_max = input.len() - 1;
+ let y_max = input[0].len() - 1;
+ let (_start, end) = {
+ let mut start = None;
+ let mut end = None;
+ for x in 0..input.len() {
+ for y in 0..input[0].len() {
+ if input[x][y] == 'S' {
+ start = Some(Coord(x, y));
+ } else if input[x][y] == 'E' {
+ end = Some(Coord(x, y));
+ }
+ }
+ }
+ (start.unwrap(), end.unwrap())
+ };
+ let mut steps = HashMap::new();
+ let mut queue = VecDeque::new();
+ steps.insert(end, 0);
+ queue.push_back((end, 0));
+ while let Some((curr, step_count)) = queue.pop_front() {
+ let mut neighbors = Vec::new();
+ if curr.0 != x_max {
+ neighbors.push(Coord(curr.0 + 1, curr.1));
+ }
+ if curr.0 != 0 {
+ neighbors.push(Coord(curr.0 - 1, curr.1));
+ }
+ if curr.1 != y_max {
+ neighbors.push(Coord(curr.0, curr.1 + 1));
+ }
+ if curr.1 != 0 {
+ neighbors.push(Coord(curr.0, curr.1 - 1));
+ }
+ for next in neighbors {
+ let step_count_next = step_count + 1;
+ let next_elev = input[next.0][next.1];
+ if reachable(next_elev, input[curr.0][curr.1]) {
+ let record = steps.get(&next);
+ if record.is_none() {
+ steps.insert(next.clone(), step_count_next);
+ if next_elev == 'S' || next_elev == 'a' {
+ return Some(step_count_next);
+ } else {
+ queue.push_back((next, step_count_next));
+ }
+ }
+ }
+ }
+ }
+ None
+}