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