day 12

5 files changed, 132 insertions, 5 deletions

diff --git a/data/2022/12.txt b/data/2022/12.txt
new file mode 100644
index 0000000..af66594
--- /dev/null
+++ b/data/2022/12.txt
@@ -0,0 +1,41 @@
+abaaaaaaaaccccccccccccccccccaaaaaccccaaaaaaccccccccccccccccccccccaaaaaaaaaacccccccccccccccccccccccccccccccaaaaaccccccccccccccccccccccccccccccccccccccccccaaaaaa
+abaaaaaaaacccccccccccccccccccaaaaaccccaaaacccccaaaacccccccccccccccaaaaaaaaaacccccccccccccccccccccccccccccaaaaaaccccccccccccccccccccccccccccccccccccccccccccaaaa
+abccaaaaaaccccccccccccccccccaaaaaaccccaaaaccccaaaaaccccccccccaaaaaaaaaaaaaaacccccccccccccccccccccccccccccaaaacccccccccccccccccccccccccccccaaaccccccccccccccaaaa
+abcaaaaaaaccccccccccccccccccaaaaccccccaccaccccaaaaaacccccccccaaaaaaaaaaaaaaacccccccccccccccccccccacccccccccaacccccccccccccccccccccccccccccaaaccccccccccccccaaaa
+abccaacccaccccccccccccccccccccaaacccccccccccccaaaaaaccccccccccaaaaaaaaacaaacccccccccccccccccccaaaacccccccccccccccccccccccccaacccccccaaccccaaacccccccccccccaaaaa
+abcaaaaaacccccccccccccccccccccccccccccccccccccaaaaaccccccccccaaaaaaaaaaccccaacaaccccccccccccccaaaaaacccccccccccccccccccccccaacccccccaaaacaaaaccccccccccccccaccc
+abccaaaaacccccccccccccccccccccccccccccccccccaaccaaacccccccccaaaaaaaaaaaacccaaaaccccccccccccccccaaaaacccccccccccccccaacaaaaaaacccccccaaaaaaaaacccccccccccccccccc
+abccaaaaaacccccccccccccccccccccccccccccaaacaaaccccccccccccccaaaaaaaaaaacccaaaaacccccccccccccccaaaaacccccccccccccaaaaaccaaaaaaaaccccccaaaaaalllllllcccaacccccccc
+abccaaaaaaccccccaaaaacccccccccaaaccccccaaaaaaaccccccccccccccaaacaaacaaacccaaaaaaccccccccccccccaccaaccccccccccccccaaaaacaaaaaaaaajkkkkkkkkkklllllllccccaaaaacccc
+abccaaaaacccccccaaaaacccccccccaaaaccccccaaaaaaccccccccaacaacccccaaacccccccacaaaaccccccccaaaccccccccccccccccccccccaaaaaccaaaaaaajjkkkkkkkkkkllssllllcccaaaaacccc
+abcccaaaaccccccaaaaaacccccccccaaaaccccccaaaaaaaaccccccaaaaacccccaaccccccccccaacccccccccaaaacccccccccccccccaaccccaaaaaccaaaaaacjjjjkkkkkkkkssssssslllccaaaaccccc
+abcccccccccccccaaaaaacccccccccaaaccccccaaaaaaaaacaaccccaaaaacccccccccccccccaaccccccccccaaaaccccccccccccccaaacccccccaaccaaaaaajjjjrrrrrrsssssssssslllcccaaaccccc
+abcccccccccccccaaaaaacccccccccccccccccaaaaaaaaaaaaaaacaaaaaacccccccccccaaacaacccccccccccaaaccccaaacccccaaaaaaaaccccccccaacaaajjjrrrrrrrsssssuusssslmcccaaaacccc
+abcccccccccccccccaacccccccccccccccaacaaaacaaaccaaaaaacaaaaccccccccccccccaaaaaccccccccccccccccccaaaaacccaaaaaaaaccccccccccccaajjjrrrruuurssuuuuvsqqmmcddaaaacccc
+abccccccccccccccccccccccccccccccccaaaaacccaaacccaaaaccccaaccccccccccccccaaaaaaacccccccccccccccaaaaaaccccaaaaaacccccccccccccccjjrrruuuuuuuuuuuuvvqqmmmdddccccccc
+abcccccccccccccccccccccccacccccccccaaaaaccaaacccaaaaccccccccccccccccccccaaaaaaacccccccccccccccaaaaaaccccaaaaaacccccccccaaccccjjjrrtuuuuuuuuyyvvvqqmmmddddcccccc
+abccccccccccccccccccccaaaaccccccccaaaaaacccccaacaccacccccccccccccccccccaaaaaaccccccccccccccccccaaaaaccccaaaaaaccccccccaaaccccjjjrrttuxxxuuxyyyvvqqmmmmdddcccccc
+abcccccccccaacccccccccaaaaaaccccccaaaaccccccaaaccccccccccccccccccccccccaacaaaccccccccccccccccccaacaaccccaaccaaccccaaaaaaaccccjjjrrtttxxxxxyyyyvvqqqmmmddddccccc
+abccccccccaaaacccccccccaaaacccccccccaaccccccaaacaaaccccccccccccccccccaaccccaacccccccccccccccccccccccccccccccccccccaaaaaaaaaacijjqrtttxxxxxyyyvvvqqqqmmmdddccccc
+abcccccacaaaaaccccccccaaaaaccccccccccccccaaaaaaaaaacccccccccccccccccaaaccccccccccccccccccccccccccccccccccccccccccccaaaaaaaaaciiiqqqttxxxxxyyyvvvvqqqqmmmdddcccc
+SbcccccaaaaaaaaaacccccaacaaccccccccccccccaaaaaaaaaccccccccccccccaaacaaacccccccccccccccccccccccccccccccccccccccccccccaaaaaaaciiiqqqtttxxxEzzyyyyvvvqqqmmmdddcccc
+abcccccaaaaaaaaaaccccccccccccaaccccccccccccaaaaaccccccccccccccccaaaaaaaaaacccccccaacccccccccccccaacccccccccccccccccaaaaaaccciiiqqqttxxxxyyyyyyyyvvvqqqmmmeddccc
+abcccccccaaaaaacccccccccccaaaaccccccccccaaaaaaaaacccccccaaaacccccaaaaaaaaacccccaaaaccccccccccaacaaaccccccccccccccccaaaaaaaciiiqqqtttxxyyyyyyyyyvvvvqqqnnneeeccc
+abcccccccaaaaaacccccccccccaaaaaaccccccccaaaaaaaaaaccccccaaaaccccccaaaaaaaccccccaaaaaaccccccccaaaaacccccccccccccccccaaccaaaciiiqqtttxxxxwwyyywwvvvvrrrnnnneeeccc
+abcccccccaaaaaaccccccccccccaaaaacccccccaaaaaaacaaaccccccaaaacccccaaaaaacccccccccaaaaccccccccccaaaaaaccccaaccccccccccccccaaciiqqqtttxxxwwwyywwwwvvrrrrnnneeecccc
+abccccccaaaaaaaaccccccccccaaaaaccccccccaaaaaaccccccccccccaaacccccaaaaaaacccccccaaaaaccccccccaaaaaaaaacccaaccccccccccccccccciiqqqtttttwwswwyywwrrrrrrnnnneeecccc
+abccccccccccccacccccccccccaccaaccccaaccaaaaaacccccccccccaccccccccaaacaaacccccccaacaaccccccccaaaaacaaaaaaaacccccccccaacccccciiqqqqttssssswwwwwrrrrnnnnnneeeecccc
+abcccccccccccccccccccccccccccccaaaaaaccccaacccccccaaacaaacccccccccccccaacaaacccccccccccccccccccaaaccaaaaaaaaccccaacaacccccciiiqqpppsssssswwwwrrrnnnnneeeeeccccc
+abcccccccccccccccccccccccccccccaaaaaaaccccccccccccaaaaaaaccccccccccccccccaaacccccccccccccccccccaaaccaaaaaaaaacccaaaaacccccchhhhppppppppssswwwrroonnfeeeeacccccc
+abccccccccccccccccccccaaaaaccccaaaaaaaaccccccccccccaaaaaaccccccccccccccaaaaaaaacccccccccccccccccccccaaaaaaaaaccccaaaaaaccccchhhhhpppppppsssssrroonfffeeaaaacccc
+abccccccccccccccccccccaaaaacccccaaaaaaaccccccccccccaaaaaaaaccccccccccccaaaaaaaacccccccccccccccccccccaaaaaacccccaaaaaaaacccccchhhhhhhppppsssssrooofffffaaaaacccc
+abcccccaacaaacccccccccaaaaaacccaaaaaacccccccccccccaaaaaaaaacccccccccccccaaaaacccccccccccccccccccccccaaaaaaaccccaaaaaccaccccccchhhhhhhhpppssssrooofffcaaaaaccccc
+abcccccaaaaaacccccccccaaaaaacccaaaaaaccccccccccccaaaaaaaaaacccccccccccccaaaaaaccccccccccccccccccccccaccaaaccccccacaaaccaacccccccchhhhhgppooooooofffcaaaaacccccc
+abcccccaaaaaacccccccccaaaaaaccccccaaacaacccccccccaaacaaaccccccccccaaacccaaaaaaccccccccccccccccccccccccccaaacccccccaaacaaaccccccccccchgggoooooooffffcaaaaaaccccc
+abaccccaaaaaaaccccccccccaaccccccccaaaaaacccccccccccccaaaccccccccccaaaaccaaaccacaacaacccccccccccccccccccccccccccccccaaaaaaaaccccccccccggggoooooffffccaccaaaccccc
+abacccaaaaaaaaccccccccccccccccccccaaaaaccccccccccccccaacccccccaaacaaaacccaaccccaaaaacccccccccccccccccccaacaacccccccaaaaaaaacccccccccccggggggggfffcccccccccccccc
+abacccaaaaaaaaccccccccaaacccccccccaaaaaaccccccccccccccccccccccaaacaaaacaaaaccccaaaaaaccccccccaaccccccccaaaaaccccccccaaaaaaacccccccccccaaggggggffcccccccccccccca
+abcccccccaaacccccccccaaaaaaccccccaaaaaaaacccccccccccccccccccaaaaaaaaaaaaaaaccccaaaaaaccccccacaaaacccccccaaaaacccccccaaaaaccccccccccccaaacgggggaccccccccccccccaa
+abcccccccaaccccccccccaaaaaaccccccaaaaaaaacccccccaaacccccccccaaaaaaaaaaaaaaaacccaaaaaaccccccaaaaaaccccccaaaaaaccccccaaaaaaacccccccccccaaaccccaaaccccccccccaaacaa
+abcccccccccccccccccccaaaaaccccccccccaaccccccccaaaaaccccccccccaaaaaaaaaaaaaaaaccccaaaccccccccaaaacccccccaaaaccccccccccccaaccccccccccccccccccccccccccccccccaaaaaa
+abccccccccccccccccccccaaaaacccccccccaaccccccccaaaaaacccccccccaaaaaaaaaaaaaaaacccccccccccccccaaaacccccccccaacccccccccccccccccccccccccccccccccccccccccccccccaaaaa
diff --git a/src/bin/2021/day25.rs b/src/bin/2021/day25.rs
index ed396c6..68d866e 100644
--- a/src/bin/2021/day25.rs
+++ b/src/bin/2021/day25.rs
@@ -60,7 +60,7 @@ impl Map {
 
 pub fn parse(fh: File) -> Result<Map> {
     Ok(Map {
-        grid: parse::grid(parse::raw_lines(fh), |b| match b {
+        grid: parse::grid(parse::raw_lines(fh), |b, _, _| match b {
             b'v' => Cell::Down,
             b'>' => Cell::Right,
             b'.' => Cell::None,
diff --git a/src/bin/2022/day12.rs b/src/bin/2022/day12.rs
new file mode 100644
index 0000000..d2d0acf
--- /dev/null
+++ b/src/bin/2022/day12.rs
@@ -0,0 +1,82 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use advent_of_code::prelude::*;
+
+pub struct Map {
+    grid: Grid<u8>,
+    start: (Row, Col),
+    end: (Row, Col),
+}
+
+impl advent_of_code::graph::Graph<(Row, Col), (Row, Col)> for Map {
+    type Edges = advent_of_code::grid::Adjacent;
+
+    fn edges(&self, v: (Row, Col)) -> Self::Edges {
+        self.grid.adjacent(v.0, v.1, false)
+    }
+
+    fn edge(&self, v: (Row, Col), e: (Row, Col)) -> ((Row, Col), u64) {
+        (
+            e,
+            if self.grid[e.0][e.1] <= self.grid[v.0][v.1] + 1 {
+                1
+            } else {
+                999_999_999
+            },
+        )
+    }
+}
+
+pub fn parse(fh: File) -> Result<Map> {
+    let mut start = None;
+    let mut end = None;
+    let grid = parse::grid(parse::raw_lines(fh), |c, row, col| match c {
+        b'a'..=b'z' => c - b'a',
+        b'S' => {
+            start = Some((row, col));
+            0
+        }
+        b'E' => {
+            end = Some((row, col));
+            b'z' - b'a'
+        }
+        _ => panic!("unknown map char '{c}'"),
+    });
+    Ok(Map {
+        grid,
+        start: start.expect("start not found"),
+        end: end.expect("end not found"),
+    })
+}
+
+pub fn part1(map: Map) -> Result<u64> {
+    Ok(map.dijkstra(map.start, map.end).0)
+}
+
+pub fn part2(map: Map) -> Result<u64> {
+    Ok(map
+        .grid
+        .indexed_cells()
+        .filter_map(|(pos, height)| {
+            if *height == 0 {
+                Some(map.dijkstra(pos, map.end).0)
+            } else {
+                None
+            }
+        })
+        .min()
+        .unwrap())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2022, 12).unwrap()).unwrap()).unwrap(),
+        504
+    );
+    assert_eq!(
+        part2(parse(parse::data(2022, 12).unwrap()).unwrap()).unwrap(),
+        500
+    );
+}
diff --git a/src/bin/2022/main.rs b/src/bin/2022/main.rs
index 09a9248..c694d56 100644
--- a/src/bin/2022/main.rs
+++ b/src/bin/2022/main.rs
@@ -22,6 +22,7 @@ mod day6;
 mod day7;
 mod day8;
 mod day9;
+mod day12;
 // NEXT MOD
 
 #[paw::main]
@@ -39,6 +40,7 @@ fn main(opt: Opt) -> Result<()> {
         9 => advent_of_code::day!(2022, opt.day, opt.puzzle, day9),
         10 => advent_of_code::day!(2022, opt.day, opt.puzzle, day10),
         11 => advent_of_code::day!(2022, opt.day, opt.puzzle, day11),
+        12 => advent_of_code::day!(2022, opt.day, opt.puzzle, day12),
         // NEXT PART
         _ => panic!("unknown day {}", opt.day),
     }
diff --git a/src/parse.rs b/src/parse.rs
index 7e6cab7..1219484 100644
--- a/src/parse.rs
+++ b/src/parse.rs
@@ -106,17 +106,19 @@ pub fn digit_grid(lines: impl Iterator<Item = String>) -> Grid<u8> {
 
 // false positive, doing its suggestion gives borrow checker errors
 #[allow(clippy::redundant_closure)]
-pub fn grid<F, T>(lines: impl Iterator<Item = String>, f: F) -> Grid<T>
+pub fn grid<F, T>(lines: impl Iterator<Item = String>, mut f: F) -> Grid<T>
 where
-    F: Fn(u8) -> T,
+    F: FnMut(u8, Row, Col) -> T,
     T: Clone + Default + Eq + PartialEq,
 {
     lines
-        .map(|s| {
+        .enumerate()
+        .map(|(row, s)| {
             s.as_bytes()
                 .iter()
                 .copied()
-                .map(|b| f(b))
+                .enumerate()
+                .map(|(col, b)| f(b, Row(row), Col(col)))
                 .collect::<Vec<_>>()
         })
         .collect()