nove.dev
1use std::collections::BTreeSet;
2
3use itertools::Itertools;
4
5#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
6pub struct Point {
7 pub row: usize,
8 pub col: usize,
9}
10
11pub fn all_coords(width: usize, height: usize) -> impl Iterator<Item = Point> {
12 (0..height)
13 .cartesian_product(0..width)
14 .map(|(row, col)| Point { row, col })
15}
16
17///Never Eat Shredded Wheat
18pub fn adjacent_cardinal<T: Copy>(grid: &[Vec<T>], coords: Point) -> [Option<T>; 4] {
19 let mut retval = [const { None }; 4];
20 let (row, col) = (coords.row, coords.col);
21
22 if row > 0 {
23 retval[0] = Some(grid[row - 1][col]) //N
24 }
25 if col < grid[0].len() - 1 {
26 retval[1] = Some(grid[row][col + 1]) //E
27 }
28 if row < grid.len() - 1 {
29 retval[2] = Some(grid[row + 1][col]) //S
30 }
31 if col > 0 {
32 retval[3] = Some(grid[row][col - 1]) //N
33 }
34
35 retval
36}
37
38pub fn adjacent_cardinal_points<T: Copy>(grid: &[Vec<T>], coords: Point) -> Vec<Point> {
39 let mut retval = vec![];
40 let (row, col) = (coords.row, coords.col);
41
42 if row > 0 {
43 retval.push(Point { row: row - 1, col }) //N
44 }
45 if col < grid[0].len() - 1 {
46 retval.push(Point { row, col: col + 1 }) //E
47 }
48 if row < grid.len() - 1 {
49 retval.push(Point { row: row + 1, col }) //S
50 }
51 if col > 0 {
52 retval.push(Point { row, col: col - 1 }) //W
53 }
54
55 retval
56}
57
58//2d spatial digraph
59pub fn flood(digraph: &[Vec<Vec<Point>>], start: Point) -> BTreeSet<Point> {
60 let mut reachable = BTreeSet::new();
61 let mut frontier = BTreeSet::from_iter([start]);
62
63 while let Some(cursor) = frontier.pop_first() {
64 reachable.insert(cursor);
65 let next = BTreeSet::from_iter(digraph[cursor.row][cursor.col].iter().cloned());
66 for &point in next.difference(&reachable) {
67 frontier.insert(point);
68 }
69 }
70
71 reachable
72}
73
74//2d spatial dag
75pub fn paths_to_each_point(
76 digraph: &[Vec<Vec<Point>>],
77 start: Point,
78) -> Vec<Vec<BTreeSet<Vec<Point>>>> {
79 let mut paths_to_each_point = vec![vec![BTreeSet::new(); digraph.len()]; digraph[0].len()];
80 paths_to_each_point[start.row][start.col] = BTreeSet::from_iter([vec![start]]);
81 let mut frontier = BTreeSet::from_iter([start]);
82
83 while let Some(cursor) = frontier.pop_first() {
84 for point in &digraph[cursor.row][cursor.col] {
85 frontier.insert(*point);
86 let paths_to_new_point = paths_to_each_point[cursor.row][cursor.col].clone();
87 for mut path in paths_to_new_point {
88 path.push(*point);
89 paths_to_each_point[point.row][point.col].insert(path);
90 }
91 }
92 }
93
94 paths_to_each_point
95}