diff options
| -rw-r--r-- | src/day_17.rs | 163 | ||||
| -rw-r--r-- | src/lib.rs | 112 |
2 files changed, 212 insertions, 63 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)] @@ -3,8 +3,11 @@ iter_map_windows, iter_array_chunks, array_windows, + array_chunks, iter_intersperse, - impl_trait_in_assoc_type + impl_trait_in_assoc_type, + array_try_map, + slice_first_last_chunk )] pub mod day_01; @@ -58,3 +61,110 @@ pub trait Solution: Problem { Ok(()) } } + +pub use printer::Printer; + +pub mod printer { + + pub struct Printer<W: std::io::Write> { + lines: usize, + buffer: String, + writer: W, + } + + impl<W> From<W> for Printer<W> + where + W: std::io::Write, + { + fn from(value: W) -> Self { + Self { + lines: 0, + buffer: String::new(), + writer: value, + } + } + } + + impl<W: std::io::Write> Printer<W> { + pub fn write(&mut self) -> std::io::Result<&mut Self> { + writeln!(self.writer, "{}", self.buffer)?; + self.writer.flush()?; + + self.lines = self.buffer.lines().count() + 1; + self.buffer.clear(); + + Ok(self) + } + + pub fn write_pause(&mut self, prompt: &str) -> std::io::Result<&mut Self> { + use std::io::Read; + + self.buffer.push('\n'); + self.buffer.push_str(prompt); + + self.write()?; + let _ = std::io::stdin().read(&mut [0u8])?; + Ok(self) + } + + pub fn write_pause_condition( + &mut self, + prompt: &str, + cond: bool, + ) -> std::io::Result<&mut Self> { + if cond { + self.write_pause(prompt) + } else { + self.write() + } + } + + pub fn write_sleep(&mut self, time: u64) -> std::io::Result<&mut Self> { + self.write()?; + std::thread::sleep(std::time::Duration::from_millis(time)); + + Ok(self) + } + + pub fn clear(&mut self) -> &mut Self { + self.buffer + .insert_str(0, &"\x1b[1A\x1b[K".repeat(self.lines)); + self.lines = 0; + self + } + + pub fn with(&mut self, fmt: std::fmt::Arguments) -> &mut Self { + self.buffer.push('\n'); + self.buffer.push_str(format!("{}", fmt).as_str()); + self + } + + pub fn with_grid<T: std::fmt::Display>( + &mut self, + grid: &[Vec<T>], + highlight: &[(usize, usize)], + ) -> &mut Self { + let s = grid + .iter() + .enumerate() + .flat_map(|(x, row)| { + row.iter() + .enumerate() + .map(move |(y, s)| { + if highlight.contains(&(x, y)) { + format!("\x1b[1;30;42m{s}\x1b[0m") + } else { + s.to_string() + } + }) + .chain(std::iter::once("\n".to_string())) + }) + .collect::<String>(); + + self.buffer.push('\n'); + self.buffer.push_str(s.as_str()); + + self + } + } +} |