utils/
grid.rs

1//! Grid helpers.
2
3use crate::input::InputError;
4
5/// Parse 2D grid.
6///
7/// This function assumes that one byte represents each item in the grid.
8///
9/// Returns (number of rows, number of columns, data) on success.
10///
11/// # Examples
12///
13/// ```
14/// # use utils::grid::from_str;
15/// assert_eq!(
16///     from_str("##.#\n#..#\n#.##", |c| match c {
17///         b'#' => Some(true),
18///         b'.' => Some(false),
19///         _ => None,
20///     }).unwrap(),
21///     (3, 4, vec![
22///         true, true, false, true,
23///         true, false, false, true,
24///         true, false, true, true,
25///     ]),
26/// );
27/// ```
28pub fn from_str<T>(
29    input: &str,
30    mut func: impl FnMut(u8) -> Option<T>,
31) -> Result<(usize, usize, Vec<T>), InputError> {
32    let mut data = Vec::with_capacity(input.len());
33    let mut lines = input.lines().peekable();
34
35    let Some(&first_line) = lines.peek() else {
36        return Err(InputError::new(input, input, "expected grid"));
37    };
38
39    let columns = first_line.len().max(1);
40    for line in lines {
41        if line.len() != columns {
42            return Err(InputError::new(
43                input,
44                line,
45                format!("expected {columns} column(s)"),
46            ));
47        }
48
49        for b in line.bytes() {
50            if let Some(v) = func(b) {
51                data.push(v);
52            } else {
53                return Err(InputError::new(input, b as char, "invalid character"));
54            }
55        }
56    }
57
58    let rows = data.len() / columns;
59    debug_assert_eq!(rows * columns, data.len());
60
61    Ok((rows, columns, data))
62}
63
64/// Parse 2D grid, adding padding around the edges.
65///
66/// Similar to [`from_str`], but pads the edges of the parsed grid with `padding` rows and columns
67/// filled with the default value. This is helpful to avoid bounds checks when considering a
68/// location's neighbors.
69///
70/// Returns (number of rows, number of columns, data) on success (row and column counts include
71/// the added padding).
72///
73/// # Examples
74///
75/// ```
76/// # use utils::grid::from_str_padded;
77/// assert_eq!(
78///     from_str_padded("##.#\n#..#\n#.##", 2, false, |c| match c {
79///         b'#' => Some(true),
80///         b'.' => Some(false),
81///         _ => None,
82///     }).unwrap(),
83///     (7, 8, vec![
84///         false, false, false, false, false, false, false, false,
85///         false, false, false, false, false, false, false, false,
86///         false, false, true, true, false, true, false, false,
87///         false, false, true, false, false, true, false, false,
88///         false, false, true, false, true, true, false, false,
89///         false, false, false, false, false, false, false, false,
90///         false, false, false, false, false, false, false, false,
91///     ]),
92/// );
93/// ```
94pub fn from_str_padded<T: Clone>(
95    input: &str,
96    padding: usize,
97    padding_value: T,
98    mut func: impl FnMut(u8) -> Option<T>,
99) -> Result<(usize, usize, Vec<T>), InputError> {
100    let mut data = Vec::with_capacity(input.len());
101    let mut lines = input.lines().peekable();
102
103    let Some(&first_line) = lines.peek() else {
104        return Err(InputError::new(input, input, "expected grid"));
105    };
106
107    let columns = first_line.len().max(1);
108    let padded_columns = columns + 2 * padding;
109
110    // Add initial padding rows + padding for start of first actual row
111    data.resize(padded_columns * padding + padding, padding_value.clone());
112
113    for line in lines {
114        if line.len() != columns {
115            return Err(InputError::new(
116                input,
117                line,
118                format!("expected {columns} column(s)"),
119            ));
120        }
121
122        for b in line.bytes() {
123            if let Some(v) = func(b) {
124                data.push(v);
125            } else {
126                return Err(InputError::new(input, b as char, "invalid character"));
127            }
128        }
129
130        // Add padding for the end of the current row, and the start of the next row
131        data.resize(data.len() + 2 * padding, padding_value.clone());
132    }
133
134    // Add final padding rows, minus the already added padding for the start of a row
135    data.resize(
136        data.len() + padded_columns * padding - padding,
137        padding_value,
138    );
139
140    let rows = data.len() / padded_columns;
141    debug_assert_eq!(rows * padded_columns, data.len());
142
143    Ok((rows, padded_columns, data))
144}
145
146/// Checks that the provided grid has walls on each edge.
147///
148/// # Examples
149/// ```
150/// # use utils::grid::is_enclosed;
151/// assert_eq!(
152///     is_enclosed(5, 6, &[
153///         b'#', b'#', b'#', b'#', b'#', b'#',
154///         b'#', b'.', b'.', b'.', b'.', b'#',
155///         b'#', b'.', b'.', b'.', b'.', b'#',
156///         b'#', b'.', b'.', b'.', b'.', b'#',
157///         b'#', b'#', b'#', b'#', b'#', b'#',
158///     ], |&b| b == b'#'),
159///     true,
160/// );
161/// assert_eq!(
162///     is_enclosed(5, 6, &[
163///         b'#', b'#', b'#', b'#', b'#', b'#',
164///         b'#', b'.', b'.', b'.', b'.', b'#',
165///         b'#', b'.', b'.', b'.', b'.', b'#',
166///         b'#', b'.', b'.', b'.', b'.', b'.',
167///         b'#', b'#', b'#', b'#', b'#', b'#',
168///     ], |&b| b == b'#'),
169///     false,
170/// );
171/// ```
172pub fn is_enclosed<T>(rows: usize, cols: usize, grid: &[T], is_wall: impl Fn(&T) -> bool) -> bool {
173    grid[..cols].iter().all(&is_wall)
174        && grid[(rows - 1) * cols..].iter().all(&is_wall)
175        && (1..rows).all(|r| is_wall(&grid[r * cols]) && is_wall(&grid[(r + 1) * cols - 1]))
176}
utils/grid.rs

utils/
grid.rs
