bwc9876.dev
Advent of Code solutions
1use cursors::GridCursor;
2
3use crate::{
4 dir::{Direction, Movement, CARDINALS},
5 pos::Position,
6};
7
8#[derive(Clone)]
9/// A 2D integer grid of values.
10///
11/// This grid is represented by a vector of vectors.
12///
13/// # Examples
14///
15/// ```
16/// use utils::prelude::*;
17///
18/// let data = vec![
19/// vec![1, 2, 3],
20/// vec![4, 5, 6],
21/// vec![7, 8, 9],
22/// ];
23///
24/// let grid = Grid::new(data);
25///
26/// assert_eq!(grid.get(Position::new(0, 0)), Some(&1));
27/// assert_eq!(grid.get(Position::new(1, 1)), Some(&5));
28/// assert_eq!(grid.get(Position::new(2, 2)), Some(&9));
29/// ```
30///
31pub struct Grid<T> {
32 data: Vec<Vec<T>>,
33}
34
35impl<T> Grid<T> {
36 /// Create a new grid from a vector of vectors.
37 pub fn new(data: Vec<Vec<T>>) -> Self {
38 Self { data }
39 }
40
41 /// Parse a grid from a string, this will convert each character into `T` via `From<char>`.
42 ///
43 /// Use the `tiles!` macro to easily create an enum that implements `From<char>`.
44 ///
45 /// # Examples
46 ///
47 /// ```
48 /// use utils::prelude::*;
49 ///
50 /// #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
51 /// enum Tile {
52 /// Floor,
53 /// Wall,
54 /// }
55 ///
56 /// impl From<char> for Tile {
57 /// fn from(c: char) -> Self {
58 /// match c {
59 /// '.' => Self::Floor,
60 /// '#' => Self::Wall,
61 /// _ => panic!("Invalid tile {c}"),
62 /// }
63 /// }
64 /// }
65 ///
66 /// let input = ".#.\n#.#\n.#.";
67 /// let grid = Grid::<Tile>::parse(input);
68 ///
69 /// assert_eq!(grid.get(Position::new(0, 0)), Some(&Tile::Floor));
70 /// assert_eq!(grid.get(Position::new(1, 0)), Some(&Tile::Wall));
71 /// assert_eq!(grid.get(Position::new(2, 0)), Some(&Tile::Floor));
72 /// assert_eq!(grid.get(Position::new(1, 1)), Some(&Tile::Floor));
73 /// ```
74 ///
75 /// Using `tiles!`...
76 ///
77 /// ```
78 /// use utils::prelude::*;
79 /// use utils::tiles;
80 ///
81 /// tiles!(Tile, [
82 /// '.' => Floor,
83 /// '#' => Wall,
84 /// ]);
85 ///
86 /// let input = ".#.\n#.#\n.#.";
87 /// let grid = Grid::<Tile>::parse(input);
88 ///
89 /// assert_eq!(grid.get(Position::new(0, 0)), Some(&Tile::Floor));
90 /// assert_eq!(grid.get(Position::new(1, 0)), Some(&Tile::Wall));
91 /// assert_eq!(grid.get(Position::new(2, 0)), Some(&Tile::Floor));
92 /// assert_eq!(grid.get(Position::new(1, 1)), Some(&Tile::Floor));
93 /// ```
94 ///
95 pub fn parse(input: &str) -> Self
96 where
97 T: From<char>,
98 {
99 let data = input
100 .lines()
101 .map(|line| line.chars().map(|c| c.into()).collect())
102 .collect();
103 Self::new(data)
104 }
105
106 /// Return the width of the grid.
107 pub fn width(&self) -> usize {
108 self.data[0].len()
109 }
110
111 /// Return the height of the grid.
112 pub fn height(&self) -> usize {
113 self.data.len()
114 }
115
116 /// Get the size of the grid.
117 pub fn size(&self) -> (usize, usize) {
118 (self.width(), self.height())
119 }
120
121 /// Get the bounds of the grid.
122 ///
123 /// (This is the same as `self.size()` with -1 added to each component)
124 pub fn bounds(&self) -> (usize, usize) {
125 (self.width() - 1, self.height() - 1)
126 }
127
128 /// Get if a given position is in this grid's bounds
129 pub fn in_bounds(&self, pos: &Position) -> bool {
130 pos.x >= 0 && pos.y >= 0 && pos.x < self.width() as isize && pos.y < self.height() as isize
131 }
132
133 /// Get a value from the grid at the given position.
134 ///
135 /// # Examples
136 ///
137 /// ```
138 /// use utils::prelude::*;
139 ///
140 /// let data = vec![
141 /// vec![1, 2, 3],
142 /// vec![4, 5, 6],
143 /// vec![7, 8, 9],
144 /// ];
145 ///
146 /// let grid = Grid::new(data);
147 /// assert_eq!(grid.get(Position::new(0, 0)), Some(&1));
148 /// assert_eq!(grid.get(Position::new(1, 1)), Some(&5));
149 /// assert_eq!(grid.get(Position::new(2, 2)), Some(&9));
150 /// assert_eq!(grid.get(Position::new(3, 3)), None);
151 /// ```
152 ///
153 pub fn get(&self, pos: Position) -> Option<&T> {
154 self.data
155 .get(pos.y as usize)
156 .and_then(|row| row.get(pos.x as usize))
157 }
158
159 /// Obtain a mutable reference to a tile in the grid
160 pub fn get_mut(&mut self, pos: Position) -> Option<&mut T> {
161 self.data
162 .get_mut(pos.y as usize)
163 .and_then(|row| row.get_mut(pos.x as usize))
164 }
165
166 /// Get a value from the grid at the given position,
167 /// panicking if the position is out of bounds.
168 ///
169 /// # Examples
170 ///
171 /// ```
172 /// use utils::prelude::*;
173 ///
174 /// let data = vec![
175 /// vec![1, 2, 3],
176 /// vec![4, 5, 6],
177 /// vec![7, 8, 9],
178 /// ];
179 ///
180 /// let grid = Grid::new(data);
181 ///
182 /// assert_eq!(grid.unsafe_get(Position::new(0, 0)), &1);
183 /// assert_eq!(grid.unsafe_get(Position::new(1, 1)), &5);
184 /// ```
185 ///
186 pub fn unsafe_get(&self, pos: Position) -> &T {
187 &self.data[pos.y as usize][pos.x as usize]
188 }
189
190 /// Get the value at the given position, wrapping around the grid if necessary.
191 ///
192 /// # Examples
193 ///
194 /// ```
195 /// use utils::prelude::*;
196 ///
197 /// let data = vec![
198 /// vec![1, 2, 3],
199 /// vec![4, 5, 6],
200 /// vec![7, 8, 9],
201 /// ];
202 ///
203 /// let grid = Grid::new(data);
204 /// assert_eq!(grid.get_wrapped(Position::new(0, 0)), &1);
205 /// assert_eq!(grid.get_wrapped(Position::new(1, 1)), &5);
206 /// assert_eq!(grid.get_wrapped(Position::new(2, 2)), &9);
207 /// assert_eq!(grid.get_wrapped(Position::new(3, 3)), &1);
208 /// assert_eq!(grid.get_wrapped(Position::new(-1, -1)), &9);
209 /// ```
210 ///
211 pub fn get_wrapped(&self, pos: Position) -> &T {
212 let wrapped_pos = pos.bind(self.size());
213 &self.data[wrapped_pos.1][wrapped_pos.0]
214 }
215
216 /// Iterate over a row of the grid.
217 ///
218 /// # Examples
219 ///
220 /// ```
221 /// use utils::prelude::*;
222 ///
223 /// let data = vec![
224 /// vec![1, 2, 3],
225 /// vec![4, 5, 6],
226 /// vec![7, 8, 9],
227 /// ];
228 ///
229 /// let grid = Grid::new(data);
230 ///
231 /// assert_eq!(grid.iter_row(0).unwrap().collect::<Vec<_>>(), vec![&1, &2, &3]);
232 /// assert_eq!(grid.iter_row(1).unwrap().sum::<usize>(), 4+5+6);
233 /// assert!(grid.iter_row(8).is_none());
234 /// ```
235 ///
236 pub fn iter_row(&self, row: usize) -> Option<impl Iterator<Item = &T>> {
237 self.data.get(row).map(|row| row.iter())
238 }
239
240 /// Iterate over a column of the grid.
241 ///
242 /// # Examples
243 ///
244 /// ```
245 /// use utils::prelude::*;
246 ///
247 ///
248 /// let data = vec![
249 /// vec![1, 2, 3],
250 /// vec![4, 5, 6],
251 /// vec![7, 8, 9],
252 /// ];
253 ///
254 /// let grid = Grid::new(data);
255 ///
256 /// assert_eq!(grid.iter_col(0).unwrap().collect::<Vec<_>>(), vec![&1, &4, &7]);
257 /// assert_eq!(grid.iter_col(1).unwrap().sum::<usize>(), 2+5+8);
258 /// assert!(grid.iter_col(8).is_none());
259 /// ```
260 ///
261 pub fn iter_col(&self, col: usize) -> Option<impl Iterator<Item = &T>> {
262 if col > self.width() {
263 return None;
264 }
265 Some(self.data.iter().filter_map(move |row| row.get(col)))
266 }
267
268 /// Get a row of the grid.
269 ///
270 /// This is the same as `self.iter_row(row).map(|iter| iter.collect())`.
271 pub fn get_row(&self, y: usize) -> Option<Vec<&T>> {
272 self.iter_row(y).map(|iter| iter.collect())
273 }
274
275 /// Get a column of the grid.
276 ///
277 /// This is the same as `self.iter_col(col).map(|iter| iter.collect())`.
278 pub fn get_col(&self, x: usize) -> Option<Vec<&T>> {
279 self.iter_col(x).map(|iter| iter.collect())
280 }
281
282 /// Iterate over all rows of the grid.
283 ///
284 /// # Examples
285 ///
286 /// ```
287 /// use utils::prelude::*;
288 ///
289 ///
290 /// let data = vec![
291 /// vec![1, 2, 3],
292 /// vec![4, 5, 6],
293 /// vec![7, 8, 9],
294 /// ];
295 ///
296 /// let grid = Grid::new(data);
297 ///
298 /// assert_eq!(grid.iter_rows().enumerate().filter_map(|(y, row)| row.collect::<Vec<_>>().get(y).copied()).sum::<usize>(), 1+5+9);
299 /// ```
300 ///
301 pub fn iter_rows(&self) -> impl Iterator<Item = impl Iterator<Item = &T>> {
302 self.data.iter().map(|row| row.iter())
303 }
304
305 /// Iterate over all columns of the grid.
306 ///
307 /// # Examples
308 ///
309 /// ```
310 /// use utils::prelude::*;
311 ///
312 ///
313 /// let data = vec![
314 /// vec![1, 2, 3],
315 /// vec![4, 5, 6],
316 /// vec![7, 8, 9],
317 /// ];
318 ///
319 /// let grid = Grid::new(data);
320 ///
321 /// assert_eq!(grid.iter_cols().enumerate().filter_map(|(x, col)| col.collect::<Vec<_>>().get(x).copied()).sum::<usize>(), 1+5+9);
322 /// ```
323 ///
324 pub fn iter_cols(&self) -> impl Iterator<Item = impl Iterator<Item = &T>> {
325 (0..self.width()).map(move |col| self.iter_col(col).unwrap())
326 }
327
328 /// Iterate over all elements of the grid.
329 ///
330 /// This also yields the position of each element for easy access.
331 ///
332 /// # Examples
333 ///
334 /// ```
335 /// use utils::prelude::*;
336 ///
337 /// let data = vec![
338 /// vec![1, 2, 3],
339 /// vec![4, 5, 6],
340 /// vec![7, 8, 9],
341 /// ];
342 ///
343 /// let grid = Grid::new(data);
344 ///
345 /// assert_eq!(grid.iter().map(|(_, v)| v).sum::<usize>(), 1+2+3+4+5+6+7+8+9);
346 /// ```
347 ///
348 pub fn iter(&self) -> impl Iterator<Item = (Position, &T)> {
349 self.data.iter().enumerate().flat_map(|(y, row)| {
350 row.iter()
351 .enumerate()
352 .map(move |(x, col)| (Position::new(x as isize, y as isize), col))
353 })
354 }
355
356 /// Iterate over all elements of the grid.
357 ///
358 /// This also yields the position of each element for easy access.
359 ///
360 /// # Examples
361 ///
362 /// ```
363 /// use utils::prelude::*;
364 ///
365 /// let data = vec![
366 /// vec![1, 2, 3],
367 /// vec![4, 5, 6],
368 /// vec![7, 8, 9],
369 /// ];
370 ///
371 /// let grid = Grid::new(data);
372 ///
373 /// assert_eq!(grid.iter().map(|(_, v)| v).sum::<usize>(), 1+2+3+4+5+6+7+8+9);
374 /// ```
375 ///
376 pub fn iter_mut(&mut self) -> impl Iterator<Item = (Position, &mut T)> {
377 self.data.iter_mut().enumerate().flat_map(|(y, row)| {
378 row.iter_mut()
379 .enumerate()
380 .map(move |(x, col)| (Position::new(x as isize, y as isize), col))
381 })
382 }
383
384 /// Get all positions relative to the given position in the grid based off the given kernels.
385 ///
386 /// This will automatically filter out any positions that are out of bounds.
387 ///
388 /// # Examples
389 ///
390 /// ```
391 /// use utils::prelude::*;
392 ///
393 /// let data = vec![
394 /// vec![1, 2, 3],
395 /// vec![4, 5, 6],
396 /// vec![7, 8, 9],
397 /// ];
398 ///
399 /// let grid = Grid::new(data);
400 ///
401 /// let pos = Position::new(1, 1);
402 /// let kernels = &[
403 /// Direction::North,
404 /// Direction::East,
405 /// ];
406 ///
407 /// let mut relatives = grid.relatives(pos, kernels);
408 ///
409 /// assert_eq!(relatives.next(), Some((Direction::North, Position::new(1, 0), &2)));
410 /// assert_eq!(relatives.next(), Some((Direction::East, Position::new(2, 1), &6)));
411 /// ```
412 ///
413 /// ```
414 /// use utils::prelude::*;
415 ///
416 /// let data = vec![
417 /// vec![1, 2, 3],
418 /// vec![4, 5, 6],
419 /// vec![7, 8, 9],
420 /// ];
421 ///
422 /// let grid = Grid::new(data);
423 ///
424 /// let pos = Position::new(1, 0);
425 /// let kernels = &[
426 /// Direction::North, // This will be filtered out, as (1, -1) is out of bounds
427 /// Direction::East,
428 /// ];
429 ///
430 /// let mut relatives = grid.relatives(pos, kernels);
431 ///
432 /// assert_eq!(relatives.next(), Some((Direction::East, Position::new(2, 0), &3)));
433 /// ```
434 ///
435 pub fn relatives<'a, M: Movement>(
436 &'a self,
437 pos: Position,
438 kernels: &'a [M],
439 ) -> impl Iterator<Item = (M, Position, &'a T)> + 'a {
440 pos.relatives(kernels)
441 .filter_map(move |(pos, dir)| self.get(pos).map(|v| (dir, pos, v)))
442 }
443
444 pub fn relatives_valid<'a, M: Movement>(
445 &'a self,
446 pos: Position,
447 kernels: &'a [M],
448 ) -> impl Iterator<Item = (M, Option<(Position, &'a T)>)> + 'a {
449 pos.relatives(kernels)
450 .map(move |(pos, dir)| (dir, self.get(pos).map(|v| (pos, v))))
451 }
452
453 /// Get all positions relative to the given position, returning [None] if the relatives would
454 /// go out of bounds
455 ///
456 /// # Examples
457 ///
458 /// ```
459 /// use utils::prelude::*;
460 ///
461 /// let data = vec![
462 /// vec![1, 2, 3],
463 /// vec![4, 5, 6],
464 /// vec![7, 8, 9],
465 /// ];
466 ///
467 /// let grid = Grid::new(data);
468 ///
469 /// let pos = Position::new(1, 1);
470 /// let kernels = &[
471 /// Direction::North,
472 /// Direction::East,
473 /// ];
474 ///
475 /// let mut relatives = grid.relatives_strict(pos, kernels);
476 /// if let Some(relatives) = relatives {
477 /// assert_eq!(relatives.get(0), Some((Direction::North, Position::new(1, 0), &2)).as_ref());
478 /// assert_eq!(relatives.get(1), Some((Direction::East, Position::new(2, 1), &6)).as_ref());
479 /// } else { panic!("Relatives should be Some!") }
480 /// ```
481 ///
482 /// ```
483 /// use utils::prelude::*;
484 ///
485 /// let data = vec![
486 /// vec![1, 2, 3],
487 /// vec![4, 5, 6],
488 /// vec![7, 8, 9],
489 /// ];
490 ///
491 /// let grid = Grid::new(data);
492 ///
493 /// let pos = Position::new(1, 0);
494 /// let kernels = &[
495 /// Direction::North, // This will result in [None], as (1, -1) is out of bounds
496 /// Direction::East,
497 /// ];
498 ///
499 /// let mut relatives = grid.relatives_strict(pos, kernels);
500 ///
501 /// assert!(relatives.is_none());
502 /// ```
503 pub fn relatives_strict<M: Movement>(
504 &self,
505 pos: Position,
506 kernels: &[M],
507 ) -> Option<Vec<(M, Position, &T)>> {
508 pos.relatives(kernels)
509 .map(move |(pos, dir)| self.get(pos).map(|v| (dir, pos, v)))
510 .collect::<Option<Vec<_>>>()
511 }
512
513 /// Get all positions relative to the given position in the grid based off the given kernels.
514 ///
515 /// Wraps around the grid if necessary.
516 ///
517 pub fn relatives_wrapped<'a, M: Movement>(
518 &'a self,
519 pos: Position,
520 kernels: &'a [M],
521 ) -> impl Iterator<Item = (M, Position, &'a T)> + 'a {
522 pos.relatives(kernels)
523 .map(move |(pos, dir)| (dir, pos, self.get_wrapped(pos)))
524 }
525
526 /// Get all positions relative to the given position in the grid based off the given kernels,
527 /// applying the kernel multiple times.
528 ///
529 /// This will automatically filter out any positions that are out of bounds.
530 ///
531 pub fn relatives_expand_by<'a, M: Movement>(
532 &'a self,
533 pos: Position,
534 kernels: &'a [M],
535 expand: usize,
536 ) -> impl Iterator<Item = ((M, usize), Position, &'a T)> + 'a {
537 pos.relatives_expand_by(kernels, expand)
538 .filter_map(move |(dir, pos)| self.get(pos).map(|v| (dir, pos, v)))
539 }
540
541 /// Get all positions relative to the given position in the grid based off the given kernels,
542 /// applying the kernel multiple times.
543 ///
544 /// Wraps around the grid if necessary.
545 ///
546 pub fn relatives_expand_by_wrapped<'a, M: Movement>(
547 &'a self,
548 pos: Position,
549 kernels: &'a [M],
550 expand: usize,
551 ) -> impl Iterator<Item = ((M, usize), Position, &'a T)> + 'a {
552 pos.relatives_expand_by(kernels, expand)
553 .map(move |(dir, pos)| (dir, pos, self.get_wrapped(pos)))
554 }
555
556 /// Like [Grid::relatives] but with `kernels` set to the four cardinal directions.
557 pub fn adjacent(&self, pos: Position) -> impl Iterator<Item = (Direction, Position, &T)> {
558 self.relatives(pos, &CARDINALS)
559 }
560
561 /// Like [Grid::relatives_wrapped] but with `kernels` set to the four cardinal directions.
562 pub fn adjacent_wrapped(
563 &self,
564 pos: Position,
565 ) -> impl Iterator<Item = (Direction, Position, &T)> {
566 self.relatives_wrapped(pos, &CARDINALS)
567 }
568
569 /// Like [Grid::relatives_expand_by] but with `kernels` set to the four cardinal directions.
570 pub fn adjacent_expand_by(
571 &self,
572 pos: Position,
573 expand: usize,
574 ) -> impl Iterator<Item = ((Direction, usize), Position, &T)> {
575 self.relatives_expand_by(pos, &CARDINALS, expand)
576 }
577
578 /// Like [Grid::relatives_expand_by_wrapped] but with `kernels` set to the four cardinal directions.
579 pub fn adjacent_expand_by_wrapped(
580 &self,
581 pos: Position,
582 expand: usize,
583 ) -> impl Iterator<Item = ((Direction, usize), Position, &T)> {
584 self.relatives_expand_by_wrapped(pos, &CARDINALS, expand)
585 }
586
587 /// Create a new cursor for this grid facing in the specified direction at the specified
588 /// position
589 pub fn cursor<D: Movement>(&self, pos: Position, dir: D) -> GridCursor<'_, T, D> {
590 GridCursor::new(self, pos, dir)
591 }
592}
593
594impl<T: Eq> Grid<T> {
595 pub fn find_tile(&self, tile: &T) -> Option<Position> {
596 self.iter()
597 .find_map(|(p, t)| if t == tile { Some(p) } else { None })
598 }
599
600 pub fn cursor_at_tile<D: Movement>(&self, tile: &T, dir: D) -> Option<GridCursor<'_, T, D>> {
601 self.find_tile(tile).map(|pos| self.cursor(pos, dir))
602 }
603}
604
605impl<T: std::fmt::Debug> std::fmt::Debug for Grid<T> {
606 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
607 let mut debug = f.debug_struct("Grid");
608 for (y, row) in self.data.iter().enumerate() {
609 debug.field(&format!("row_{}", y), row);
610 }
611 debug.finish()
612 }
613}
614
615/// Utilities for making tiles of a grid.
616pub mod tiles {
617 use crate::{dir::Movement, pos::Position};
618
619 use super::Grid;
620
621 #[macro_export]
622 /// Create an enum that implements `From<char>`.
623 ///
624 /// There are three versions of this macro:
625 ///
626 /// ## 1. Simple
627 ///
628 /// Create a simple enum that implements `From<char>`, with the specific characters mapping to specific variants.
629 /// Also will make the implementation panic if an invalid character is given.
630 ///
631 /// ```
632 /// use utils::prelude::*;
633 /// use utils::tiles;
634 ///
635 /// tiles!(Tile, [
636 /// '.' => Floor,
637 /// '#' => Wall,
638 /// ]);
639 ///
640 /// assert_eq!(Tile::from('.'), Tile::Floor);
641 /// assert_eq!(Tile::from('#'), Tile::Wall);
642 /// ```
643 ///
644 /// ## 2. With Extra Variants
645 ///
646 /// Create an enum that implements `From<char>`, with the specific characters mapping to specific variants.
647 /// Also allows for extra variants to be added, which won't be mapped to any characters.
648 ///
649 /// ```
650 /// use utils::prelude::*;
651 /// use utils::tiles;
652 ///
653 /// tiles!(Tile, [
654 /// '.' => Floor,
655 /// '#' => Wall,
656 /// ], [
657 /// Empty,
658 /// ]);
659 ///
660 /// assert_eq!(Tile::from('.'), Tile::Floor);
661 /// assert_eq!(Tile::from('#'), Tile::Wall);
662 /// let empty = Tile::Empty;
663 /// ```
664 ///
665 /// The extra variants can also have fields.
666 ///
667 /// ```
668 /// use utils::prelude::*;
669 /// use utils::tiles;
670 ///
671 /// tiles!(Tile, [
672 /// '.' => Floor,
673 /// '#' => Wall,
674 /// ], [
675 /// Door(bool),
676 /// ]);
677 ///
678 /// assert_eq!(Tile::from('.'), Tile::Floor);
679 /// assert_eq!(Tile::from('#'), Tile::Wall);
680 /// let door = Tile::Door(true);
681 /// ```
682 ///
683 /// ## 3. With Extra Variants and Extra Logic for Invalid Characters
684 ///
685 /// Create an enum that implements `From<char>`, with the specific characters mapping to specific variants.
686 /// Also allows for extra variants to be added, which won't be mapped to any characters.
687 /// Also allows for extra logic to be added for invalid characters.
688 ///
689 /// ```
690 /// use utils::prelude::*;
691 /// use utils::tiles;
692 ///
693 /// tiles!(Tile, [
694 /// '.' => Floor,
695 /// '#' => Wall,
696 /// ], [
697 /// Slope(Direction)
698 /// ], |c| {
699 /// match c {
700 /// '>' => Tile::Slope(Direction::East),
701 /// '<' => Tile::Slope(Direction::West),
702 /// _ => panic!("Invalid tile {c}"),
703 /// }
704 /// });
705 ///
706 /// assert_eq!(Tile::from('.'), Tile::Floor);
707 /// assert_eq!(Tile::from('#'), Tile::Wall);
708 /// assert_eq!(Tile::from('>'), Tile::Slope(Direction::East));
709 /// ```
710 ///
711 macro_rules! tiles {
712 ($name:ident, [$($char:pat => $v_name:ident$(,)?)*]) => {
713 tiles!($name, [$($char => $v_name,)*], [], |c| { panic!("Invalid tile {c}") });
714 };
715
716 ($name:ident, [$($char:pat => $v_name:ident$(,)?)*], [$($e_name:ident$(($($i_name:ty$(,)?)*))?$(,)?)*]) => {
717 tiles!($name, [$($char => $v_name,)*], [$($e_name$(($($i_name,)*))?,)*], |c| { panic!("Invalid tile {c}") });
718 };
719
720 ($name:ident, [$($char:pat => $v_name:ident$(,)?)*], [$($e_name:ident$(($($i_name:ty$(,)?)*))?$(,)?)*], $default:expr) => {
721 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
722 pub enum $name {
723 $($v_name,)*
724 $($e_name$(($($i_name,)*))?,)*
725 }
726
727 impl From<char> for $name {
728 fn from(c: char) -> Self {
729 match c {
730 $($char => Self::$v_name,)*
731 _ => ($default)(c),
732 }
733 }
734 }
735 };
736 }
737
738 /// Simple tile that holds a number value.
739 pub struct NumberTile {
740 pub value: isize,
741 }
742
743 impl From<char> for NumberTile {
744 fn from(c: char) -> Self {
745 Self {
746 value: c.to_digit(10).unwrap() as isize,
747 }
748 }
749 }
750
751 /// A tile that represents some kind of movement to another position in the grid.
752 pub trait DirectedTile<T: Movement>: Copy + Clone {
753 /// Get the next direction from the previous direction and position.
754 fn next_dir(&self, previous_dir: T, pos: Position) -> Option<T>;
755
756 /// Get the next position and position from the previous direction and position.
757 fn next_pos(&self, previous_dir: T, pos: Position) -> Option<(T, Position)> {
758 self.next_dir(previous_dir, pos)
759 .map(|d| (d, pos.move_dir(d)))
760 }
761 }
762
763 /// A tile that can be used in a flood fill.
764 pub trait FillableTile: Copy + Clone {
765 /// Check if the tile can be filled.
766 fn get_next_tiles(&self, pos: Position, grid: &Grid<Self>) -> Vec<Position>;
767 }
768}
769
770/// Utilities for traversing a grid.
771pub mod cursors {
772
773 use std::{
774 collections::{HashSet, VecDeque},
775 hash::Hasher,
776 };
777
778 use super::{
779 tiles::{DirectedTile, FillableTile},
780 *,
781 };
782
783 #[derive(Clone, Copy)]
784 /// A cursor for traversing a grid.
785 ///
786 /// This cursor holds a position and a direction which represents the current position in the grid.
787 ///
788 /// # Examples
789 ///
790 /// ```
791 /// use utils::prelude::*;
792 ///
793 /// let data = vec![
794 /// vec![1, 2, 3],
795 /// vec![4, 5, 6],
796 /// vec![7, 8, 9],
797 /// ];
798 ///
799 /// let grid = Grid::new(data);
800 ///
801 /// let mut cursor = GridCursor::zero(&grid);
802 ///
803 /// assert_eq!(cursor.get(), Some(&1));
804 /// cursor.move_forward();
805 /// assert_eq!(cursor.get(), Some(&2));
806 /// cursor.turn(true);
807 /// cursor.move_forward();
808 /// assert_eq!(cursor.get(), Some(&5));
809 /// ```
810 ///
811 pub struct GridCursor<'a, T, D: Movement> {
812 grid: &'a Grid<T>,
813 pub pos: Position,
814 pub dir: D,
815 }
816
817 impl<'a, T> GridCursor<'a, T, Direction> {
818 /// Create a new cursor at position (0, 0) facing east.
819 pub fn zero(grid: &'a Grid<T>) -> Self {
820 Self {
821 grid,
822 pos: Position::new(0, 0),
823 dir: Direction::East,
824 }
825 }
826
827 /// Turn the cursor 90 degrees clockwise or counter-clockwise.
828 pub fn turn(&mut self, clockwise: bool) {
829 self.dir = self.dir.ninety_deg(clockwise);
830 }
831
832 /// Turn the cursor 180 degrees.
833 pub fn turn_around(&mut self) {
834 self.dir = self.dir.opposite();
835 }
836 }
837
838 impl<T, D: Movement> PartialEq for GridCursor<'_, T, D> {
839 fn eq(&self, other: &Self) -> bool {
840 self.pos == other.pos && self.dir == other.dir
841 }
842 }
843
844 impl<T, D: Movement> std::hash::Hash for GridCursor<'_, T, D> {
845 fn hash<H: Hasher>(&self, state: &mut H) {
846 self.pos.hash(state);
847 self.dir.hash(state);
848 }
849 }
850
851 impl<'a, T, D: Movement> GridCursor<'a, T, D> {
852 /// Create a new cursor at the given position and direction.
853 pub fn new(grid: &'a Grid<T>, pos: Position, dir: D) -> Self {
854 Self { grid, pos, dir }
855 }
856
857 /// Get the current state of the cursor (position and direction) for use in tracking
858 pub fn state(&self) -> (Position, D) {
859 (self.pos, self.dir)
860 }
861
862 /// Move the cursor forward one step in the direction it is facing.
863 pub fn move_forward(&mut self) {
864 self.pos = self.pos.move_dir(self.dir);
865 }
866
867 /// See what tile (if any) the cursor will go to if it would move forward
868 pub fn peek_forward(&self) -> Option<(Position, &T)> {
869 let next_pos = self.pos.move_dir(self.dir);
870 self.grid.get(next_pos).map(|value| (next_pos, value))
871 }
872
873 /// Get the value at the current position of the cursor.
874 pub fn get(&self) -> Option<&T> {
875 self.grid.get(self.pos)
876 }
877
878 /// Move the cursor forward one step in the direction it is facing and get the value at the new position.
879 pub fn advance_get(&mut self) -> Option<&T> {
880 self.move_forward();
881 self.get()
882 }
883 }
884
885 impl<T: std::fmt::Debug, D: Movement> std::fmt::Debug for GridCursor<'_, T, D> {
886 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
887 f.debug_struct("GridCursor")
888 .field("pos", &self.pos)
889 .field("dir", &self.dir)
890 .field("value", &self.get())
891 .finish()
892 }
893 }
894
895 /// A cursor for traversing a grid with a direction.
896 ///
897 /// This cursor will follow the direction of the tile it is currently on.
898 ///
899 /// # Examples
900 ///
901 /// ```
902 /// use utils::prelude::*;
903 /// use utils::tiles;
904 ///
905 /// tiles!(Tile, [
906 /// '>' => Right,
907 /// '<' => Left,
908 /// '^' => Up,
909 /// 'v' => Down,
910 /// ]);
911 ///
912 /// impl DirectedTile<Direction> for Tile {
913 /// fn next_dir(&self, previous_dir: Direction, pos: Position) -> Option<Direction> {
914 /// match self {
915 /// Tile::Right => Some(Direction::East),
916 /// Tile::Left => Some(Direction::West),
917 /// Tile::Up => Some(Direction::North),
918 /// Tile::Down => Some(Direction::South),
919 /// _ => None,
920 /// }
921 /// }
922 /// }
923 ///
924 /// let data = vec![
925 /// vec![Tile::Right, Tile::Right, Tile::Down],
926 /// vec![Tile::Up, Tile::Left, Tile::Down],
927 /// vec![Tile::Up, Tile::Left, Tile::Left],
928 /// ];
929 ///
930 /// let grid = Grid::new(data);
931 ///
932 /// let mut cursor = DirectedCursor::new(&grid, Position::new(0, 0), Direction::East);
933 ///
934 /// let path = cursor.map(|(p, _, _)| p).take(8).collect::<Vec<_>>();
935 ///
936 /// assert_eq!(path, vec![
937 /// Position::new(1, 0),
938 /// Position::new(2, 0),
939 /// Position::new(2, 1),
940 /// Position::new(2, 2),
941 /// Position::new(1, 2),
942 /// Position::new(0, 2),
943 /// Position::new(0, 1),
944 /// Position::new(0, 0),
945 /// ]);
946 /// ```
947 ///
948 pub struct DirectedCursor<'a, T: DirectedTile<D>, D: Movement>(GridCursor<'a, T, D>);
949
950 impl<'a, T: DirectedTile<D>, D: Movement> DirectedCursor<'a, T, D> {
951 /// Create a new cursor at the given position and direction.
952 /// Note this starting position will *not* be included in the iterator.
953 pub fn new(grid: &'a Grid<T>, pos: Position, dir: D) -> Self {
954 let initial_cursor = GridCursor::new(grid, pos, dir);
955 Self(initial_cursor)
956 }
957 }
958
959 impl<T: DirectedTile<D>, D: Movement> Iterator for DirectedCursor<'_, T, D> {
960 type Item = (Position, D, T);
961
962 fn next(&mut self) -> Option<Self::Item> {
963 let current_val = self.0.get().cloned();
964 current_val.and_then(|tile| {
965 tile.next_pos(self.0.dir, self.0.pos).map(|(dir, pos)| {
966 self.0.dir = dir;
967 self.0.pos = pos;
968 (self.0.pos, self.0.dir, tile)
969 })
970 })
971 }
972 }
973
974 /// A cursor that flood fills a grid.
975 ///
976 /// This cursor will flood fill the grid from the given position,
977 /// using [FillableTile::get_next_tiles] to determine which tiles to fill.
978 ///
979 /// Setting `wrapped` to true will make the cursor wrap around the grid if necessary.
980 /// Note this can lead to infinite loops if you don't have something to stop the iterator.
981 ///
982 /// # Examples
983 ///
984 /// ```
985 /// use utils::prelude::*;
986 /// use utils::tiles;
987 ///
988 /// tiles!(Tile, [
989 /// '.' => Floor,
990 /// '#' => Wall,
991 /// ]);
992 ///
993 /// impl FillableTile for Tile {
994 /// fn get_next_tiles(&self, pos: Position, grid: &Grid<Self>) -> Vec<Position> {
995 /// match self {
996 /// Tile::Floor => grid.adjacent(pos).filter(|(_, _, t)| t == &&Tile::Floor).map(|(_, p, _)| p).collect(),
997 /// _ => vec![],
998 /// }
999 /// }
1000 /// }
1001 ///
1002 /// let data = vec![
1003 /// vec![Tile::Floor, Tile::Floor, Tile::Floor],
1004 /// vec![Tile::Floor, Tile::Wall, Tile::Floor],
1005 /// vec![Tile::Floor, Tile::Floor, Tile::Wall],
1006 /// ];
1007 ///
1008 /// let grid = Grid::new(data);
1009 ///
1010 /// let mut cursor = FloodFillCursor::new(&grid, Position::new(0, 0), true);
1011 ///
1012 /// let path = cursor.collect::<Vec<_>>();
1013 ///
1014 /// assert_eq!(path, vec![
1015 /// Position::new(0, 0),
1016 /// Position::new(0, 1),
1017 /// Position::new(1, 0),
1018 /// Position::new(0, 2),
1019 /// Position::new(2, 0),
1020 /// Position::new(1, 2),
1021 /// Position::new(2, 1),
1022 /// ]);
1023 /// ```
1024 ///
1025 pub struct FloodFillCursor<'a, T: FillableTile> {
1026 grid: &'a Grid<T>,
1027 visited: HashSet<Position>,
1028 queue: VecDeque<Position>,
1029 wrapped: bool,
1030 }
1031
1032 impl<'a, T: FillableTile> FloodFillCursor<'a, T> {
1033 /// Create a new cursor at the given position.
1034 pub fn new(grid: &'a Grid<T>, pos: Position, wrapped: bool) -> Self {
1035 let mut visited = HashSet::new();
1036 visited.insert(pos);
1037 let mut queue = VecDeque::new();
1038 queue.push_back(pos);
1039 Self {
1040 grid,
1041 visited,
1042 queue,
1043 wrapped,
1044 }
1045 }
1046 }
1047
1048 impl<T: FillableTile> std::fmt::Debug for FloodFillCursor<'_, T> {
1049 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1050 f.debug_struct("FloodFillCursor")
1051 .field("visited", &self.visited)
1052 .field("queue", &self.queue)
1053 .finish()
1054 }
1055 }
1056
1057 impl<T: FillableTile> Iterator for FloodFillCursor<'_, T> {
1058 type Item = Position;
1059
1060 fn next(&mut self) -> Option<Self::Item> {
1061 let pos = self.queue.pop_front()?;
1062 let tile = if self.wrapped {
1063 self.grid.get_wrapped(pos)
1064 } else {
1065 self.grid.get(pos)?
1066 };
1067 for next_pos in tile.get_next_tiles(pos, self.grid) {
1068 if self.visited.insert(next_pos) {
1069 self.queue.push_back(next_pos);
1070 }
1071 }
1072 Some(pos)
1073 }
1074 }
1075}