diff options
Diffstat (limited to 'src/day_17.rs')
| -rw-r--r-- | src/day_17.rs | 163 |
1 files changed, 101 insertions, 62 deletions
diff --git a/src/day_17.rs b/src/day_17.rs index 0ba3be8..728e1d8 100644 --- a/src/day_17.rs +++ b/src/day_17.rs @@ -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::<0, 3>(&grid, (0, 0), (grid.len() - 1, grid[0].len() - 1)) + astar::<1, 3>(&grid, (0, 0), (grid.len() - 1, grid[0].len() - 1)) .context("Failed to find path") // 755 == @@ -50,31 +50,64 @@ fn parse_grid(input: &str) -> Option<Grid> { .try_collect::<Grid>() } -fn astar<const M: u8, const N: u8>(grid: &Grid, start: Position, goal: Position) -> Option<usize> { - let mut queue = BinaryHeap::from([Reverse(Node::<M, N>::start(start))]); - let mut cache = HashMap::from([((start, vec![]), usize::MAX)]); +#[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>( + grid: &Grid, + start: Position, + goal: Position, +) -> 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()); while let Some(Reverse(node)) = queue.pop() { - for (edge, position) in node.successors(grid) { + for (edges, position, cost) in node.successors(grid) { let mut next = node.clone(); next.position = position; - next.path.push(edge); - next.cost += grid[position.0][position.1]; + next.path.extend(edges); + next.cost += cost; next.estimated = next.cost + next.dist(goal); - if next.goal(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); } - let trail = next - .path - .iter() - .copied() - .rev() - .take(N as usize) - .rev() - .collect::<Vec<_>>(); - match cache.entry((next.position, trail)) { + match cache.entry((next.position, next.trail())) { Entry::Vacant(e) => { e.insert(next.cost); } @@ -98,14 +131,14 @@ type Grid = Vec<Vec<usize>>; type Position = (usize, usize); #[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)] -pub struct Node<const M: u8, const N: u8> { +pub struct Node<const STEP: usize, const MAX: usize> { estimated: usize, cost: usize, position: Position, path: Vec<Edge>, } -impl<const M: u8, const N: u8> Node<M, N> { +impl<const S: usize, const M: usize> Node<S, M> { fn start(position: Position) -> Self { Node { position, @@ -114,56 +147,53 @@ impl<const M: u8, const N: u8> Node<M, N> { } } - fn goal(&self, position: Position) -> bool { - self.position == position - && self - .path - .iter() - .rev() - .take(M as usize) - .map_windows(|[a, b]| a == b) - .all(|b| b) + fn trail(&self) -> Option<[Edge; M]> { + self.path.last_chunk().copied() } - fn successors(&self, grid: &Grid) -> Vec<(Edge, Position)> { - let Some(last) = self.path.last() else { - return Edge::ALL - .into_iter() - .filter_map(|edge| self.traverse_edge(grid, edge)) - .collect::<Vec<_>>(); + 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), }; - last.edges() - .into_iter() - .filter(|edge| { - let seq = self.path.iter().rev().take_while(|e| *e == last).count(); - if edge == last { - seq < N as usize - } else { - seq >= M as usize + 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| self.traverse_edge(grid, edge)) + .filter_map(|(edge, step)| self.traverse(*edge, step, grid)) .collect() } - fn traverse_edge(&self, grid: &Grid, edge: Edge) -> Option<(Edge, Position)> { - let (row, col) = self.position; - - Some(( - edge, - match edge { - Edge::North => (row.checked_sub(1)?, col), - Edge::East if col < grid[row].len().saturating_sub(1) => (row, col.checked_add(1)?), - Edge::South if row < grid.len().saturating_sub(1) => (row.checked_add(1)?, col), - Edge::West => (row, col.checked_sub(1)?), - _ => return None, - }, - )) + 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)?; + } + + Some((vec![edge; step], position, cost)) } fn dist(&self, p2: Position) -> usize { - self.position.0.abs_diff(p2.0) + self.position.1.abs_diff(p2.1) + (self.position.0.abs_diff(p2.0) + self.position.1.abs_diff(p2.1)) * S } } @@ -178,14 +208,23 @@ enum Edge { impl Edge { const ALL: [Edge; 4] = [Edge::North, Edge::East, Edge::South, Edge::West]; - fn edges(&self) -> [Edge; 3] { + fn edges(&self) -> &[Edge] { match self { - Edge::North => [Edge::North, Edge::East, Edge::West], - Edge::East => [Edge::North, Edge::East, Edge::South], - Edge::South => [Edge::East, Self::South, Edge::West], - Edge::West => [Edge::North, Edge::South, Edge::West], + Edge::North => &[Edge::North, Edge::East, Edge::West], + Edge::East => &[Edge::North, Edge::East, Edge::South], + Edge::South => &[Edge::East, Self::South, Edge::West], + Edge::West => &[Edge::North, Edge::South, Edge::West], } } + + fn traverse(&self, (row, col): Position) -> Option<Position> { + Some(match self { + Edge::North => (row.checked_sub(1)?, col), + Edge::East => (row, col.checked_add(1)?), + Edge::South => (row.checked_add(1)?, col), + Edge::West => (row, col.checked_sub(1)?), + }) + } } #[cfg(test)] |