year2018/
day20.rs

1use utils::prelude::*;
2use utils::slice::merge_sorted_deduped_in_place;
3
4/// Following a regex’s branching paths within a grid.
5#[derive(Clone, Debug)]
6pub struct Day20 {
7    part1: u16,
8    part2: u16,
9}
10
11const WIDTH: usize = 109;
12
13impl Day20 {
14    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
15        if input.as_bytes().first() != Some(&b'^') {
16            return Err(InputError::new(input, 0, "expected '^'"));
17        }
18        if input.as_bytes().last() != Some(&b'$') {
19            return Err(InputError::new(input, input.len() - 1, "expected '$'"));
20        }
21
22        let mut grid = [0u16; WIDTH * WIDTH];
23        let mut positions = vec![(WIDTH * WIDTH) / 2];
24        let (mut start, mut end) = (Vec::new(), Vec::new());
25        let mut stack = Vec::with_capacity(256);
26
27        for (i, &b) in input.as_bytes()[..input.len() - 1]
28            .iter()
29            .enumerate()
30            .skip(1)
31        {
32            let dir = match b {
33                b'N' => -(WIDTH as isize),
34                b'E' => 1,
35                b'S' => WIDTH as isize,
36                b'W' => -1,
37                b'(' => {
38                    stack.push((std::mem::take(&mut start), std::mem::take(&mut end)));
39                    start.clone_from(&positions);
40
41                    continue;
42                }
43                b'|' => {
44                    if stack.is_empty() {
45                        return Err(InputError::new(input, i, "unexpected '|'"));
46                    }
47
48                    merge_sorted_deduped_in_place(&mut end, &positions);
49                    positions.clone_from(&start);
50
51                    continue;
52                }
53                b')' => {
54                    merge_sorted_deduped_in_place(&mut positions, &end);
55
56                    let Some(entry) = stack.pop() else {
57                        return Err(InputError::new(input, i, "unexpected ')'"));
58                    };
59                    (start, end) = entry;
60
61                    continue;
62                }
63                _ => {
64                    return Err(InputError::new(
65                        input,
66                        i,
67                        "expected 'N', 'E', 'S', 'W', '(', '|' or ')'",
68                    ));
69                }
70            };
71
72            for p in positions.iter_mut() {
73                let distance = grid[*p];
74                *p = p.wrapping_add_signed(dir);
75                if grid[*p] == 0 || distance + 1 < grid[*p] {
76                    grid[*p] = distance + 1;
77                }
78            }
79        }
80
81        if !stack.is_empty() {
82            return Err(InputError::new(input, input.len() - 1, "expected ')'"));
83        }
84
85        Ok(Self {
86            part1: grid.iter().max().copied().unwrap_or(0),
87            part2: grid.iter().filter(|&&d| d >= 1000).count() as u16,
88        })
89    }
90
91    #[must_use]
92    pub fn part1(&self) -> u16 {
93        self.part1
94    }
95
96    #[must_use]
97    pub fn part2(&self) -> u16 {
98        self.part2
99    }
100}
101
102examples!(Day20 -> (u16, u16) [
103    {input: "^WNE$", part1: 3},
104    {input: "^ENWWW(NEEE|SSE(EE|N))$", part1: 10},
105    {input: "^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$", part1: 18},
106    {input: "^ESSWWN(E|NNENN(EESS(WNSE|)SSS|WWWSSSSE(SW|NNNE)))$", part1: 23},
107    {input: "^WSSEESWWWNW(S|NENNEEEENN(ESSSSW(NWSW|SSEN)|WSWWN(E|WWS(E|SS))))$", part1: 31},
108]);
year2018/day20.rs

year2018/
day20.rs
