diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/day_17.rs | 221 | ||||
-rw-r--r-- | 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<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)] @@ -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; |