From 957e26f1cae9cdd2288ef16232615851e0d4a3e1 Mon Sep 17 00:00:00 2001 From: Toby Vincent Date: Wed, 20 Dec 2023 00:52:01 -0600 Subject: simplified with more wip --- src/day_17.rs | 221 +++++++++++++++++++++++++--------------------------------- src/lib.rs | 3 +- 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 { 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 { 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 { .try_collect::() } -#[cfg(test)] -fn rebuild_path(edges: &[Edge], start: Position, end: Position) -> Vec { - 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( +fn astar( grid: &Grid, start: Position, goal: Position, + min_step: usize, + max_step: usize, ) -> Option { - let mut queue = BinaryHeap::from([Reverse(Node::::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>; -type Position = (usize, usize); - -#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)] -pub struct Node { - estimated: usize, - cost: usize, - position: Position, - path: Vec, -} +fn extend_node( + mut node: Node, + edge: Edge, + min: usize, + max: usize, + grid: &Grid, +) -> Option<(Node, usize)> { + let mut cost = 0; -impl Node { - 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, 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, 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, start: Position) -> Vec { +// 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>; +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, + 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; -- cgit v1.2.3-70-g09d2