aoc/year2022/
day13.rs

1//! # Distress Signal
2//!
3//! One possible approach is to parse the input into a tree, then compare recursively node
4//! by node. We're going to use a much faster and simpler approach by noting an observation about
5//! the input data. If the sequence `10` is replaced by any single character greater than `9` then
6//! we can compare the 2 packets *lexicographically*. We'll replace all occurrences of `10` with `A`
7//! then compare packets character by character.
8//!
9//! The rules to compare 2 packets become:
10//! * If both characters are the same then it's a draw, move onto the next character in each packet.
11//! * If the first packet is `]` and the second packet is anything else, then the first list is shorter
12//!   so the packets are in order.
13//! * Conversely, if the second packet is `]` and the first packet is anything else, the packets are not
14//!   in order.
15//! * If the first packet is an opening `[` and the second character is anything else, then we're
16//!   comparing a number with a list, so *push* the second character back onto the list to check
17//!   again along with a closing `]` character.
18//! * Do a similar push if the second character is an opening `[` and the first is anything else.
19//! * Finally, compare the 2 characters by value. Since we've already covered the equal case, one
20//!   is guaranteed to be greater than or less than the other.
21struct Packet<'a> {
22    slice: &'a [u8],
23    index: usize,
24    extra: Vec<u8>,
25}
26
27impl Packet<'_> {
28    fn new(str: &str) -> Packet<'_> {
29        Packet { slice: str.as_bytes(), index: 0, extra: Vec::new() }
30    }
31}
32
33pub fn parse(input: &str) -> Vec<&str> {
34    input.lines().filter(|line| !line.is_empty()).collect()
35}
36
37/// Count adjacent pairs of packets that are in order.
38pub fn part1(input: &[&str]) -> usize {
39    input
40        .chunks_exact(2)
41        .enumerate()
42        .filter_map(|(i, chunk)| compare(chunk[0], chunk[1]).then_some(i + 1))
43        .sum()
44}
45
46/// Find the position of `[[2]]` and `[[6]]` in linear `O(n)` time.
47///
48/// One approach would be to insert `[[2]]` and `[[6]]` into the list, sort in `O(nlogn)` time,
49/// then find the indices of the 2 values in `O(n)` time.
50///
51/// A much faster approach is to iterate over the list, comparing each packet first with `[[2]]`.
52/// If the packets are in order, then increment the positions of *both* `[[2]]` and `[[6]]`,
53/// since `[[2]]` is less than `[[6]]`.
54///
55/// If the packet and `[[2]]` are not in order, then also check against `[[6]]`, incrementing only
56/// the second index if the 2 packets are in order.
57///
58/// This obtains the relative indices of `[[2]]` and `[[6]]` efficiently in fewer than `2n` comparisons.
59pub fn part2(input: &[&str]) -> u32 {
60    let mut first = 1;
61    let mut second = 2;
62
63    for packet in input {
64        if compare(packet, "[[2]]") {
65            first += 1;
66            second += 1;
67        } else if compare(packet, "[[6]]") {
68            second += 1;
69        }
70    }
71
72    first * second
73}
74
75/// Compare 2 packets using the rules listed in the module description.
76///
77/// It's faster to use 2 temporary `vec`s to store extra characters, rather than copy each
78/// packet into a mutable [`VecDeque`]. We use the [`or_else`] method on [`Option`] to check
79/// in the temporary `vec` for available characters first.
80///
81/// [`VecDeque`]: std::collections::VecDeque
82/// [`or_else`]: Option::or_else
83fn compare(left: &str, right: &str) -> bool {
84    let mut left = Packet::new(left);
85    let mut right = Packet::new(right);
86
87    while let (Some(a), Some(b)) = (left.next(), right.next()) {
88        match (a, b) {
89            (a, b) if a == b => (),
90            (b']', _) => return true,
91            (_, b']') => return false,
92            (b'[', b) => {
93                right.extra.push(b']');
94                right.extra.push(b);
95            }
96            (a, b'[') => {
97                left.extra.push(b']');
98                left.extra.push(a);
99            }
100            (a, b) => return a < b,
101        }
102    }
103
104    unreachable!()
105}
106
107impl Iterator for Packet<'_> {
108    type Item = u8;
109
110    // Rely on the fact that all input is valid to avoid bounds checks.
111    fn next(&mut self) -> Option<Self::Item> {
112        self.extra.pop().or_else(|| {
113            let (index, slice) = (self.index, self.slice);
114
115            // Replace occurrences of "10" with "A"
116            if slice[index] == b'1' && slice[index + 1] == b'0' {
117                self.index += 2;
118                Some(b'A')
119            } else {
120                self.index += 1;
121                Some(slice[index])
122            }
123        })
124    }
125}
aoc/year2022/day13.rs

aoc/year2022/
day13.rs
