factor out pathfinding

6 files changed, 160 insertions, 113 deletions

diff --git a/src/2021/15/mod.rs b/src/2021/15/mod.rs
index efb2716..15b05fb 100644
--- a/src/2021/15/mod.rs
+++ b/src/2021/15/mod.rs
@@ -1,69 +1,58 @@
 use crate::prelude::*;
 
-fn dijkstra(map: &Grid<u8>) -> i64 {
-    let mut to_visit: priority_queue::PriorityQueue<_, _> = (0..map.rows().0)
-        .flat_map(|row| {
-            (0..map.cols().0).map(move |col| (Row(row), Col(col)))
-        })
-        .map(|pos| {
-            (
-                pos,
-                std::cmp::Reverse(if pos == (Row(0), Col(0)) {
-                    0
-                } else {
-                    i64::max_value()
-                }),
-            )
-        })
-        .collect();
+pub struct Map {
+    grid: Grid<u8>,
+}
 
-    while let Some(((row, col), std::cmp::Reverse(distance))) = to_visit.pop()
-    {
-        if row == Row(map.rows().0 - 1) && col == Col(map.cols().0 - 1) {
-            return distance;
-        }
+impl crate::graph::Graph<(Row, Col), (Row, Col)> for Map {
+    type Edges = crate::grid::Adjacent;
 
-        for neighbor in map.adjacent(row, col, false) {
-            if to_visit.get(&neighbor).is_some() {
-                let new_distance =
-                    distance + i64::from(map[neighbor.0][neighbor.1]);
-                if new_distance < to_visit.get_priority(&neighbor).unwrap().0
-                {
-                    to_visit.change_priority(
-                        &neighbor,
-                        std::cmp::Reverse(new_distance),
-                    );
-                }
-            }
-        }
+    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), i64) {
+        (e, i64::from(self.grid[e.0][e.1]))
     }
-    unreachable!()
 }
 
-pub fn parse(fh: File) -> Result<Grid<u8>> {
-    Ok(parse::digit_grid(parse::lines(fh)))
+pub fn parse(fh: File) -> Result<Map> {
+    Ok(Map {
+        grid: parse::digit_grid(parse::lines(fh)),
+    })
 }
 
-pub fn part1(grid: Grid<u8>) -> Result<i64> {
-    Ok(dijkstra(&grid))
+pub fn part1(map: Map) -> Result<i64> {
+    Ok(map
+        .dijkstra(
+            (Row(0), Col(0)),
+            (map.grid.rows() - 1, map.grid.cols() - 1),
+        )
+        .0)
 }
 
-pub fn part2(grid: Grid<u8>) -> Result<i64> {
+pub fn part2(map: Map) -> Result<i64> {
     let mut large_grid = Grid::default();
-    large_grid.grow(Row(grid.rows().0 * 5), Col(grid.cols().0 * 5));
+    large_grid.grow(Row(map.grid.rows().0 * 5), Col(map.grid.cols().0 * 5));
     for lrow in 0..5 {
         for lcol in 0..5 {
-            for ((Row(row), Col(col)), val) in grid.indexed_cells() {
+            for ((Row(row), Col(col)), val) in map.grid.indexed_cells() {
                 let mut val = val + lrow + lcol;
                 while val > 9 {
                     val -= 9;
                 }
-                large_grid[Row(usize::from(lrow) * grid.rows().0 + row)]
-                    [Col(usize::from(lcol) * grid.cols().0 + col)] = val;
+                large_grid[Row(usize::from(lrow) * map.grid.rows().0 + row)]
+                    [Col(usize::from(lcol) * map.grid.cols().0 + col)] = val;
             }
         }
     }
-    Ok(dijkstra(&large_grid))
+    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),
+        )
+        .0)
 }
 
 #[test]
diff --git a/src/2021/23/mod.rs b/src/2021/23/mod.rs
index 3abb878..632dbaf 100644
--- a/src/2021/23/mod.rs
+++ b/src/2021/23/mod.rs
@@ -1277,24 +1277,31 @@ impl Burrow {
         }
     }
 
-    fn done(&self) -> bool {
-        self.spaces[11] == Some(A)
-            && self.spaces[15] == Some(A)
-            && self.spaces[12] == Some(B)
-            && self.spaces[16] == Some(B)
-            && self.spaces[13] == Some(C)
-            && self.spaces[17] == Some(C)
-            && self.spaces[14] == Some(D)
-            && self.spaces[18] == Some(D)
-            && (!self.big
-                || (self.spaces[19] == Some(A)
-                    && self.spaces[23] == Some(A)
-                    && self.spaces[20] == Some(B)
-                    && self.spaces[24] == Some(B)
-                    && self.spaces[21] == Some(C)
-                    && self.spaces[25] == Some(C)
-                    && self.spaces[22] == Some(D)
-                    && self.spaces[26] == Some(D)))
+    fn done(big: bool) -> Self {
+        let mut done = Self::default();
+
+        done.spaces[11] = Some(A);
+        done.spaces[15] = Some(A);
+        done.spaces[12] = Some(B);
+        done.spaces[16] = Some(B);
+        done.spaces[13] = Some(C);
+        done.spaces[17] = Some(C);
+        done.spaces[14] = Some(D);
+        done.spaces[18] = Some(D);
+
+        if big {
+            done.spaces[19] = Some(A);
+            done.spaces[23] = Some(A);
+            done.spaces[20] = Some(B);
+            done.spaces[24] = Some(B);
+            done.spaces[21] = Some(C);
+            done.spaces[25] = Some(C);
+            done.spaces[22] = Some(D);
+            done.spaces[26] = Some(D);
+            done.big = true;
+        }
+
+        done
     }
 
     fn move_cost(&self, mv: Move) -> i64 {
@@ -1664,6 +1671,20 @@ impl Move {
     }
 }
 
+struct Pathfinder;
+
+impl crate::graph::Graph<Burrow, Move> for Pathfinder {
+    type Edges = Vec<Move>;
+
+    fn edges(&self, v: Burrow) -> Self::Edges {
+        v.legal_moves()
+    }
+
+    fn edge(&self, v: Burrow, e: Move) -> (Burrow, i64) {
+        (v.make_move(e), v.move_cost(e))
+    }
+}
+
 pub fn parse(fh: File) -> Result<Burrow> {
     let mut burrow = Burrow::default();
     let lines: Vec<_> = parse::lines(fh).collect();
@@ -1685,56 +1706,8 @@ pub fn parse(fh: File) -> Result<Burrow> {
     Ok(burrow)
 }
 
-#[allow(dead_code)]
-fn organize_recursive(burrow: Burrow, so_far: &mut Vec<Move>) -> bool {
-    if burrow.done() {
-        return true;
-    }
-    for mv in burrow.legal_moves() {
-        so_far.push(mv);
-        if organize_recursive(burrow.make_move(mv), so_far) {
-            return true;
-        }
-        so_far.pop();
-    }
-    false
-}
-
-fn organize_dijkstra(burrow: Burrow) -> (i64, Vec<Burrow>) {
-    let mut to_visit = priority_queue::PriorityQueue::new();
-    let mut prev = HashMap::new();
-    to_visit.push(burrow, std::cmp::Reverse(0));
-    while let Some((burrow, std::cmp::Reverse(distance))) = to_visit.pop() {
-        if burrow.done() {
-            let mut path = vec![burrow];
-            let mut cur = burrow;
-            while let Some(next) = prev.get(&cur) {
-                path.insert(0, *next);
-                cur = *next;
-            }
-            return (distance, path);
-        }
-        for mv in burrow.legal_moves() {
-            let next = burrow.make_move(mv);
-            prev.insert(next, burrow);
-            let new_distance = distance + burrow.move_cost(mv);
-            if to_visit.get(&next).is_some() {
-                if new_distance < to_visit.get_priority(&next).unwrap().0 {
-                    to_visit.change_priority(
-                        &next,
-                        std::cmp::Reverse(new_distance),
-                    );
-                }
-            } else {
-                to_visit.push(next, std::cmp::Reverse(new_distance));
-            }
-        }
-    }
-    unreachable!()
-}
-
 pub fn part1(burrow: Burrow) -> Result<i64> {
-    let (cost, _path) = organize_dijkstra(burrow);
+    let (cost, _path) = Pathfinder.dijkstra(burrow, Burrow::done(false));
     // for burrow in path {
     //     eprintln!("{}", burrow);
     // }
@@ -1742,7 +1715,8 @@ pub fn part1(burrow: Burrow) -> Result<i64> {
 }
 
 pub fn part2(burrow: Burrow) -> Result<i64> {
-    let (cost, _path) = organize_dijkstra(burrow.to_big());
+    let (cost, _path) =
+        Pathfinder.dijkstra(burrow.to_big(), Burrow::done(true));
     // for burrow in path {
     //     eprintln!("{}", burrow);
     // }
diff --git a/src/graph.rs b/src/graph.rs
new file mode 100644
index 0000000..831cc17
--- /dev/null
+++ b/src/graph.rs
@@ -0,0 +1,54 @@
+use crate::prelude::*;
+
+pub trait Graph<Vertex, Edge>
+where
+    Vertex: std::hash::Hash + Clone + Copy + PartialEq + Eq + std::fmt::Debug,
+{
+    type Edges: IntoIterator<Item = Edge>;
+
+    fn edges(&self, v: Vertex) -> Self::Edges;
+    fn edge(&self, v: Vertex, e: Edge) -> (Vertex, i64);
+
+    fn dijkstra(&self, start: Vertex, end: Vertex) -> (i64, 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 {
+                let mut path = vec![v];
+                let mut cur = v;
+                while let Some(next) = prev.get(&cur) {
+                    if *next == cur {
+                        break;
+                    }
+                    path.insert(0, *next);
+                    cur = *next;
+                }
+                return (distance, path);
+            }
+
+            for e in self.edges(v) {
+                let (next, weight) = self.edge(v, e);
+                let visited = prev.contains_key(&next);
+                let new_distance = distance + weight;
+                if to_visit.get(&next).is_some() {
+                    prev.insert(next, v);
+                    if new_distance < to_visit.get_priority(&next).unwrap().0
+                    {
+                        to_visit.change_priority(
+                            &next,
+                            std::cmp::Reverse(new_distance),
+                        );
+                    }
+                } else {
+                    if !visited {
+                        prev.insert(next, v);
+                        to_visit.push(next, std::cmp::Reverse(new_distance));
+                    }
+                }
+            }
+        }
+        unreachable!()
+    }
+}
diff --git a/src/grid.rs b/src/grid.rs
index c0607c0..46f6263 100644
--- a/src/grid.rs
+++ b/src/grid.rs
@@ -31,6 +31,34 @@ impl std::ops::Add<Col> for usize {
     }
 }
 
+impl std::ops::Sub<usize> for Row {
+    type Output = Self;
+    fn sub(self, other: usize) -> Self::Output {
+        Self(self.0 - other)
+    }
+}
+
+impl std::ops::Sub<Row> for usize {
+    type Output = Row;
+    fn sub(self, other: Row) -> Self::Output {
+        Row(self - other.0)
+    }
+}
+
+impl std::ops::Sub<usize> for Col {
+    type Output = Self;
+    fn sub(self, other: usize) -> Self::Output {
+        Self(self.0 - other)
+    }
+}
+
+impl std::ops::Sub<Col> for usize {
+    type Output = Col;
+    fn sub(self, other: Col) -> Self::Output {
+        Col(self - other.0)
+    }
+}
+
 #[derive(Default, Clone, Debug)]
 pub struct GridRow<T: Default + Clone> {
     cells: Vec<T>,
diff --git a/src/main.rs b/src/main.rs
index d5b4516..6a1de63 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -12,6 +12,7 @@
 #[macro_use]
 pub mod regex;
 
+pub mod graph;
 pub mod grid;
 pub mod parse;
 pub mod prelude;
diff --git a/src/prelude.rs b/src/prelude.rs
index 19382dc..6c53874 100644
--- a/src/prelude.rs
+++ b/src/prelude.rs
@@ -1,3 +1,4 @@
+pub use crate::graph::Graph as _;
 pub use crate::grid::{Col, Grid, Row};
 pub use crate::parse;