complete day 12

4 files changed, 259 insertions, 0 deletions

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}");
+}