From 229f1057468e6f7508ef36e804bc55af224b9fab Mon Sep 17 00:00:00 2001
From: Jesse Luehrs <doy@tozt.net>
Date: Mon, 12 Dec 2022 01:31:23 -0500
Subject: optimize day 12

---
 src/bin/2021/day15.rs | 14 ++++++--------
 src/bin/2021/day23.rs |  5 +++--
 src/bin/2022/day12.rs | 21 ++++++---------------
 src/graph.rs          |  8 ++++++--
 4 files changed, 21 insertions(+), 27 deletions(-)

diff --git a/src/bin/2021/day15.rs b/src/bin/2021/day15.rs
index ca7a72f..259780e 100644
--- a/src/bin/2021/day15.rs
+++ b/src/bin/2021/day15.rs
@@ -24,10 +24,9 @@ pub fn parse(fh: File) -> Result<Map> {
 
 pub fn part1(map: Map) -> Result<u64> {
     Ok(map
-        .dijkstra(
-            (Row(0), Col(0)),
-            (map.grid.rows() - 1, map.grid.cols() - 1),
-        )
+        .dijkstra((Row(0), Col(0)), |v| {
+            v == (map.grid.rows() - 1, map.grid.cols() - 1)
+        })
         .0)
 }
 
@@ -48,10 +47,9 @@ pub fn part2(map: Map) -> Result<u64> {
     }
     let large_map = Map { grid: large_grid };
     Ok(large_map
-        .dijkstra(
-            (Row(0), Col(0)),
-            (large_map.grid.rows() - 1, large_map.grid.cols() - 1),
-        )
+        .dijkstra((Row(0), Col(0)), |v| {
+            v == (large_map.grid.rows() - 1, large_map.grid.cols() - 1)
+        })
         .0)
 }
 
diff --git a/src/bin/2021/day23.rs b/src/bin/2021/day23.rs
index c86f7c0..7923361 100644
--- a/src/bin/2021/day23.rs
+++ b/src/bin/2021/day23.rs
@@ -1707,7 +1707,8 @@ pub fn parse(fh: File) -> Result<Burrow> {
 }
 
 pub fn part1(burrow: Burrow) -> Result<u64> {
-    let (cost, _path) = Pathfinder.dijkstra(burrow, Burrow::done(false));
+    let (cost, _path) =
+        Pathfinder.dijkstra(burrow, |v| v == Burrow::done(false));
     // for burrow in path {
     //     eprintln!("{}", burrow);
     // }
@@ -1716,7 +1717,7 @@ pub fn part1(burrow: Burrow) -> Result<u64> {
 
 pub fn part2(burrow: Burrow) -> Result<u64> {
     let (cost, _path) =
-        Pathfinder.dijkstra(burrow.to_big(), Burrow::done(true));
+        Pathfinder.dijkstra(burrow.to_big(), |v| v == Burrow::done(true));
     // for burrow in path {
     //     eprintln!("{}", burrow);
     // }
diff --git a/src/bin/2022/day12.rs b/src/bin/2022/day12.rs
index d2d0acf..f722f09 100644
--- a/src/bin/2022/day12.rs
+++ b/src/bin/2022/day12.rs
@@ -19,10 +19,12 @@ impl advent_of_code::graph::Graph<(Row, Col), (Row, Col)> for Map {
     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 {
+            if self.grid[e.0][e.1] >= self.grid[v.0][v.1].saturating_sub(1) {
                 1
             } else {
-                999_999_999
+                (self.grid.rows().0 * self.grid.cols().0)
+                    .try_into()
+                    .unwrap()
             },
         )
     }
@@ -51,22 +53,11 @@ pub fn parse(fh: File) -> Result<Map> {
 }
 
 pub fn part1(map: Map) -> Result<u64> {
-    Ok(map.dijkstra(map.start, map.end).0)
+    Ok(map.dijkstra(map.end, |v| v == map.start).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())
+    Ok(map.dijkstra(map.end, |v| map.grid[v.0][v.1] == 0).0)
 }
 
 #[test]
diff --git a/src/graph.rs b/src/graph.rs
index 74c2910..9312e7c 100644
--- a/src/graph.rs
+++ b/src/graph.rs
@@ -9,13 +9,17 @@ where
     fn edges(&self, v: Vertex) -> Self::Edges;
     fn edge(&self, v: Vertex, e: Edge) -> (Vertex, u64);
 
-    fn dijkstra(&self, start: Vertex, end: Vertex) -> (u64, Vec<Vertex>) {
+    fn dijkstra<F: Fn(Vertex) -> bool>(
+        &self,
+        start: Vertex,
+        end: F,
+    ) -> (u64, Vec<Vertex>) {
         let mut to_visit = priority_queue::PriorityQueue::new();
         let mut prev = HashMap::new();
         prev.insert(start, start);
         to_visit.push(start, std::cmp::Reverse(0));
         while let Some((v, std::cmp::Reverse(distance))) = to_visit.pop() {
-            if v == end {
+            if end(v) {
                 let mut path = vec![v];
                 let mut cur = v;
                 while let Some(next) = prev.get(&cur) {
-- 
cgit v1.2.3-54-g00ecf