diff options
| -rw-r--r-- | 2024/04/rust/src/main.rs | 18 | ||||
| -rw-r--r-- | lib/rust/src/grid.rs | 182 | ||||
| -rw-r--r-- | lib/rust/src/lib.rs | 99 |
3 files changed, 188 insertions, 111 deletions
diff --git a/2024/04/rust/src/main.rs b/2024/04/rust/src/main.rs index fd6a715..f3b152c 100644 --- a/2024/04/rust/src/main.rs +++ b/2024/04/rust/src/main.rs @@ -1,4 +1,6 @@ -use aoc::Grid; +#![feature(iter_order_by)] + +use aoc::grid::{chebyshev_ball, Grid}; use std::io; fn main() -> io::Result<()> { @@ -17,19 +19,9 @@ fn main() -> io::Result<()> { } fn silver(grid: &Grid<char>) -> usize { - let dirs = [ - (1, 1), - (1, 0), - (1, -1), - (0, 1), - (0, -1), - (-1, 1), - (-1, 0), - (-1, -1), - ]; grid.points() - .flat_map(|p| dirs.into_iter().map(move |dp| grid.ray(p, dp))) - .map(|cs| cs.zip("XMAS".chars()).all(|(&a, b)| a == b)) + .flat_map(|p| chebyshev_ball(1).map(move |dp| grid.ray(p, dp))) + .map(|cs| cs.take(4).eq_by("XMAS".chars(), |a, b| *a == b)) .filter(|p| *p) .count() } diff --git a/lib/rust/src/grid.rs b/lib/rust/src/grid.rs new file mode 100644 index 0000000..cc2e2e6 --- /dev/null +++ b/lib/rust/src/grid.rs @@ -0,0 +1,182 @@ +#[derive(Debug)] +pub struct Grid<T> { + data: Vec<T>, + width: usize, + height: usize, +} + +type Point = (usize, usize); +type Direction = (i64, i64); + +pub fn chebyshev_ball(n: i64) -> impl Iterator<Item = Direction> { + (-n..=n).flat_map(move |x| (-n..=n).map(move |y| (x, y))) +} + +impl<T> Grid<T> { + pub fn new(grid: Vec<Vec<T>>) -> Grid<T> { + // unfold grid. assume that width/height are consistent + Grid { + height: grid.len(), + width: grid.first().map_or(0, Vec::len), + data: grid.into_iter().flatten().collect(), + } + } + + pub fn at(&self, (x, y): Point) -> Option<&T> { + if x >= self.width || y >= self.height { + None + } else { + self.data.get(x + y * self.width) + } + } + + pub fn is_in(&self, p: Point) -> bool { + self.at(p).is_some() + } + + pub fn points(&self) -> impl Iterator<Item = Point> { + (0..self.width).flat_map(|x| (0..self.height).map(move |y| (x, y))) + } + + pub fn move_pos(&self, (x, y): Point, (dx, dy): Direction, n: i64) -> Option<Point> { + let x = (i64::try_from(x).ok()? + n * dx).try_into().ok()?; + let y = (i64::try_from(y).ok()? + n * dy).try_into().ok()?; + let p = (x, y); + if self.is_in(p) { Some(p) } else { None } + } + + pub fn ray(&self, p: Point, dp: Direction) -> impl Iterator<Item = &T> { + (0..) + .map(move |n| self.move_pos(p, dp, n)) + .take_while(Option::is_some) + .flatten() + .map(|p| self.at(p)) + .flatten() + } +} + +#[cfg(test)] +mod tests { + use std::collections::HashSet; + + use super::*; + + #[test] + fn chebyshev_ball_zero() { + assert_eq!( + chebyshev_ball(0).collect::<HashSet<_>>(), + [(0, 0)].iter().cloned().collect() + ) + } + + #[test] + fn chebyshev_ball_one() { + assert_eq!( + chebyshev_ball(1).collect::<HashSet<_>>(), + [ + (-1, -1), + (-1, 0), + (-1, 1), + (0, -1), + (0, 0), + (0, 1), + (1, -1), + (1, 0), + (1, 1) + ] + .iter() + .cloned() + .collect() + ) + } + + #[test] + fn chebyshev_ball_two() { + let points = chebyshev_ball(2).collect::<HashSet<_>>(); + assert_eq!(points.len(), 25); + let norms = points + .iter() + .map(|(x, y)| x.abs().max(y.abs())) + .collect::<Vec<_>>(); + + assert_eq!(norms.iter().filter(|&&n| n == 0).count(), 1); + assert_eq!(norms.iter().filter(|&&n| n == 1).count(), 8); + assert_eq!(norms.iter().filter(|&&n| n == 2).count(), 16); + } + + #[test] + fn create_grid() { + let _grid = Grid::new(vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]]); + } + + #[test] + fn at_exists() { + let grid = Grid::new(vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]]); + assert_eq!(grid.at((1, 0)).unwrap(), &2); + } + + #[test] + fn at_not_exists() { + let grid = Grid::new(vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]]); + assert!(grid.at((17, 10)).is_none()); + } + + #[test] + fn points_empty() { + let grid = Grid::<u64>::new(vec![vec![]]); + assert!(grid.points().eq(vec![])) + } + + #[test] + fn points_equal_size() { + let grid = Grid::new(vec![vec![1, 2], vec![3, 4]]); + let points = grid.points().collect::<HashSet<_>>(); + assert_eq!( + points, + [(0, 0), (0, 1), (1, 0), (1, 1)].iter().cloned().collect() + ) + } + + #[test] + fn points_unequal_size() { + let grid = Grid::new(vec![vec![1, 2], vec![3, 4], vec![5, 6]]); + let points = grid.points().collect::<HashSet<_>>(); + assert_eq!( + points, + [(0, 0), (1, 0), (0, 1), (1, 1), (0, 2), (1, 2)] + .iter() + .cloned() + .collect() + ) + } + + #[test] + fn ray_empty() { + let grid = Grid::<u64>::new(vec![vec![]]); + assert!(grid.ray((1, 1), (1, 2)).eq(vec![].iter())) + } + + #[test] + fn ray_single_element() { + let grid = Grid::<u64>::new(vec![vec![1]]); + assert!(grid.ray((0, 0), (1, 2)).eq(vec![1].iter())) + } + + #[test] + fn ray_horizontal() { + let grid = Grid::new(vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]]); + assert!(grid.ray((0, 0), (1, 0)).eq(vec![1, 2, 3].iter())) + } + + #[test] + fn ray_vertical() { + let grid = Grid::new(vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]]); + assert!(grid.ray((1, 0), (0, 1)).eq(vec![2, 5, 8].iter())) + } + + #[test] + fn ray_diagonal() { + let grid = Grid::new(vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]]); + assert!(grid.ray((0, 0), (1, 2)).eq(vec![1, 8].iter())) + } +} diff --git a/lib/rust/src/lib.rs b/lib/rust/src/lib.rs index 060439f..f7a1b46 100644 --- a/lib/rust/src/lib.rs +++ b/lib/rust/src/lib.rs @@ -1,98 +1 @@ -#[derive(Debug)] -pub struct Grid<T> { - grid: Vec<Vec<T>>, -} - -impl<T> Grid<T> { - pub fn new(grid: Vec<Vec<T>>) -> Grid<T> { - Grid { grid } - } - - pub fn points(&self) -> impl Iterator<Item = (usize, usize)> { - (0..self.grid.len()) - .flat_map(|y| (0..self.grid.first().unwrap_or(&Vec::new()).len()).map(move |x| (x, y))) - } - - pub fn ray(&self, (x, y): (usize, usize), (dx, dy): (i64, i64)) -> impl Iterator<Item = &T> { - let (x, y) = (i64::try_from(x).unwrap(), i64::try_from(y).unwrap()); - (0..) - .map(move |n| { - self.grid - .get(usize::try_from(y + n * dy).ok()?) - .and_then(|row| row.get(usize::try_from(x + n * dx).ok()?)) - }) - .take_while(Option::is_some) - .flatten() - } -} - -#[cfg(test)] -mod tests { - use std::collections::HashSet; - - use super::*; - - #[test] - fn create_grid() { - let _grid = Grid::new(vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]]); - } - - #[test] - fn points_empty() { - let grid = Grid::<u64>::new(vec![vec![]]); - assert!(grid.points().eq(vec![])) - } - - #[test] - fn points_equal_size() { - let grid = Grid::new(vec![vec![1, 2], vec![3, 4]]); - let points = grid.points().collect::<HashSet<_>>(); - assert_eq!( - points, - [(0, 0), (0, 1), (1, 0), (1, 1)].iter().cloned().collect() - ) - } - - #[test] - fn points_unequal_size() { - let grid = Grid::new(vec![vec![1, 2], vec![3, 4], vec![5, 6]]); - let points = grid.points().collect::<HashSet<_>>(); - assert_eq!( - points, - [(0, 0), (1, 0), (0, 1), (1, 1), (0, 2), (1, 2)] - .iter() - .cloned() - .collect() - ) - } - - #[test] - fn ray_empty() { - let grid = Grid::<u64>::new(vec![vec![]]); - assert!(grid.ray((1, 1), (1, 2)).eq(vec![].iter())) - } - - #[test] - fn ray_single_element() { - let grid = Grid::<u64>::new(vec![vec![1]]); - assert!(grid.ray((0, 0), (1, 2)).eq(vec![1].iter())) - } - - #[test] - fn ray_horizontal() { - let grid = Grid::new(vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]]); - assert!(grid.ray((0, 0), (1, 0)).eq(vec![1, 2, 3].iter())) - } - - #[test] - fn ray_vertical() { - let grid = Grid::new(vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]]); - assert!(grid.ray((1, 0), (0, 1)).eq(vec![2, 5, 8].iter())) - } - - #[test] - fn ray_diagonal() { - let grid = Grid::new(vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]]); - assert!(grid.ray((0, 0), (1, 2)).eq(vec![1, 8].iter())) - } -} +pub mod grid; |