complete day 12

10 files changed, 613 insertions, 2 deletions

diff --git a/Cargo.lock b/Cargo.lock
index c636331..9e1997f 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -250,12 +250,36 @@ dependencies = [
 ]
 
 [[package]]
+name = "day12a"
+version = "0.1.0"
+dependencies = [
+ "clap",
+ "itertools",
+ "pathfinding",
+]
+
+[[package]]
+name = "day12b"
+version = "0.1.0"
+dependencies = [
+ "clap",
+ "itertools",
+ "pathfinding",
+]
+
+[[package]]
 name = "either"
 version = "1.8.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "90e5c1c8368803113bf0c9584fc495a58b86dc8a29edbf8fe877d21d9507e797"
 
 [[package]]
+name = "fixedbitset"
+version = "0.4.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0ce7134b9999ecaf8bcd65542e436736ef32ddca1b3e06094cb6ec5755203b80"
+
+[[package]]
 name = "hashbrown"
 version = "0.12.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -287,6 +311,15 @@ dependencies = [
 ]
 
 [[package]]
+name = "integer-sqrt"
+version = "0.1.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "276ec31bcb4a9ee45f58bec6f9ec700ae4cf4f4f8f2fa7e06cb406bd5ffdd770"
+dependencies = [
+ "num-traits",
+]
+
+[[package]]
 name = "itertools"
 version = "0.10.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -324,6 +357,15 @@ dependencies = [
 ]
 
 [[package]]
+name = "num-traits"
+version = "0.2.15"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "578ede34cf02f8924ab9447f50c28075b4d3e5b269972345e7e0372b38c6cdcd"
+dependencies = [
+ "autocfg",
+]
+
+[[package]]
 name = "once_cell"
 version = "1.16.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -336,6 +378,21 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "9b7820b9daea5457c9f21c69448905d723fbd21136ccf521748f23fd49e723ee"
 
 [[package]]
+name = "pathfinding"
+version = "4.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "c66505cf9c582f34ae89f6433c16ccc05f88803a36adff59c812188021edee78"
+dependencies = [
+ "fixedbitset",
+ "indexmap",
+ "integer-sqrt",
+ "itertools",
+ "num-traits",
+ "rustc-hash",
+ "thiserror",
+]
+
+[[package]]
 name = "proc-macro-error"
 version = "1.0.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -378,6 +435,12 @@ dependencies = [
 ]
 
 [[package]]
+name = "rustc-hash"
+version = "1.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "08d43f7aa6b08d49f382cde6a7982047c3426db949b1424bc4b7ec9ae12c6ce2"
+
+[[package]]
 name = "strsim"
 version = "0.10.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -410,6 +473,26 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "222a222a5bfe1bba4a77b45ec488a741b3cb8872e5e499451fd7d0129c9c7c3d"
 
 [[package]]
+name = "thiserror"
+version = "1.0.38"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "6a9cd18aa97d5c45c6603caea1da6628790b37f7a34b6ca89522331c5180fed0"
+dependencies = [
+ "thiserror-impl",
+]
+
+[[package]]
+name = "thiserror-impl"
+version = "1.0.38"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1fb327af4685e4d03fa8cbcf1716380da910eeb2bb8be417e7f9fd3fb164f36f"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "syn",
+]
+
+[[package]]
 name = "unicode-ident"
 version = "1.0.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/Cargo.toml b/Cargo.toml
index c0bc003..e91aa7e 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -23,8 +23,8 @@ members = [
     "day10b",
     "day11a",
     "day11b",
-    # "day12a",
-    # "day12b",
+    "day12a",
+    "day12b",
     # "day13a",
     # "day13b",
     # "day14a",
diff --git a/day12a/Cargo.toml b/day12a/Cargo.toml
new file mode 100644
index 0000000..3f67904
--- /dev/null
+++ b/day12a/Cargo.toml
@@ -0,0 +1,11 @@
+[package]
+name = "day12a"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+clap = { version = "3.2.20", features = ["derive"] }
+itertools = "0.10.5"
+pathfinding = "4.2.0"
diff --git a/day12a/examples/input.txt b/day12a/examples/input.txt
new file mode 100644
index 0000000..4b447da
--- /dev/null
+++ b/day12a/examples/input.txt
@@ -0,0 +1,41 @@
+abccccaaaaaaaaaaaaaccaaaaaaaacccccccccaaaaaaaaccccccccaaacaaacccccccaaaaaaccccccccccccccccccccccaaaacccccccccccacccccccccccccccccccccccccccccccccccccccccccccccaaaa
+abccccaaaaacaaaaaaccccaaaaaaccccccccccaaaaaaacccccccccaaaaaaacccccaaaaaaaaaacccccccccccccccccccaaaaaacccccccccaaaaaaaaccccccccccccccccccccccccccccccccccccccccaaaaa
+abcccaaaaaccaaaaaaccccaaaaaaccccccaacccaaaaaacccccccccaaaaaacccaaaaaaaaaaaaaaacaaccacccccccccccaaaaaaccccccccccaaaaaacccccccccccccccccccccccccccccccccccccccccaaaaa
+abccccccaaccaaaaaaccaaaaaaaaccccccaaacaaaacaaacccccccaaaaaaaaccaaaaaaaaaaaaaaacaaaaacccccccccccccaaccccccccccccaaaaaaccccccccccccccccccccccccccccacccccccccccaaaaaa
+abccccccccccaaccaaccaaaaccaacccccccaaaaaaaccccccccccaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaacccccccaaaaccccccccccccccccaaaaaaaacccccccccccccccccccccccccccaaccccccccccccccaa
+abcccccccaaaaacccaaaaaaaacccaaccccaaaaaaccccccccccccaaaaaaaaaaaaaaaacaaaaaaaccaaaaaaccccccaaaaaccccccccccccccaaaaaaaaaaccaccccccccccccccccccccccccaccccccccccccccca
+abcccccccaaaaacccaaaaaaaaccaaaaccaaaaaaaaccccccccccccccaaacaaaaaaaaacaaaaaacccccaaaacccccaaaaaaccccccccccccccaaaaaaaaaaaaacccccccccccccccllllllccccdccccccccccccccc
+abccccccaaaaaacccccaaaaccccaaaaacaaaaaaaaccccccccccccccaaacccccaaaccccaaaaaacccaaccccccccaaaaaacccccccccccccccccaaaaaaaaaacccccccccccccklllllllllcddddccaccaaaccccc
+abccccccaaaaaacccccaaaaaaaaaaaaaaaccaaccccccaacaacccccccaaccccccccccccaaacaacccccccccccccaaaaaacccccccccccccccccaaaaaaaaaacccccccccccckklllppllllcddddddddaaaaccccc
+abccccccaaaaaaccccaaacaaaaaaaaaaaaccaaccccccaaaaaccccccccccccccccccccccccccccccccccccccccccaaccccccaaccccccccccccaacaaaaaaaccccccccccckklpppppplllmdddddddddacccccc
+abccccccccaaacccccaacccaccaaaaaaccccccccccccaaaaaaccccccccccccccccccccccccccccccccccccccccccccccccaaaaccccccccccccaaaaaaaaaaccccccccckkkkppppppplmmmmmmddddddaacccc
+abccccaaacaaacccccccccccccaaaaaaccccccccccccaaaaaacccccccccccccccccaaaccccccccccccccccccccccccccccaaaaccccccccccccaaaaaaaaaaccccccccckkkppppuppppmmmmmmmmddeeeacccc
+abccccaaaaaaacccccccccccccaaaaaacccaccccccccaaaaaacccccccccccccccccaaaacccccccccccccccccccccaaacccaaaacccccccccccaaaacaaaccccccccccckkkpppuuuuuppqqmmmmmmmmeeeacccc
+abcccccaaaaaaccccccccccccaaaaaaaacaaccccccccccaaaccccccccccccccccccaaaaccccccccccccccccccccaaaaccccccccccccccccccaaaaaaaacccccccccckkkkpppuuuuupqqqqqqqmmmmeeeccccc
+abcccccaaaaaaaacccccccccccaccccaaaaacccccccccccccccccccccccccccccccaaaccccccccccccccaaaccccaaaacccccccccccccaaccaaaaaaaaccccccccckkkkkrrpuuuxuuuqqqqqqqqmmmmeeccccc
+abccccaaaaaaaaaccccccccccccccaaaaaacccccccacaacccccccccccccccccccccccccccccccccccccaaaaaacccaaaccccccccccaaaaccaaaaaaacccccccccckkkkrrrrruuuxxuvvvvvvqqqqnnneeccccc
+abcccaaaaaaaaaaccccccccccccccaaaaaaaacccccaaaaacccccccccccccccaaaaaccccccccccccccccaaaaaaccccccccccccccccaaaaaaaaaaaaacccccccccjjjkrrrrruuuxxxxvvvvvvvqqqnnneeccccc
+abcaaaaacaaacccccccccccccccccaaaaaaaacccccaaaaaccaacccccccccccaaaaaccccccccccccccccaaaaaccccccccccccccccccaaaaaccaaaaaacccccccjjjrrrrruuuuuxxxyvyyyvvvqqqnneeeccccc
+abcaaaaacaaaccaaccccccccccccccccaacccccccaaaaaaaaaaaccccccccccaaaaaaccccccccccccccccaaaaaccccccccccccccccaaaaacccaaaaaaaacaaacjjjrrrtttuuxxxxxyyyyyvvvqqnnneeeccccc
+abaaaaaccaacccaaaccaacccaaccccccaccccccccaaaaaaaaaacccccccccccaaaaaaccccccccccccccccaacaacccccccccccccccccccaacccaaccccaaaaaacjjjrrrtttxxxxxxxyyyyyvvvrrnnneeeccccc
+SbaaaaacccccccaaaaaaaccaaaacccccccccccccccaaaaaaaaacccccccccccaaaaaaccccccccccccccccccccccccccccccccccccccccccccccaacccaaaaaacjjjrrrtttxxxEzzzzyyyvvvrrnnneeecccccc
+abcaaaaacccccccaaaaaaccaaaacccccccccccccccaaaaaaaaacccccccccccccaaccccccccccccccccccccccccccccaaccccccccccaaccccacaaaacaaaaaaajjjrrrtttxxxxxyyyyyvvvrrrnnnfffcccccc
+abcaacccccccaaaaaaaacccaaaaccccccccccccccccaaaaaaaaaaccccccccccccccccccccccccccccccccccccccaaaaaccccccccccaaccccaaaaaaaaaaaaaajjjqqqttttxxxxyyyyyyvvrrrnnnfffcccccc
+abccccccccccaaaaaaaaaccccccccccccccccccccaaaaaaaaaaaaacccccccccccccccccaacccccccccccccccccccaaaaaccccccaacaaaaaccaaaacaaaaaaaacjjjqqqqttttxxyywyyyywvrrnnnfffcccccc
+abccccccccccaaaaaaaaaacccccccccccccccccccaaaaaaaaacaaacccccccccccccaaacaacccccccccccccccccccaaaaaccccccaaaaaaaaccaaaaccccaaacccjjjjqqqqtttxwywwwyywwwrrnnnfffcccccc
+abcccccccccccccaaaaaaacccccccccccccccccccaaaaaaaaaaaaaaaacccccccccccaaaaaccccccccccccccccccaaaaacccaaccccaaaaccccaacaacccaaaccccjjjiqqqtttwwywwwwwwwwrrroofffcccccc
+abcccccccccccccaaaccccccccccccccccccccccaaaaaaaaaaaaaaaaaccccccccccccaaaaaacccccccccccccccccccaaacaaaccccaaaaaccccccccccccccccccciiiiqqqttwwwwwswwwwrrrroofffcccccc
+abcccccccccccccaaccccccccccccaaaacccccccaaaaaaaaccaaaaacccccccccccccaaaaaaacccccccccccccccccccaaaaaaacccaaacaacccccaaaaacccccccccciiiqqqttwwwwsssssrrrrroofffaccccc
+abcccccccccccccccccccccccccccaaaaccccccccacaaacccaaaaaaccccccaaccccaaaaaaccccccccaacaaccccccccaaaaaaccccaaaacacccccaaaaacccccccccciiiqqqtsswsssssssrrrrooofffaccccc
+abcccccccccccccccccccccccccccaaaaccccccccccaaaccaaaaaaaccccccaaaaccaacaaaccccccccaaaaacccccccccaaaaaaaaccaaacacccccaaaaaacccccccccciiqqqssssssspposrrroooofffaccccc
+abccccaaacccccccccccccccccccccaaacccccccccccccccaaacaaaccccaaaaaacccccaaaccccccccaaaaaacccccccaaaaaaaaaaaaaaaaaccccaaaaaaccccccaccciiiqqpsssssppppooooooogffaaccccc
+abccccaaaaaacccaaaccccccccccccccccccccccccccccccccccccaccccaaaaacccccccccccccccccaaaaaaccccccaaaaaaaaaaaaaaaaaaccccaaaaaacccaaaaccciiiqqppppppppppoooooogggfaaacccc
+abcccaaaaaaacccaaaccccccccccccccccccccccccccccccccccccccccccaaaaaccccccccccccccccaaaaaaccccccaaacaaaccccaaaaaacccccccaacccccaaaaaacciiipppppppphgggggggggggaaaacccc
+abccaaaaaaaacccaaacaaacccccccccccccccccccccaacccccccccccccccaacaacccccaacccccccccccaaacccccccccccaaacccccaaaaacccccccccccccccaaaaacciiihppppphhhhgggggggggaaccccccc
+abccaaaaaaacaaaaaaaaaacccccccccccccccccccccaaaccccccacccccccccccccccccaaccccccccccccccccccccccccaaaaccccaaaaaaccccccccccccccaaaaacccciihhhhhhhhhhgggggggccaaccccccc
+abccccaaaaaaaaaaaaaaacccccccccccccccccccaaaaaaaaccccaaacaaaccccccccccaaaaccaaccccccccaacaacccccaaaaaaacccaacccccccccccccccccaacaaccccchhhhhhhhhaaaacccccccccccccccc
+abccccaaaaaacaaaaaaaccccccccccccccccccccaaaaaaaaccccaaaaaaaccccccccccaaaaaaaacaccccccaaaaaccccccaaaaacccccccccccccccccccccccccccccccccchhhhhhacaaaaaccccccccccccccc
+abccccaaccccccaaaaaacccccccccccccaaccccccaaaaaacccccaaaaaaccccccaaaaaaaaaaaaaaaccccccaaaaaacccaaaaaaacccccccccccccccccccccccccccccccccccccaaaaccaaacccccccccccaaaca
+abccccccccccccaaaaaaaccccccccccccaaccccccaaaaaacccaaaaaaaaccccccaaaaaaaaaaaaaacccccccaaaaaacccaaaaaaaaccccccaaacccccccccccccccccccccccccccaaaaccccccccccccccccaaaaa
+abccaaacccccccaaacaaacccccccccaaaaaaaacccaaaaaacccaaaaaaaaacccccaaaaaaaaaaaaaacccccccaaaaaccccaaaaaaaaccccccaaaaccccccccccccccccccccccccccaaaccccccccccccccccccaaaa
+abcaaaacccccccaaccccccccccccccaaaaaaaacccaaccaacccaaaaaaaaaaccccccccaaaaaaacaacccccccccaaaccccccaaacaaccccccaaaacccccccccccccccccccccccccccccccccccccccccccccaaaaaa
diff --git a/day12a/examples/test.txt b/day12a/examples/test.txt
new file mode 100644
index 0000000..86e9cac
--- /dev/null
+++ b/day12a/examples/test.txt
@@ -0,0 +1,5 @@
+Sabqponm
+abcryxxl
+accszExk
+acctuvwj
+abdefghi
diff --git a/day12a/src/main.rs b/day12a/src/main.rs
new file mode 100644
index 0000000..2ae1c4b
--- /dev/null
+++ b/day12a/src/main.rs
@@ -0,0 +1,212 @@
+/// --- Day 12: Hill Climbing Algorithm ---
+///
+/// You try contacting the Elves using your handheld device, but the river you're following must be
+/// too low to get a decent signal.
+///
+/// You ask the device for a heightmap of the surrounding area (your puzzle input).  The heightmap
+/// shows the local area from above broken into a grid; the elevation of each square of the grid is
+/// given by a single lowercase letter, where a is the lowest elevation, b is the next-lowest, and
+/// so on up to the highest elevation, z.
+///
+/// Also included on the heightmap are marks for your current position (S) and the location that
+/// should get the best signal (E).  Your current position (S) has elevation a, and the location
+/// that should get the best signal (E) has elevation z.
+///
+/// You'd like to reach E, but to save energy, you should do it in as few steps as possible.
+/// During each step, you can move exactly one square up, down, left, or right.  To avoid needing
+/// to get out your climbing gear, the elevation of the destination square can be at most one
+/// higher than the elevation of your current square; that is, if your current elevation is m, you
+/// could step to elevation n, but not to elevation o.  (This also means that the elevation of the
+/// destination square can be much lower than the elevation of your current square.)
+///
+/// For example:
+///
+/// ```
+/// Sabqponm
+/// abcryxxl
+/// accszExk
+/// acctuvwj
+/// abdefghi
+/// ```
+///
+/// Here, you start in the top-left corner; your goal is near the middle.  You could start by
+/// moving down or right, but eventually you'll need to head toward the e at the bottom.  From
+/// there, you can spiral around to the goal:
+///
+/// ```
+/// v..v<<<<
+/// >v.vv<<^
+/// .>vv>E^^
+/// ..v>>>^^
+/// ..>>>>>^
+/// ```
+///
+/// In the above diagram, the symbols indicate whether the path exits each square moving up (^),
+/// down (v), left (<), or right (>).  The location that should get the best signal is still E, and
+/// . marks unvisited squares.
+///
+/// This path reaches the goal in 31 steps, the fewest possible.
+///
+/// What is the fewest steps required to move from your current position to the location that
+/// should get the best signal?
+use clap::Parser;
+use itertools::Itertools;
+use pathfinding::prelude::bfs;
+
+use std::fs::File;
+use std::hash::{Hash, Hasher};
+use std::io::prelude::*;
+use std::io::BufReader;
+use std::path::PathBuf;
+
+const FILEPATH: &'static str = "examples/input.txt";
+
+#[derive(Parser, Debug)]
+#[clap(author, version, about, long_about = None)]
+struct Cli {
+    #[clap(short, long, default_value = FILEPATH)]
+    file: PathBuf,
+}
+
+#[derive(Clone, Debug)]
+struct Arena(Vec<Vec<Node>>);
+
+#[derive(Copy, Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
+struct Pos(usize, usize);
+
+#[derive(Clone, Debug)]
+struct Node {
+    pos: Pos,
+    value: char,
+    connected: Vec<Pos>,
+}
+
+impl Node {
+    fn new(pos: Pos, value: char) -> Self {
+        Node {
+            pos,
+            value,
+            connected: Vec::new(),
+        }
+    }
+}
+
+impl PartialEq for Node {
+    fn eq(&self, other: &Self) -> bool {
+        self.pos == other.pos
+    }
+}
+
+impl Eq for Node {}
+
+impl Hash for Node {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        self.pos.hash(state);
+    }
+}
+
+impl Arena {
+    fn get(&self, coords: Pos) -> &Node {
+        &self.0[coords.0][coords.1]
+    }
+
+    fn get_mut(&mut self, coords: Pos) -> &mut Node {
+        &mut self.0[coords.0][coords.1]
+    }
+}
+
+fn is_connected(x: char, y: char) -> bool {
+    let (x, y) = match (x, y) {
+        ('S', _) => ('a', y),
+        ('E', _) => ('z', y),
+        (_, 'S') => (x, 'a'),
+        (_, 'E') => (x, 'z'),
+        _ => (x, y),
+    };
+
+    let (x, y) = (x as i8, y as i8);
+    i8::abs(x - y) <= 1 || x > y
+}
+
+fn main() {
+    let args = Cli::parse();
+
+    let file = File::open(&args.file).unwrap();
+    let reader = BufReader::new(file);
+
+    let mut arena = Arena(Vec::new());
+    let _ = reader
+        .lines()
+        .enumerate()
+        .map(|(idx, l)| {
+            l.unwrap()
+                .chars()
+                .enumerate()
+                .map(|(idy, c)| Node::new(Pos(idx, idy), c))
+                .collect_vec()
+        })
+        .scan(&mut arena, |arena, row| {
+            arena.0.push(row);
+            Some(())
+        })
+        .last();
+
+    let xdim = arena.0.len();
+    let ydim = arena.0[0].len();
+
+    let mut start_pos = None;
+    let mut end_pos = None;
+
+    for idx in 0..xdim {
+        for idy in 0..ydim {
+            let node_val = arena.get(Pos(idx, idy)).value;
+
+            match node_val {
+                'S' => start_pos = Some(Pos(idx, idy)),
+                'E' => end_pos = Some(Pos(idx, idy)),
+                _ => (),
+            }
+
+            if idx != 0 {
+                let up_idx = Pos(idx - 1, idy);
+                if is_connected(node_val, arena.get(up_idx).value) {
+                    arena.get_mut(Pos(idx, idy)).connected.push(up_idx);
+                }
+            }
+
+            if idx != xdim - 1 {
+                let down_idx = Pos(idx + 1, idy);
+                if is_connected(node_val, arena.get(down_idx).value) {
+                    arena.get_mut(Pos(idx, idy)).connected.push(down_idx);
+                }
+            }
+
+            if idy != 0 {
+                let left_idx = Pos(idx, idy - 1);
+                if is_connected(node_val, arena.get(left_idx).value) {
+                    arena.get_mut(Pos(idx, idy)).connected.push(left_idx);
+                }
+            }
+
+            if idy != ydim - 1 {
+                let right_idx = Pos(idx, idy + 1);
+                if is_connected(node_val, arena.get(right_idx).value) {
+                    arena.get_mut(Pos(idx, idy)).connected.push(right_idx);
+                }
+            }
+        }
+    }
+
+    let start = arena.get(start_pos.unwrap());
+    let end = arena.get(end_pos.unwrap());
+
+    let res = bfs(
+        &start,
+        |n| n.connected.iter().map(|&p| arena.get(p)),
+        |&n| n == end,
+    )
+    .unwrap()
+    .len()
+        - 1;
+    println!("{res}");
+}
diff --git a/day12b/Cargo.toml b/day12b/Cargo.toml
new file mode 100644
index 0000000..b5465cf
--- /dev/null
+++ b/day12b/Cargo.toml
@@ -0,0 +1,11 @@
+[package]
+name = "day12b"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+clap = { version = "3.2.20", features = ["derive"] }
+itertools = "0.10.5"
+pathfinding = "4.2.0"
diff --git a/day12b/examples/input.txt b/day12b/examples/input.txt
new file mode 100644
index 0000000..4b447da
--- /dev/null
+++ b/day12b/examples/input.txt
@@ -0,0 +1,41 @@
+abccccaaaaaaaaaaaaaccaaaaaaaacccccccccaaaaaaaaccccccccaaacaaacccccccaaaaaaccccccccccccccccccccccaaaacccccccccccacccccccccccccccccccccccccccccccccccccccccccccccaaaa
+abccccaaaaacaaaaaaccccaaaaaaccccccccccaaaaaaacccccccccaaaaaaacccccaaaaaaaaaacccccccccccccccccccaaaaaacccccccccaaaaaaaaccccccccccccccccccccccccccccccccccccccccaaaaa
+abcccaaaaaccaaaaaaccccaaaaaaccccccaacccaaaaaacccccccccaaaaaacccaaaaaaaaaaaaaaacaaccacccccccccccaaaaaaccccccccccaaaaaacccccccccccccccccccccccccccccccccccccccccaaaaa
+abccccccaaccaaaaaaccaaaaaaaaccccccaaacaaaacaaacccccccaaaaaaaaccaaaaaaaaaaaaaaacaaaaacccccccccccccaaccccccccccccaaaaaaccccccccccccccccccccccccccccacccccccccccaaaaaa
+abccccccccccaaccaaccaaaaccaacccccccaaaaaaaccccccccccaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaacccccccaaaaccccccccccccccccaaaaaaaacccccccccccccccccccccccccccaaccccccccccccccaa
+abcccccccaaaaacccaaaaaaaacccaaccccaaaaaaccccccccccccaaaaaaaaaaaaaaaacaaaaaaaccaaaaaaccccccaaaaaccccccccccccccaaaaaaaaaaccaccccccccccccccccccccccccaccccccccccccccca
+abcccccccaaaaacccaaaaaaaaccaaaaccaaaaaaaaccccccccccccccaaacaaaaaaaaacaaaaaacccccaaaacccccaaaaaaccccccccccccccaaaaaaaaaaaaacccccccccccccccllllllccccdccccccccccccccc
+abccccccaaaaaacccccaaaaccccaaaaacaaaaaaaaccccccccccccccaaacccccaaaccccaaaaaacccaaccccccccaaaaaacccccccccccccccccaaaaaaaaaacccccccccccccklllllllllcddddccaccaaaccccc
+abccccccaaaaaacccccaaaaaaaaaaaaaaaccaaccccccaacaacccccccaaccccccccccccaaacaacccccccccccccaaaaaacccccccccccccccccaaaaaaaaaacccccccccccckklllppllllcddddddddaaaaccccc
+abccccccaaaaaaccccaaacaaaaaaaaaaaaccaaccccccaaaaaccccccccccccccccccccccccccccccccccccccccccaaccccccaaccccccccccccaacaaaaaaaccccccccccckklpppppplllmdddddddddacccccc
+abccccccccaaacccccaacccaccaaaaaaccccccccccccaaaaaaccccccccccccccccccccccccccccccccccccccccccccccccaaaaccccccccccccaaaaaaaaaaccccccccckkkkppppppplmmmmmmddddddaacccc
+abccccaaacaaacccccccccccccaaaaaaccccccccccccaaaaaacccccccccccccccccaaaccccccccccccccccccccccccccccaaaaccccccccccccaaaaaaaaaaccccccccckkkppppuppppmmmmmmmmddeeeacccc
+abccccaaaaaaacccccccccccccaaaaaacccaccccccccaaaaaacccccccccccccccccaaaacccccccccccccccccccccaaacccaaaacccccccccccaaaacaaaccccccccccckkkpppuuuuuppqqmmmmmmmmeeeacccc
+abcccccaaaaaaccccccccccccaaaaaaaacaaccccccccccaaaccccccccccccccccccaaaaccccccccccccccccccccaaaaccccccccccccccccccaaaaaaaacccccccccckkkkpppuuuuupqqqqqqqmmmmeeeccccc
+abcccccaaaaaaaacccccccccccaccccaaaaacccccccccccccccccccccccccccccccaaaccccccccccccccaaaccccaaaacccccccccccccaaccaaaaaaaaccccccccckkkkkrrpuuuxuuuqqqqqqqqmmmmeeccccc
+abccccaaaaaaaaaccccccccccccccaaaaaacccccccacaacccccccccccccccccccccccccccccccccccccaaaaaacccaaaccccccccccaaaaccaaaaaaacccccccccckkkkrrrrruuuxxuvvvvvvqqqqnnneeccccc
+abcccaaaaaaaaaaccccccccccccccaaaaaaaacccccaaaaacccccccccccccccaaaaaccccccccccccccccaaaaaaccccccccccccccccaaaaaaaaaaaaacccccccccjjjkrrrrruuuxxxxvvvvvvvqqqnnneeccccc
+abcaaaaacaaacccccccccccccccccaaaaaaaacccccaaaaaccaacccccccccccaaaaaccccccccccccccccaaaaaccccccccccccccccccaaaaaccaaaaaacccccccjjjrrrrruuuuuxxxyvyyyvvvqqqnneeeccccc
+abcaaaaacaaaccaaccccccccccccccccaacccccccaaaaaaaaaaaccccccccccaaaaaaccccccccccccccccaaaaaccccccccccccccccaaaaacccaaaaaaaacaaacjjjrrrtttuuxxxxxyyyyyvvvqqnnneeeccccc
+abaaaaaccaacccaaaccaacccaaccccccaccccccccaaaaaaaaaacccccccccccaaaaaaccccccccccccccccaacaacccccccccccccccccccaacccaaccccaaaaaacjjjrrrtttxxxxxxxyyyyyvvvrrnnneeeccccc
+SbaaaaacccccccaaaaaaaccaaaacccccccccccccccaaaaaaaaacccccccccccaaaaaaccccccccccccccccccccccccccccccccccccccccccccccaacccaaaaaacjjjrrrtttxxxEzzzzyyyvvvrrnnneeecccccc
+abcaaaaacccccccaaaaaaccaaaacccccccccccccccaaaaaaaaacccccccccccccaaccccccccccccccccccccccccccccaaccccccccccaaccccacaaaacaaaaaaajjjrrrtttxxxxxyyyyyvvvrrrnnnfffcccccc
+abcaacccccccaaaaaaaacccaaaaccccccccccccccccaaaaaaaaaaccccccccccccccccccccccccccccccccccccccaaaaaccccccccccaaccccaaaaaaaaaaaaaajjjqqqttttxxxxyyyyyyvvrrrnnnfffcccccc
+abccccccccccaaaaaaaaaccccccccccccccccccccaaaaaaaaaaaaacccccccccccccccccaacccccccccccccccccccaaaaaccccccaacaaaaaccaaaacaaaaaaaacjjjqqqqttttxxyywyyyywvrrnnnfffcccccc
+abccccccccccaaaaaaaaaacccccccccccccccccccaaaaaaaaacaaacccccccccccccaaacaacccccccccccccccccccaaaaaccccccaaaaaaaaccaaaaccccaaacccjjjjqqqqtttxwywwwyywwwrrnnnfffcccccc
+abcccccccccccccaaaaaaacccccccccccccccccccaaaaaaaaaaaaaaaacccccccccccaaaaaccccccccccccccccccaaaaacccaaccccaaaaccccaacaacccaaaccccjjjiqqqtttwwywwwwwwwwrrroofffcccccc
+abcccccccccccccaaaccccccccccccccccccccccaaaaaaaaaaaaaaaaaccccccccccccaaaaaacccccccccccccccccccaaacaaaccccaaaaaccccccccccccccccccciiiiqqqttwwwwwswwwwrrrroofffcccccc
+abcccccccccccccaaccccccccccccaaaacccccccaaaaaaaaccaaaaacccccccccccccaaaaaaacccccccccccccccccccaaaaaaacccaaacaacccccaaaaacccccccccciiiqqqttwwwwsssssrrrrroofffaccccc
+abcccccccccccccccccccccccccccaaaaccccccccacaaacccaaaaaaccccccaaccccaaaaaaccccccccaacaaccccccccaaaaaaccccaaaacacccccaaaaacccccccccciiiqqqtsswsssssssrrrrooofffaccccc
+abcccccccccccccccccccccccccccaaaaccccccccccaaaccaaaaaaaccccccaaaaccaacaaaccccccccaaaaacccccccccaaaaaaaaccaaacacccccaaaaaacccccccccciiqqqssssssspposrrroooofffaccccc
+abccccaaacccccccccccccccccccccaaacccccccccccccccaaacaaaccccaaaaaacccccaaaccccccccaaaaaacccccccaaaaaaaaaaaaaaaaaccccaaaaaaccccccaccciiiqqpsssssppppooooooogffaaccccc
+abccccaaaaaacccaaaccccccccccccccccccccccccccccccccccccaccccaaaaacccccccccccccccccaaaaaaccccccaaaaaaaaaaaaaaaaaaccccaaaaaacccaaaaccciiiqqppppppppppoooooogggfaaacccc
+abcccaaaaaaacccaaaccccccccccccccccccccccccccccccccccccccccccaaaaaccccccccccccccccaaaaaaccccccaaacaaaccccaaaaaacccccccaacccccaaaaaacciiipppppppphgggggggggggaaaacccc
+abccaaaaaaaacccaaacaaacccccccccccccccccccccaacccccccccccccccaacaacccccaacccccccccccaaacccccccccccaaacccccaaaaacccccccccccccccaaaaacciiihppppphhhhgggggggggaaccccccc
+abccaaaaaaacaaaaaaaaaacccccccccccccccccccccaaaccccccacccccccccccccccccaaccccccccccccccccccccccccaaaaccccaaaaaaccccccccccccccaaaaacccciihhhhhhhhhhgggggggccaaccccccc
+abccccaaaaaaaaaaaaaaacccccccccccccccccccaaaaaaaaccccaaacaaaccccccccccaaaaccaaccccccccaacaacccccaaaaaaacccaacccccccccccccccccaacaaccccchhhhhhhhhaaaacccccccccccccccc
+abccccaaaaaacaaaaaaaccccccccccccccccccccaaaaaaaaccccaaaaaaaccccccccccaaaaaaaacaccccccaaaaaccccccaaaaacccccccccccccccccccccccccccccccccchhhhhhacaaaaaccccccccccccccc
+abccccaaccccccaaaaaacccccccccccccaaccccccaaaaaacccccaaaaaaccccccaaaaaaaaaaaaaaaccccccaaaaaacccaaaaaaacccccccccccccccccccccccccccccccccccccaaaaccaaacccccccccccaaaca
+abccccccccccccaaaaaaaccccccccccccaaccccccaaaaaacccaaaaaaaaccccccaaaaaaaaaaaaaacccccccaaaaaacccaaaaaaaaccccccaaacccccccccccccccccccccccccccaaaaccccccccccccccccaaaaa
+abccaaacccccccaaacaaacccccccccaaaaaaaacccaaaaaacccaaaaaaaaacccccaaaaaaaaaaaaaacccccccaaaaaccccaaaaaaaaccccccaaaaccccccccccccccccccccccccccaaaccccccccccccccccccaaaa
+abcaaaacccccccaaccccccccccccccaaaaaaaacccaaccaacccaaaaaaaaaaccccccccaaaaaaacaacccccccccaaaccccccaaacaaccccccaaaacccccccccccccccccccccccccccccccccccccccccccccaaaaaa
diff --git a/day12b/examples/test.txt b/day12b/examples/test.txt
new file mode 100644
index 0000000..86e9cac
--- /dev/null
+++ b/day12b/examples/test.txt
@@ -0,0 +1,5 @@
+Sabqponm
+abcryxxl
+accszExk
+acctuvwj
+abdefghi
diff --git a/day12b/src/main.rs b/day12b/src/main.rs
new file mode 100644
index 0000000..9c422c3
--- /dev/null
+++ b/day12b/src/main.rs
@@ -0,0 +1,202 @@
+/// --- Part Two ---
+///
+/// As you walk up the hill, you suspect that the Elves will want to turn this into a hiking
+/// trail. The beginning isn't very scenic, though; perhaps you can find a better starting point.
+///
+/// To maximize exercise while hiking, the trail should start as low as possible: elevation a. The
+/// goal is still the square marked E. However, the trail should still be direct, taking the fewest
+/// steps to reach its goal. So, you'll need to find the shortest path from any square at elevation
+/// a to the square marked E.
+///
+/// Again consider the example from above:
+///
+/// ```
+/// Sabqponm
+/// abcryxxl
+/// accszExk
+/// acctuvwj
+/// abdefghi
+/// ```
+///
+/// Now, there are six choices for starting position (five marked a, plus the square marked S that
+/// counts as being at elevation a). If you start at the bottom-left square, you can reach the goal
+/// most quickly:
+///
+/// ```
+/// ...v<<<<
+/// ...vv<<^
+/// ...v>E^^
+/// .>v>>>^^
+/// >^>>>>>^
+/// ```
+///
+/// This path reaches the goal in only 29 steps, the fewest possible.
+///
+/// What is the fewest steps required to move starting from any square with elevation a to the
+/// location that should get the best signal?
+use clap::Parser;
+use itertools::Itertools;
+use pathfinding::prelude::bfs;
+
+use std::fs::File;
+use std::hash::{Hash, Hasher};
+use std::io::prelude::*;
+use std::io::BufReader;
+use std::path::PathBuf;
+
+const FILEPATH: &'static str = "examples/input.txt";
+
+#[derive(Parser, Debug)]
+#[clap(author, version, about, long_about = None)]
+struct Cli {
+    #[clap(short, long, default_value = FILEPATH)]
+    file: PathBuf,
+}
+
+#[derive(Clone, Debug)]
+struct Arena(Vec<Vec<Node>>);
+
+#[derive(Copy, Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
+struct Pos(usize, usize);
+
+#[derive(Clone, Debug)]
+struct Node {
+    pos: Pos,
+    value: char,
+    connected: Vec<Pos>,
+}
+
+impl Node {
+    fn new(pos: Pos, value: char) -> Self {
+        Node {
+            pos,
+            value,
+            connected: Vec::new(),
+        }
+    }
+}
+
+impl PartialEq for Node {
+    fn eq(&self, other: &Self) -> bool {
+        self.pos == other.pos
+    }
+}
+
+impl Eq for Node {}
+
+impl Hash for Node {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        self.pos.hash(state);
+    }
+}
+
+impl Arena {
+    fn get(&self, coords: Pos) -> &Node {
+        &self.0[coords.0][coords.1]
+    }
+
+    fn get_mut(&mut self, coords: Pos) -> &mut Node {
+        &mut self.0[coords.0][coords.1]
+    }
+}
+
+fn is_connected(x: char, y: char) -> bool {
+    let (x, y) = match (x, y) {
+        ('S', _) => ('a', y),
+        ('E', _) => ('z', y),
+        (_, 'S') => (x, 'a'),
+        (_, 'E') => (x, 'z'),
+        _ => (x, y),
+    };
+
+    let (x, y) = (x as i8, y as i8);
+    i8::abs(x - y) <= 1 || x > y
+}
+
+fn main() {
+    let args = Cli::parse();
+
+    let file = File::open(&args.file).unwrap();
+    let reader = BufReader::new(file);
+
+    let mut arena = Arena(Vec::new());
+    let _ = reader
+        .lines()
+        .enumerate()
+        .map(|(idx, l)| {
+            l.unwrap()
+                .chars()
+                .enumerate()
+                .map(|(idy, c)| Node::new(Pos(idx, idy), c))
+                .collect_vec()
+        })
+        .scan(&mut arena, |arena, row| {
+            arena.0.push(row);
+            Some(())
+        })
+        .last();
+
+    let xdim = arena.0.len();
+    let ydim = arena.0[0].len();
+
+    let mut lowest_pos = Vec::new();
+    let mut end_pos = None;
+
+    for idx in 0..xdim {
+        for idy in 0..ydim {
+            let node_val = arena.get(Pos(idx, idy)).value;
+
+            match node_val {
+                'a' | 'S' => lowest_pos.push(Pos(idx, idy)),
+                'E' => end_pos = Some(Pos(idx, idy)),
+                _ => (),
+            }
+
+            if idx != 0 {
+                let up_idx = Pos(idx - 1, idy);
+                if is_connected(node_val, arena.get(up_idx).value) {
+                    arena.get_mut(Pos(idx, idy)).connected.push(up_idx);
+                }
+            }
+
+            if idx != xdim - 1 {
+                let down_idx = Pos(idx + 1, idy);
+                if is_connected(node_val, arena.get(down_idx).value) {
+                    arena.get_mut(Pos(idx, idy)).connected.push(down_idx);
+                }
+            }
+
+            if idy != 0 {
+                let left_idx = Pos(idx, idy - 1);
+                if is_connected(node_val, arena.get(left_idx).value) {
+                    arena.get_mut(Pos(idx, idy)).connected.push(left_idx);
+                }
+            }
+
+            if idy != ydim - 1 {
+                let right_idx = Pos(idx, idy + 1);
+                if is_connected(node_val, arena.get(right_idx).value) {
+                    arena.get_mut(Pos(idx, idy)).connected.push(right_idx);
+                }
+            }
+        }
+    }
+
+    let end = arena.get(end_pos.unwrap());
+
+    let res = lowest_pos
+        .into_iter()
+        .filter_map(|s| {
+            let steps = bfs(
+                &arena.get(s),
+                |n| n.connected.iter().map(|&p| arena.get(p)),
+                |&n| n == end,
+            )?
+            .len()
+                - 1;
+            Some(steps)
+        })
+        .min()
+        .unwrap();
+    println!("{res}");
+}