bwc9876.dev
Advent of Code solutions
1/// Position utilities
2use std::{
3 fmt::{Debug, Display},
4 ops::{Add, Mul, Neg, Sub},
5 str::FromStr,
6};
7
8use crate::dir::{Direction, Movement, CARDINALS};
9
10type CompType = isize;
11type PositiveType = (usize, usize);
12
13#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
14/// A position in 2D space on an integer grid
15/// This is meant to represent indices of a 2D array, so north is negative y
16///
17/// This is also used to represent a vector in 2D space at times
18pub struct Position {
19 pub x: CompType,
20 pub y: CompType,
21}
22
23#[macro_export]
24macro_rules! ipos {
25 ($x:expr, $y:expr) => {
26 $crate::pos::Position::new($x, $y)
27 };
28}
29
30#[macro_export]
31macro_rules! upos {
32 ($x:expr, $y:expr) => {
33 $crate::ipos!($x as isize, $y as isize)
34 };
35}
36
37#[macro_export]
38macro_rules! kern {
39
40 (@builtin N) => { $crate::dir::ALL_8[0] };
41 (@builtin S) => { $crate::dir::ALL_8[1] };
42 (@builtin E) => { $crate::dir::ALL_8[2] };
43 (@builtin W) => { $crate::dir::ALL_8[3] };
44 (@builtin SE) => { $crate::dir::ALL_8[4] };
45 (@builtin NE) => { $crate::dir::ALL_8[5] };
46 (@builtin SW) => { $crate::dir::ALL_8[6] };
47 (@builtin NW) => { $crate::dir::ALL_8[7] };
48
49 (@builtin ($x:expr, $y: expr)) => { $crate::pos::upos!($x, $y) };
50
51 [$($s:tt),*] => {
52 [$(kern!(@builtin $s),)*]
53 };
54}
55
56impl Position {
57 /// Create a new position
58 pub const fn new(x: CompType, y: CompType) -> Self {
59 Self { x, y }
60 }
61
62 /// Create a new position at 0, 0
63 pub const fn zero() -> Self {
64 Self { x: 0, y: 0 }
65 }
66
67 /// Create the unit vector position
68 pub fn one() -> Self {
69 Self { x: 1, y: 1 }
70 }
71
72 /// Get the position flipped over the line y = x
73 ///
74 /// # Examples
75 ///
76 /// ```
77 /// use utils::prelude::*;
78 ///
79 /// let flipped = Position::new(1, 2).flip();
80 /// assert_eq!(flipped, Position::new(2, 1));
81 /// ```
82 ///
83 pub fn flip(&self) -> Self {
84 Self {
85 x: self.y,
86 y: self.x,
87 }
88 }
89
90 /// Normalize a position to a unit vector
91 ///
92 /// # Examples
93 ///
94 /// ```
95 /// use utils::prelude::*;
96 ///
97 /// let normalized = Position::new(1, 1).normalize();
98 /// assert_eq!(normalized, Position::new(1, 1));
99 ///
100 /// let normalized = Position::new(50, -45).normalize();
101 /// assert_eq!(normalized, Position::new(1, -1));
102 ///
103 /// let normalized = Position::new(-30, 0).normalize();
104 /// assert_eq!(normalized, Position::new(-1, 0));
105 /// ```
106 ///
107 pub fn normalize(&self) -> Self {
108 Self {
109 x: self.x.signum(),
110 y: self.y.signum(),
111 }
112 }
113
114 /// Get the magnitude of a position
115 ///
116 /// # Examples
117 ///
118 /// ```
119 /// use utils::prelude::*;
120 ///
121 /// let mag = Position::new(0, 1).magnitude();
122 /// assert_eq!(mag, 1.0);
123 ///
124 /// let mag = Position::new(3, 4).magnitude();
125 /// assert_eq!(mag, 5.0);
126 /// ```
127 ///
128 pub fn magnitude(&self) -> f64 {
129 (((self.x * self.x) + (self.y * self.y)) as f64).sqrt()
130 }
131
132 /// Get the absolute value of a position
133 ///
134 /// # Examples
135 ///
136 /// ```
137 /// use utils::prelude::*;
138 ///
139 /// let abs = Position::new(-1, -1).abs();
140 /// assert_eq!(abs, Position::new(1, 1));
141 /// ```
142 ///
143 pub fn abs(&self) -> Self {
144 Self {
145 x: self.x.abs(),
146 y: self.y.abs(),
147 }
148 }
149
150 /// Sum the components of a position
151 ///
152 /// # Examples
153 ///
154 /// ```
155 /// use utils::prelude::*;
156 ///
157 /// let sum = Position::new(1, 1).sum();
158 /// assert_eq!(sum, 2);
159 /// ```
160 ///
161 pub fn sum(&self) -> CompType {
162 self.x + self.y
163 }
164
165 /// Get the difference between the components of a position
166 ///
167 /// # Examples
168 ///
169 /// ```
170 /// use utils::prelude::*;
171 ///
172 /// let diff = Position::new(1, 1).diff();
173 /// assert_eq!(diff, 0);
174 /// ```
175 ///
176 pub fn diff(&self) -> CompType {
177 self.x - self.y
178 }
179
180 /// Get the direction of one position relative to another
181 ///
182 /// This is the direction that the second position is from the first
183 ///
184 /// Meaning
185 ///
186 /// ```txt
187 /// ...
188 /// A.B
189 /// ...
190 ///
191 /// A.get_dir(B) == Direction::East
192 /// and
193 /// B.get_dir(A) == Direction::West
194 /// ```
195 ///
196 /// # Panics
197 ///
198 /// If the positions are the same or diagonal from each other
199 ///
200 /// # Examples
201 ///
202 /// ```
203 /// use utils::prelude::*;
204 ///
205 /// let dir = Position::new(1, 1).get_dir(&Position::new(5, 1));
206 /// assert_eq!(dir, Direction::East);
207 ///
208 /// let dir = Position::new(5, 1).get_dir(&Position::new(1, 1));
209 /// assert_eq!(dir, Direction::West);
210 ///
211 /// let dir = Position::new(1, 1).get_dir(&Position::new(1, 5));
212 /// assert_eq!(dir, Direction::South);
213 /// ```
214 ///
215 pub fn get_dir(&self, other: &Self) -> Direction {
216 other.sub(self).normalize().into()
217 }
218
219 /// Add two positions together
220 ///
221 /// # Examples
222 ///
223 /// ```
224 /// use utils::prelude::*;
225 ///
226 /// let sum = Position::new(1, 1).add(&Position::new(5, 4));
227 /// assert_eq!(sum, Position::new(6, 5));
228 /// ```
229 ///
230 pub fn add(&self, other: &Self) -> Self {
231 Self {
232 x: self.x + other.x,
233 y: self.y + other.y,
234 }
235 }
236
237 /// Get the difference between two positions
238 ///
239 /// # Examples
240 ///
241 /// ```
242 /// use utils::prelude::*;
243 ///
244 /// let diff = Position::new(1, 1).sub(&Position::new(5, 5));
245 /// assert_eq!(diff, Position::new(-4, -4));
246 /// ```
247 ///
248 pub fn sub(&self, other: &Self) -> Self {
249 Self {
250 x: self.x - other.x,
251 y: self.y - other.y,
252 }
253 }
254
255 /// Multiply two positions together
256 ///
257 /// # Examples
258 ///
259 /// ```
260 /// use utils::prelude::*;
261 ///
262 /// let multiplied = Position::new(1, 1).multiply(&Position::new(5, 4));
263 /// assert_eq!(multiplied, Position::new(5, 4));
264 /// ```
265 ///
266 pub fn multiply(&self, other: &Self) -> Self {
267 Self {
268 x: self.x * other.x,
269 y: self.y * other.y,
270 }
271 }
272
273 /// Get the dot product of two positions
274 ///
275 /// x1 * x2 + y1 * y2
276 ///
277 /// # Examples
278 ///
279 /// ```
280 /// use utils::prelude::*;
281 ///
282 /// let dot = Position::new(1, 1).dot(&Position::new(5, 4));
283 /// assert_eq!(dot, 9);
284 /// ```
285 ///
286 pub fn dot(&self, other: &Self) -> CompType {
287 self.multiply(other).sum()
288 }
289
290 /// Get the angle between two positions
291 ///
292 /// # Examples
293 ///
294 /// ```
295 /// use utils::prelude::*;
296 ///
297 /// let angle = Position::new(0, 1).angle(&Position::new(1, 0));
298 ///
299 /// assert_eq!(angle, std::f64::consts::FRAC_PI_2);
300 /// ```
301 ///
302 pub fn angle(&self, other: &Self) -> f64 {
303 let dot = self.dot(other) as f64;
304 let mag = self.magnitude() * other.magnitude();
305 (dot / mag).acos()
306 }
307
308 /// Get the cross product of two positions
309 ///
310 /// x1 * y2 - y1 * x2
311 ///
312 /// # Examples
313 ///
314 /// ```
315 /// use utils::prelude::*;
316 ///
317 /// let cross = Position::new(2, 3).cross(&Position::new(5, 4));
318 /// assert_eq!(cross, -7);
319 /// ```
320 ///
321 pub fn cross(&self, other: &Self) -> CompType {
322 self.multiply(&other.flip()).diff()
323 }
324
325 /// Multiply a position by a scalar
326 ///
327 /// # Examples
328 ///
329 /// ```
330 /// use utils::prelude::*;
331 ///
332 /// let multiplied = Position::new(1, 1).multiply_comp(5);
333 /// assert_eq!(multiplied, Position::new(5, 5));
334 /// ```
335 ///
336 pub fn multiply_comp(&self, other: CompType) -> Self {
337 Self {
338 x: self.x * other,
339 y: self.y * other,
340 }
341 }
342
343 /// Get the manhattan distance between two positions
344 ///
345 /// # Examples
346 ///
347 /// ```
348 /// use utils::prelude::*;
349 ///
350 /// let distance = Position::new(1, 1).manhattan(&Position::new(5, 5));
351 /// assert_eq!(distance, 8);
352 /// ```
353 ///
354 pub fn manhattan(&self, other: &Self) -> CompType {
355 self.sub(other).abs().sum()
356 }
357
358 /// Get the chebyshev distance between two positions
359 ///
360 /// # Examples
361 ///
362 /// ```
363 /// use utils::prelude::*;
364 ///
365 /// let distance = Position::new(1, 1).chebyshev(&Position::new(5, 5));
366 /// assert_eq!(distance, 4);
367 /// ```
368 ///
369 pub fn chebyshev(&self, other: &Self) -> CompType {
370 let diff = self.sub(other).abs();
371 diff.x.max(diff.y)
372 }
373
374 /// Check if a component is within a range of 0..bound
375 /// Note bound is exclusive
376 fn check_comp(comp: CompType, bound: usize) -> bool {
377 (0..(bound as isize)).contains(&comp)
378 }
379
380 /// Check if a position is within a range of (0..bound.0, 0..bound.1)
381 /// Note bound is exclusive
382 ///
383 /// # Examples
384 ///
385 /// ```
386 /// use utils::prelude::*;
387 ///
388 /// let checked = Position::new(0, 0).check((10, 10));
389 /// assert!(checked);
390 ///
391 /// let checked = Position::new(50, 50).check((5, 5));
392 /// assert_eq!(checked, false);
393 /// ```
394 ///
395 pub fn check(&self, bounds: PositiveType) -> bool {
396 Self::check_comp(self.x, bounds.0) && Self::check_comp(self.y, bounds.1)
397 }
398
399 /// Normalize a value to be within a range of 0..bound
400 /// Note bound is exclusive
401 ///
402 /// # Examples
403 ///
404 /// ```
405 /// use utils::prelude::*;
406 ///
407 /// let normalized = Position::bind_comp(-1, 10);
408 /// assert_eq!(normalized, 9);
409 ///
410 /// let normalized = Position::bind_comp(-10, 5);
411 /// assert_eq!(normalized, 0);
412 ///
413 /// let normalized = Position::bind_comp(10, 5);
414 /// assert_eq!(normalized, 0);
415 ///
416 /// let normalized = Position::bind_comp(3, 6);
417 /// assert_eq!(normalized, 3);
418 /// ```
419 ///
420 pub fn bind_comp(comp: CompType, bound: usize) -> usize {
421 let bound = bound as isize;
422 if comp >= bound || comp.is_negative() {
423 let ans = comp % bound;
424 if ans.is_negative() {
425 (ans + bound) as usize
426 } else {
427 ans as usize
428 }
429 } else {
430 comp as usize
431 }
432 }
433
434 /// Bind a position to be within ranges of (0..bound.0, 0..bound.1)
435 /// Note bound is exclusive
436 ///
437 /// # Examples
438 ///
439 /// ```
440 /// use utils::prelude::*;
441 ///
442 /// let bound = Position::new(-1, -1).bind((11, 11));
443 /// assert_eq!(bound, (10, 10));
444 ///
445 /// let bound = Position::new(-10, -10).bind((6, 6));
446 /// assert_eq!(bound, (2, 2));
447 ///
448 /// let bound = Position::new(10, 10).bind((6, 6));
449 /// assert_eq!(bound, (4, 4));
450 /// ```
451 ///
452 pub fn bind(&self, bounds: PositiveType) -> PositiveType {
453 (
454 Self::bind_comp(self.x, bounds.0),
455 Self::bind_comp(self.y, bounds.1),
456 )
457 }
458
459 /// Move a position by direction
460 ///
461 /// # Examples
462 ///
463 /// ```
464 /// use utils::prelude::*;
465 ///
466 /// let moved = Position::new(0, 0).move_dir(Direction::North);
467 /// assert_eq!(moved, Position::new(0, -1));
468 ///
469 /// let moved = Position::new(0, 0).move_dir(Direction::East);
470 /// assert_eq!(moved, Position::new(1, 0));
471 /// ```
472 ///
473 pub fn move_dir(&self, dir: impl Movement) -> Self {
474 self.add(&dir.get_kernel())
475 }
476
477 /// Move a position by direction a certain number of times
478 ///
479 /// # Examples
480 ///
481 /// ```
482 /// use utils::prelude::*;
483 ///
484 /// let moved = Position::new(0, 0).move_times(Direction::North, 5);
485 /// assert_eq!(moved, Position::new(0, -5));
486 /// ```
487 ///
488 pub fn move_times(&self, dir: impl Movement, times: usize) -> Self {
489 self.add(&dir.get_kernel().multiply_comp(times as isize))
490 }
491
492 /// Move a position by direction,
493 /// checking if it is within a range of (0..bound.0, 0..bound.1)
494 ///
495 /// # Returns
496 ///
497 /// * `Some(Position)` if the new position is within the bounds
498 /// * `None` if the new position is outside the bounds
499 ///
500 /// # Examples
501 ///
502 /// ```
503 /// use utils::prelude::*;
504 ///
505 /// let moved = Position::new(0, 0).move_dir_checked(Direction::East, (10, 10));
506 /// assert_eq!(moved.unwrap(), Position::new(1, 0));
507 ///
508 /// let moved = Position::new(40, 40).move_dir_checked(Direction::East, (40, 40));
509 /// assert!(moved.is_none());
510 /// ```
511 ///
512 pub fn move_dir_checked(&self, dir: impl Movement, bounds: PositiveType) -> Option<Self> {
513 let new = self.move_dir(dir);
514 if new.check(bounds) {
515 Some(new)
516 } else {
517 None
518 }
519 }
520
521 /// Move a position by direction a certain number of times,
522 /// checking if it is within a range of (0..bound.0, 0..bound.1)
523 ///
524 /// # Returns
525 ///
526 /// * `Some(Position)` if the new position is within the bounds
527 /// * `None` if the new position is outside the bounds
528 ///
529 pub fn move_times_checked(
530 &self,
531 dir: impl Movement,
532 times: usize,
533 bounds: PositiveType,
534 ) -> Option<Self> {
535 let new = self.move_times(dir, times);
536 if new.check(bounds) {
537 Some(new)
538 } else {
539 None
540 }
541 }
542
543 /// Get all positions relative to this position by a list of directions
544 ///
545 /// # Examples
546 ///
547 /// ```
548 /// use utils::prelude::*;
549 ///
550 /// let relatives = Position::new(0, 0).relatives(&[Direction::North, Direction::East]).collect::<Vec<_>>();
551 /// assert_eq!(relatives, vec![(Position::new(0, -1), Direction::North), (Position::new(1, 0), Direction::East)]);
552 /// ```
553 ///
554 pub fn relatives<T: Movement>(self, kernels: &[T]) -> impl Iterator<Item = (Self, T)> + '_ {
555 kernels.iter().map(move |k| (self.move_dir(*k), *k))
556 }
557
558 /// Get all positions relative to this position by a list of directions,
559 /// checking if they are within a range of (0..bound.0, 0..bound.1)
560 ///
561 /// # Examples
562 ///
563 /// ```
564 /// use utils::prelude::*;
565 ///
566 /// let relatives = Position::new(0, 0).relatives_checked(&[Direction::North, Direction::East], (10, 10)).collect::<Vec<_>>();
567 /// assert_eq!(relatives, vec![(Position::new(1, 0), Direction::East)]);
568 /// ```
569 ///
570 pub fn relatives_checked<T: Movement>(
571 self,
572 kernels: &[T],
573 bounds: PositiveType,
574 ) -> impl Iterator<Item = (Self, T)> + '_ {
575 kernels
576 .iter()
577 .filter_map(move |k| self.move_dir_checked(*k, bounds).map(|p| (p, *k)))
578 }
579
580 /// Get all positions relative to this position by a list of directions,
581 /// repeating each direction a certain number of times
582 ///
583 /// # Examples
584 ///
585 /// ```
586 /// use utils::prelude::*;
587 ///
588 /// let relatives = Position::new(0, 0).relatives_expand_by(&[Direction::North, Direction::East], 2).collect::<Vec<_>>();
589 /// let expected = vec![
590 /// ((Direction::North, 1), Position::new(0, -1)),
591 /// ((Direction::North, 2), Position::new(0, -2)),
592 /// ((Direction::East, 1), Position::new(1, 0)),
593 /// ((Direction::East, 2), Position::new(2, 0)),
594 /// ];
595 ///
596 /// assert_eq!(relatives, expected);
597 /// ```
598 ///
599 pub fn relatives_expand_by<T: Movement>(
600 self,
601 kernels: &[T],
602 times: usize,
603 ) -> impl Iterator<Item = ((T, usize), Self)> + '_ {
604 kernels
605 .iter()
606 .flat_map(move |k| (1..=times).map(move |t| ((*k, t), self.move_times(*k, t))))
607 }
608
609 /// Get all positions relative to this position by a list of directions,
610 /// repeating each direction a certain number of times,
611 /// checking if they are within a range of (0..bound.0, 0..bound.1)
612 ///
613 /// # Examples
614 ///
615 /// ```
616 /// use utils::prelude::*;
617 ///
618 /// let relatives = Position::new(0, 0).relatives_expand_by_checked(&[Direction::North, Direction::East], 2, (10, 10)).collect::<Vec<_>>();
619 /// let expected = vec![
620 /// ((Direction::East, 1), Position::new(1, 0)),
621 /// ((Direction::East, 2), Position::new(2, 0)),
622 /// ];
623 ///
624 /// assert_eq!(relatives, expected);
625 /// ```
626 ///
627 pub fn relatives_expand_by_checked<T: Movement>(
628 self,
629 kernels: &[T],
630 times: usize,
631 bounds: PositiveType,
632 ) -> impl Iterator<Item = ((T, usize), Self)> + '_ {
633 kernels.iter().flat_map(move |k| {
634 (1..=times)
635 .filter_map(move |t| self.move_times_checked(*k, t, bounds).map(|p| ((*k, t), p)))
636 })
637 }
638
639 /// Get all positions adjacent to this position
640 ///
641 /// # Examples
642 ///
643 /// ```
644 /// use utils::prelude::*;
645 ///
646 /// let adjacents = Position::new(0, 0).adjacents().collect::<Vec<_>>();
647 /// let expected = vec![
648 /// (Position::new(0, -1), Direction::North),
649 /// (Position::new(0, 1), Direction::South),
650 /// (Position::new(1, 0), Direction::East),
651 /// (Position::new(-1, 0), Direction::West),
652 /// ];
653 ///
654 /// assert_eq!(adjacents, expected);
655 /// ```
656 ///
657 pub fn adjacents(self) -> impl Iterator<Item = (Self, Direction)> {
658 self.relatives(&CARDINALS)
659 }
660
661 /// Get all positions adjacent to this position
662 ///
663 /// # Examples
664 ///
665 /// ```
666 /// use utils::prelude::*;
667 ///
668 /// let adjacents = Position::new(0, 0).adjacents_checked((2, 2)).collect::<Vec<_>>();
669 /// let expected = vec![
670 /// (Position::new(0, 1), Direction::South),
671 /// (Position::new(1, 0), Direction::East),
672 /// ];
673 ///
674 /// assert_eq!(adjacents, expected);
675 /// ```
676 ///
677 pub fn adjacents_checked(
678 self,
679 bounds: PositiveType,
680 ) -> impl Iterator<Item = (Self, Direction)> {
681 self.relatives_checked(&CARDINALS, bounds)
682 }
683}
684
685impl Add for Position {
686 type Output = Self;
687
688 fn add(self, other: Self) -> Self {
689 Self::add(&self, &other)
690 }
691}
692
693impl Add<&Position> for Position {
694 type Output = Self;
695
696 fn add(self, other: &Self) -> Self {
697 Self::add(&self, other)
698 }
699}
700
701impl Sub for Position {
702 type Output = Self;
703
704 fn sub(self, other: Self) -> Self {
705 Self::sub(&self, &other)
706 }
707}
708
709impl Sub<&Position> for Position {
710 type Output = Self;
711
712 fn sub(self, other: &Self) -> Self {
713 Self::sub(&self, other)
714 }
715}
716
717impl Mul for Position {
718 type Output = Self;
719
720 fn mul(self, other: Self) -> Self {
721 Self::multiply(&self, &other)
722 }
723}
724
725impl Mul<&Position> for Position {
726 type Output = Self;
727
728 fn mul(self, other: &Self) -> Self {
729 Self::multiply(&self, other)
730 }
731}
732
733impl Mul<CompType> for Position {
734 type Output = Self;
735
736 fn mul(self, other: CompType) -> Self {
737 Self::multiply_comp(&self, other)
738 }
739}
740
741impl Mul<usize> for Position {
742 type Output = Self;
743
744 fn mul(self, other: usize) -> Self {
745 Self::multiply_comp(&self, other as isize)
746 }
747}
748
749impl Neg for Position {
750 type Output = Self;
751
752 fn neg(self) -> Self {
753 self.multiply_comp(-1)
754 }
755}
756
757impl Display for Position {
758 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
759 write!(f, "({},{})", self.x, self.y)
760 }
761}
762
763impl FromStr for Position {
764 type Err = String;
765
766 fn from_str(s: &str) -> Result<Self, Self::Err> {
767 let mut split = s.split(',');
768 let x = split.next().ok_or("No x")?.parse().expect("No x");
769 let y = split.next().ok_or("No y")?.parse().expect("No y");
770 Ok(Self { x, y })
771 }
772}
773
774impl From<(CompType, CompType)> for Position {
775 fn from((x, y): (CompType, CompType)) -> Self {
776 Self { x, y }
777 }
778}
779
780impl From<Position> for (CompType, CompType) {
781 fn from(val: Position) -> Self {
782 (val.x, val.y)
783 }
784}
785
786impl From<(usize, usize)> for Position {
787 fn from((x, y): (usize, usize)) -> Self {
788 Self {
789 x: x as isize,
790 y: y as isize,
791 }
792 }
793}
794
795impl From<Position> for (usize, usize) {
796 fn from(val: Position) -> Self {
797 (val.x as usize, val.y as usize)
798 }
799}
800
801impl From<Direction> for Position {
802 fn from(dir: Direction) -> Self {
803 dir.get_kernel()
804 }
805}
806
807impl Movement for Position {
808 fn get_kernel(&self) -> Position {
809 *self
810 }
811}