1 files changed, 141 insertions, 0 deletions
diff --git a/2022/src/day12.rs b/2022/src/day12.rs
new file mode 100644
index 0000000..c446c74
--- /dev/null
+++ b/2022/src/day12.rs
@@ -0,0 +1,141 @@
+mod utils;
+use std::collections::BinaryHeap;
+
+use utils::read_input;
+
+fn main() {
+    let input = read_input();
+
+    let width = input.lines().next().unwrap().len();
+    let height = input.lines().count();
+    let mut heights = vec![0; width * height];
+
+    let mut start = (0, 0);
+    let mut end = (0, 0);
+
+    for (y, line) in input.lines().enumerate() {
+        for (x, c) in line.chars().enumerate() {
+            let val = if c == 'S' {
+                start = (x as isize, y as isize);
+                0
+            } else if c == 'E' {
+                end = (x as isize, y as isize);
+                25
+            } else {
+                c.to_ascii_lowercase() as isize - 97
+            };
+            heights[(y * width) + x] = val;
+        }
+    }
+
+    let cost = pathfind(&heights, width, end);
+
+    println!("Part 1: {:?}", cost[pos_to_index(&start, width)]);
+    println!(
+        "Part 2: {:?}",
+        (0..height as isize)
+            .map(|y| (0..width as isize)
+                .map(|x| pos_to_index(&(x, y), width))
+                .filter(|idx| heights[*idx] == 0)
+                .map(|idx| cost[idx])
+                .min()
+                .unwrap())
+            .min()
+            .unwrap()
+    )
+}
+
+type HeightMap = Vec<isize>;
+type Pos = (isize, isize);
+
+fn pathfind(heights: &HeightMap, width: usize, end: Pos) -> Vec<usize> {
+    let mut min_cost = vec![usize::MAX; heights.len()];
+    let mut frontier: BinaryHeap<GraphPos> = BinaryHeap::new();
+    frontier.push(GraphPos { pos: end, moves: 0 });
+    while let Some(curr) = frontier.pop() {
+        let idx = pos_to_index(&curr.pos, width);
+        if curr.moves >= min_cost[idx] {
+            continue;
+        } else {
+            min_cost[idx] = curr.moves;
+        }
+
+        for neighbour in CanReach::new(heights, width, curr.pos) {
+            frontier.push(GraphPos {
+                pos: neighbour,
+                moves: curr.moves + 1,
+            })
+        }
+    }
+
+    min_cost
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+struct GraphPos {
+    pos: Pos,
+    moves: usize,
+}
+
+impl PartialOrd for GraphPos {
+    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
+        self.moves.partial_cmp(&other.moves).map(|x| x.reverse())
+    }
+}
+
+impl Ord for GraphPos {
+    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
+        self.moves.cmp(&other.moves).reverse()
+    }
+}
+
+struct CanReach<'a> {
+    heights: &'a HeightMap,
+    curr: Pos,
+    step: usize,
+    width: usize,
+}
+
+impl<'a> CanReach<'a> {
+    fn new(heights: &'a HeightMap, width: usize, pos: Pos) -> Self {
+        CanReach {
+            heights,
+            curr: pos,
+            step: 0,
+            width,
+        }
+    }
+}
+impl Iterator for CanReach<'_> {
+    type Item = Pos;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let (curr_x, curr_y) = self.curr;
+        loop {
+            let (x, y) = match self.step {
+                0 => (curr_x + 1, curr_y),
+                1 => (curr_x - 1, curr_y),
+                2 => (curr_x, curr_y + 1),
+                3 => (curr_x, curr_y - 1),
+                _ => break,
+            };
+            self.step += 1;
+
+            if (x >= 0
+                && x < self.width as isize
+                && y >= 0
+                && y < (self.heights.len() / self.width) as isize)
+                && self.heights[pos_to_index(&(x, y), self.width)]
+                    >= self.heights[pos_to_index(&(curr_x, curr_y), self.width)] - 1
+            {
+                return Some((x, y));
+            }
+        }
+        None
+    }
+}
+
+#[inline(always)]
+fn pos_to_index(pos: &Pos, width: usize) -> usize {
+    ((pos.1 * width as isize) + pos.0) as usize
+}