simplified with more wipday17

2 files changed, 98 insertions, 126 deletions

diff --git a/src/day_17.rs b/src/day_17.rs
index 728e1d8..c05a0d3 100644
--- a/src/day_17.rs
+++ b/src/day_17.rs
@@ -1,6 +1,6 @@
 use std::{
     cmp::Reverse,
-    collections::{hash_map::Entry, BinaryHeap, HashMap},
+    collections::{BinaryHeap, HashMap},
 };
 
 use anyhow::Context;
@@ -23,7 +23,7 @@ impl Solution for Day17 {
     fn part_1(input: &str) -> anyhow::Result<Self::Answer1> {
         let grid = parse_grid(input).context("Failed to parse grid")?;
 
-        astar::<1, 3>(&grid, (0, 0), (grid.len() - 1, grid[0].len() - 1))
+        astar(&grid, (0, 0), (grid.len() - 1, grid[0].len() - 1), 1, 3)
             .context("Failed to find path")
 
         // 755 ==
@@ -32,7 +32,7 @@ impl Solution for Day17 {
     fn part_2(input: &str) -> anyhow::Result<Self::Answer2> {
         let grid = parse_grid(input).context("Failed to parse grid")?;
 
-        astar::<4, 10>(&grid, (0, 0), (grid.len() - 1, grid[0].len() - 1))
+        astar(&grid, (0, 0), (grid.len() - 1, grid[0].len() - 1), 4, 10)
             .context("Failed to find path")
         // 879 <
         // 881 ==
@@ -50,151 +50,113 @@ fn parse_grid(input: &str) -> Option<Grid> {
         .try_collect::<Grid>()
 }
 
-#[cfg(test)]
-fn rebuild_path(edges: &[Edge], start: Position, end: Position) -> Vec<Position> {
-    let mut path = vec![];
-    let mut position = start;
-    for edge in edges {
-        path.push(position);
-        position = edge.traverse(position).unwrap();
-    }
-    path.push(end);
-    path
-}
-
-fn astar<const S: usize, const M: usize>(
+fn astar(
     grid: &Grid,
     start: Position,
     goal: Position,
+    min_step: usize,
+    max_step: usize,
 ) -> Option<usize> {
-    let mut queue = BinaryHeap::from([Reverse(Node::<S, M>::start(start))]);
-    let mut cache = HashMap::from([((start, None), usize::MAX)]);
-
-    #[cfg(test)]
-    let printer = &mut crate::Printer::from(std::io::stdout().lock());
+    let start_node = Node {
+        pos: start,
+        edge: None,
+        len: 0,
+        path: vec![],
+    };
+    let mut queue = BinaryHeap::from([(Reverse(0), start_node)]);
+    let mut cache = HashMap::from([]);
+
+    while let Some((Reverse(node_cost), node)) = queue.pop() {
+        if node.pos == goal {
+            // #[cfg(test)]
+            // crate::Printer::from(std::io::stdout().lock())
+            //     .with_grid(grid, &rebuild_path(node, &cache, start))
+            //     .write()
+            //     .unwrap();
+
+            return Some(node_cost);
+        }
 
-    while let Some(Reverse(node)) = queue.pop() {
-        for (edges, position, cost) in node.successors(grid) {
+        'edge_loop: for edge in Edge::ALL {
             let mut next = node.clone();
-            next.position = position;
-            next.path.extend(edges);
-            next.cost += cost;
-            next.estimated = next.cost + next.dist(goal);
-
-            #[cfg(test)]
-            {
-                let node = &next;
-                let path = rebuild_path(&node.path, start, node.position);
-                printer
-                    .with(format_args!("pos: {:?}", node.position))
-                    .with(format_args!("score: {}", node.cost))
-                    .with(format_args!("trail: {:?}", node.trail()))
-                    .with_grid(grid, &path)
-                    .clear()
-                    .write()
-                    .unwrap();
-            }
 
-            // pause();
-            if next.position == goal {
-                #[cfg(test)]
-                printer
-                    .with(format_args!("score: {}", node.cost))
-                    .with_grid(grid, &rebuild_path(&next.path, start, next.position))
-                    .clear()
-                    .write()
-                    .unwrap();
-                return Some(next.cost);
-            }
+            next.edge = Some(edge);
+            next.len = 0;
 
-            match cache.entry((next.position, next.trail())) {
-                Entry::Vacant(e) => {
-                    e.insert(next.cost);
-                }
-                Entry::Occupied(mut e) => {
-                    if next.cost < *e.get() {
-                        e.insert(next.cost);
-                    } else {
-                        continue;
-                    }
-                }
-            }
+            let Some((next, mut next_cost)) = extend_node(next, edge, min_step, max_step, grid)
+            else {
+                continue 'edge_loop;
+            };
+
+            next_cost += node_cost;
 
-            queue.push(Reverse(next))
+            if !cache.get(&next).is_some_and(|c| next_cost >= *c) {
+                cache.insert(next.clone(), next_cost);
+                queue.push((Reverse(next_cost), next));
+            }
         }
     }
 
     None
 }
 
-type Grid = Vec<Vec<usize>>;
-type Position = (usize, usize);
-
-#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)]
-pub struct Node<const STEP: usize, const MAX: usize> {
-    estimated: usize,
-    cost: usize,
-    position: Position,
-    path: Vec<Edge>,
-}
+fn extend_node(
+    mut node: Node,
+    edge: Edge,
+    min: usize,
+    max: usize,
+    grid: &Grid,
+) -> Option<(Node, usize)> {
+    let mut cost = 0;
 
-impl<const S: usize, const M: usize> Node<S, M> {
-    fn start(position: Position) -> Self {
-        Node {
-            position,
-            estimated: usize::MAX,
-            ..Default::default()
+    let len = match node.path.last() {
+        Some((e, l)) if *e == edge => {
+            node.len = *l;
+            node.len + 1
+        }
+        _ => min,
+    };
+
+    while node.len < len {
+        node.len += 1;
+        if node.len > max {
+            // println!("Breaking due to len: {}", node.len);
+            return None;
         }
-    }
 
-    fn trail(&self) -> Option<[Edge; M]> {
-        self.path.last_chunk().copied()
+        node.pos = node.edge?.traverse(node.pos)?;
+        cost += grid.get(node.pos.0)?.get(node.pos.1)?;
     }
 
-    fn successors(&self, grid: &Grid) -> Vec<(Vec<Edge>, Position, usize)> {
-        let (iter, last_seq) = match self.path.last() {
-            Some(last) => (
-                last.edges(),
-                Some((
-                    last,
-                    self.path.iter().rev().take_while(|e| *e == last).count(),
-                )),
-            ),
-            None => (Edge::ALL.as_slice(), None),
-        };
-
-        iter.iter()
-            .flat_map(|edge| {
-                match last_seq {
-                    Some((last, seq)) if last == edge => 1..=(M - seq),
-                    _ => S..=M,
-                }
-                .map(move |step| (edge, step))
-            })
-            .filter_map(|(edge, step)| self.traverse(*edge, step, grid))
-            .collect()
-    }
+    Some((node, cost))
+}
 
-    fn traverse(
-        &self,
-        edge: Edge,
-        step: usize,
-        grid: &Grid,
-    ) -> Option<(Vec<Edge>, Position, usize)> {
-        let mut cost = 0;
-        let mut position = self.position;
-
-        for _ in 0..step {
-            position = edge.traverse(position)?;
-            cost += grid.get(position.0)?.get(position.1)?;
-        }
+// #[cfg(test)]
+// fn rebuild_path(node: Node, cache: &HashMap<Node, usize>, start: Position) -> Vec<Position> {
+//     let mut path = vec![node.pos];
+//     let mut opt = Some((0, node));
+//     while let Some((_, next)) = opt {
+//         let mut pos = next.pos;
+//         for _ in 0..next.len {
+//             path.push(pos);
+//             pos = next.edge.unwrap().inverse().traverse(pos).unwrap();
+//         }
+//         opt = cache.get(&next).cloned();
+//     }
+//     path.push(start);
+//
+//     path
+// }
 
-        Some((vec![edge; step], position, cost))
-    }
+type Grid = Vec<Vec<usize>>;
+type Position = (usize, usize);
 
-    fn dist(&self, p2: Position) -> usize {
-        (self.position.0.abs_diff(p2.0) + self.position.1.abs_diff(p2.1)) * S
-    }
+#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
+struct Node {
+    pos: (usize, usize),
+    edge: Option<Edge>,
+    len: usize,
+    path: Vec<(Edge, usize)>,
 }
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
@@ -225,6 +187,15 @@ impl Edge {
             Edge::West => (row, col.checked_sub(1)?),
         })
     }
+
+    fn inverse(&self) -> Self {
+        match self {
+            Edge::North => Edge::South,
+            Edge::East => Edge::West,
+            Edge::South => Edge::North,
+            Edge::West => Edge::East,
+        }
+    }
 }
 
 #[cfg(test)]
diff --git a/src/lib.rs b/src/lib.rs
index fa1a737..a5fcd6d 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -7,7 +7,8 @@
     iter_intersperse,
     impl_trait_in_assoc_type,
     array_try_map,
-    slice_first_last_chunk
+    slice_first_last_chunk,
+    try_blocks
 )]
 
 pub mod day_01;