utils/
grid.rs

1//! Grid helpers.
2
3use crate::input::InputError;
4use std::error::Error;
5
6/// A parsed grid: `(number of rows, number of columns, data)`.
7pub type Grid<T> = (usize, usize, Vec<T>);
8
9/// Parse a 2D grid.
10///
11/// This function assumes that each byte represents one item in the grid.
12/// Using 1 byte wide output types is recommended to enable more efficient vectorization.
13///
14/// Parsing is done in two passes per line:
15///
16/// 1. A "hot" pass, where each byte is mapped to an output value and checked for validity.
17///    This uses the `hot_map` and `hot_valid` functions, which should be pure and total mappings
18///    from [`u8`] to their respective outputs to enable vectorization.
19///    Additionally, `hot_valid` must return false for both `'\r'` and `'\n'`.
20///
21/// 2. A "slow" pass, where any invalid bytes from the first pass are re-processed with their index
22///    in the final grid.
23///    This uses the `slow_map` function which returns a [`Result`], containing either a mapped
24///    value or an error.
25///    `slow_map` can be used to perform more complex, non-pure, mappings such as storing positions
26///    and will never be called for newlines or bytes that were valid in the first pass.
27///    If all the bytes were valid in the first pass, this pass is skipped.
28///
29/// `default_value` is used to initialize the grid before parsing and for any padding.
30/// A value with an all-zero bit pattern will usually faster to initialize and is recommended when
31/// padding is not used.
32///
33/// Returns (number of rows, number of columns, data) on success.
34///
35/// # Examples
36///
37/// ```
38/// # use utils::grid;
39/// assert_eq!(
40///     grid::parse(
41///         /* input         */ "##.#\n#..#\n#.##",
42///         /* padding       */ 0,
43///         /* default_value */ false,
44///         /* hot_map       */ |b| b == b'#',
45///         /* hot_valid     */ |b| matches!(b, b'.' | b'#'),
46///         /* slow_map      */ |_, _| Err("expected '.' or '#'"),
47///     ).unwrap(),
48///     (3, 4, vec![
49///         true, true, false, true,
50///         true, false, false, true,
51///         true, false, true, true,
52///     ]),
53/// );
54/// ```
55///
56///
57/// ```
58/// # use utils::grid;
59/// assert_eq!(
60///     grid::parse(
61///         /* input         */"##.#\n#..#\n#.##",
62///         /* padding       */ 2,
63///         /* default_value */ false,
64///         /* hot_map       */ |b| b == b'#',
65///         /* hot_valid     */ |b| matches!(b, b'.' | b'#'),
66///         /* slow_map      */ |_, _| Err("expected '.' or '#'"),
67///     ).unwrap(),
68///     (7, 8, vec![
69///         false, false, false, false, false, false, false, false,
70///         false, false, false, false, false, false, false, false,
71///         false, false, true, true, false, true, false, false,
72///         false, false, true, false, false, true, false, false,
73///         false, false, true, false, true, true, false, false,
74///         false, false, false, false, false, false, false, false,
75///         false, false, false, false, false, false, false, false,
76///     ]),
77/// );
78/// ```
79///
80/// ```
81/// # use utils::grid;
82/// let mut start = None;
83/// assert_eq!(
84///     grid::parse(
85///         /* input         */ ".0.#S\r\n..1..\r\n.###2\r\n.3...",
86///         /* padding       */ 1,
87///         /* default_value */ b'#',
88///         /* hot_map       */ |b| b,
89///         /* hot_valid     */ |b| matches!(b, b'.' | b'#' | b'0'..=b'9'),
90///         /* slow_map      */ |i, b| {
91///             match b {
92///                 b'S' if start.is_none() => {
93///                     start = Some(i);
94///                     Ok(b'.')
95///                 },
96///                 b'S' => Err("expected only one 'S'"),
97///                 _ => Err("expected '.', '#', 'S' or a digit")
98///             }
99///         },
100///     ).unwrap(),
101///     (6, 7, vec![
102///         b'#', b'#', b'#', b'#', b'#', b'#', b'#',
103///         b'#', b'.', b'0', b'.', b'#', b'.', b'#',
104///         b'#', b'.', b'.', b'1', b'.', b'.', b'#',
105///         b'#', b'.', b'#', b'#', b'#', b'2', b'#',
106///         b'#', b'.', b'3', b'.', b'.', b'.', b'#',
107///         b'#', b'#', b'#', b'#', b'#', b'#', b'#',
108///     ]),
109/// );
110/// assert_eq!(start, Some(12));
111/// ```
112#[inline]
113pub fn parse<T: Clone, E: Into<Box<dyn Error>>>(
114    input: &str,
115    padding: usize,
116    default_value: T,
117    hot_map: impl Fn(u8) -> T,
118    hot_valid: impl Fn(u8) -> bool,
119    mut slow_map: impl FnMut(usize, u8) -> Result<T, E>,
120) -> Result<Grid<T>, InputError> {
121    assert!(!hot_valid(b'\n'));
122    assert!(!hot_valid(b'\r'));
123
124    // Line length including newline
125    let Some(line_length) = input
126        .bytes()
127        .position(|b| b == b'\n')
128        .map(|x| x + 1)
129        .filter(|&x| x >= 2)
130    else {
131        return Err(InputError::new(input, 0, "expected grid"));
132    };
133
134    let clrf_endings = input.as_bytes()[line_length - 2] == b'\r';
135    let newline_length = 1 + usize::from(clrf_endings);
136
137    // Add line_ending_length to account for the final newline which should have already been
138    // stripped by utils::input::strip_final_newline
139    if !(input.len() + newline_length).is_multiple_of(line_length) {
140        return Err(InputError::new(
141            input,
142            input.len(),
143            "expected input length to be a multiple of the first line length",
144        ));
145    }
146
147    let input_cols = line_length - newline_length;
148    let input_rows = (input.len() + newline_length) / line_length;
149
150    let padded_cols = input_cols + 2 * padding;
151    let padded_rows = input_rows + 2 * padding;
152
153    let mut data = vec![default_value; padded_cols * padded_rows];
154    for ((r, input_line), data_line) in input
155        .as_bytes()
156        .chunks(line_length)
157        .enumerate()
158        .zip(data.chunks_exact_mut(padded_cols).skip(padding))
159    {
160        // Hot pass
161        let mut valid = true;
162        for (&b, d) in input_line[..input_cols]
163            .iter()
164            .zip(data_line[padding..].iter_mut())
165        {
166            *d = hot_map(b);
167            valid &= hot_valid(b);
168        }
169
170        // Slow pass
171        if !valid {
172            for ((c, &b), d) in input_line[..input_cols]
173                .iter()
174                .enumerate()
175                .zip(data_line[padding..].iter_mut())
176            {
177                if hot_valid(b) {
178                    continue;
179                }
180                if b == b'\n' || b == b'\r' {
181                    return Err(InputError::new(
182                        input,
183                        &input_line[c..],
184                        format!("expected {input_cols} columns"),
185                    ));
186                }
187
188                let index = (r + padding) * padded_cols + padding + c;
189                match slow_map(index, b) {
190                    Ok(v) => *d = v,
191                    Err(err) => return Err(InputError::new(input, &input_line[c..], err)),
192                }
193            }
194        }
195
196        // Check input_line ends in the expected newline.
197        // Do this after the slow pass, so any earlier newlines earlier in the chunk have already
198        // been caught.
199        if r != input_rows - 1
200            && if clrf_endings {
201                input_line.last_chunk() != Some(b"\r\n")
202            } else {
203                input_line.last_chunk() != Some(b"\n")
204            }
205        {
206            return Err(InputError::new(
207                input,
208                &input_line[input_line.len() - 2..],
209                "expected newline",
210            ));
211        }
212    }
213
214    Ok((padded_rows, padded_cols, data))
215}
216
217/// Parse a "standard" maze with open tiles `.`, walls `#` and one start `S` and one end `E`.
218///
219/// Returns ((number of rows, number of columns, data), start index, end index) on success.
220///
221/// # Examples
222/// ```
223/// # use utils::grid;
224/// assert_eq!(
225///     grid::parse_maze("...#S\n.#E#.\n.###.\n.....", 1).unwrap(),
226///     (
227///         (6, 7, vec![
228///             b'#', b'#', b'#', b'#', b'#', b'#', b'#',
229///             b'#', b'.', b'.', b'.', b'#', b'.', b'#',
230///             b'#', b'.', b'#', b'.', b'#', b'.', b'#',
231///             b'#', b'.', b'#', b'#', b'#', b'.', b'#',
232///             b'#', b'.', b'.', b'.', b'.', b'.', b'#',
233///             b'#', b'#', b'#', b'#', b'#', b'#', b'#',
234///         ]),
235///         12,
236///         17,
237///     )
238/// );
239/// ```
240#[inline]
241pub fn parse_maze(input: &str, padding: usize) -> Result<(Grid<u8>, usize, usize), InputError> {
242    let mut start = None;
243    let mut end = None;
244    let grid = parse(
245        input,
246        padding,
247        if padding > 0 { b'#' } else { 0 },
248        |b| b,
249        |b| matches!(b, b'.' | b'#'),
250        |i, b| {
251            match b {
252                b'S' if start.is_none() => start = Some(i),
253                b'S' => return Err("expected one 'S'"),
254                b'E' if end.is_none() => end = Some(i),
255                b'E' => return Err("expected one 'E'"),
256                _ => return Err("expected '.', '#', 'S' or 'E'"),
257            }
258            Ok(b'.')
259        },
260    )?;
261    let Some(start) = start else {
262        return Err(InputError::new(input, 0, "expected one 'S'"));
263    };
264    let Some(end) = end else {
265        return Err(InputError::new(input, 0, "expected one 'E'"));
266    };
267    Ok((grid, start, end))
268}
269
270/// Checks that the provided grid has walls on each edge.
271///
272/// # Examples
273/// ```
274/// # use utils::grid::is_enclosed;
275/// assert_eq!(
276///     is_enclosed(5, 6, &[
277///         b'#', b'#', b'#', b'#', b'#', b'#',
278///         b'#', b'.', b'.', b'.', b'.', b'#',
279///         b'#', b'.', b'.', b'.', b'.', b'#',
280///         b'#', b'.', b'.', b'.', b'.', b'#',
281///         b'#', b'#', b'#', b'#', b'#', b'#',
282///     ], |&b| b == b'#'),
283///     true,
284/// );
285/// assert_eq!(
286///     is_enclosed(5, 6, &[
287///         b'#', b'#', b'#', b'#', b'#', b'#',
288///         b'#', b'.', b'.', b'.', b'.', b'#',
289///         b'#', b'.', b'.', b'.', b'.', b'#',
290///         b'#', b'.', b'.', b'.', b'.', b'.',
291///         b'#', b'#', b'#', b'#', b'#', b'#',
292///     ], |&b| b == b'#'),
293///     false,
294/// );
295/// ```
296pub fn is_enclosed<T>(rows: usize, cols: usize, grid: &[T], is_wall: impl Fn(&T) -> bool) -> bool {
297    grid[..cols].iter().all(&is_wall)
298        && grid[(rows - 1) * cols..].iter().all(&is_wall)
299        && (1..rows).all(|r| is_wall(&grid[r * cols]) && is_wall(&grid[(r + 1) * cols - 1]))
300}
utils/grid.rs

utils/
grid.rs
