complete day 12

1 files changed, 212 insertions, 0 deletions

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