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 *lexigraphically*. We'll replace all occurences 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 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 anything else, the packets are not
14//!   in order.
15//! * If the first packet is an opening `[` and the second character 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 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 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        .map(|(i, chunk)| {
43            let ordered = compare(chunk[0], chunk[1]);
44            if ordered { i + 1 } else { 0 }
45        })
46        .sum()
47}
48
49/// Find the position of `[[2]]` and `[[6]]` in linear `O(n)` time.
50///
51/// One approach would be to insert `[[2]]` and `[[6]]` into the list, sort in `O(nlogn)` time,
52/// then find the indices of the 2 values in `O(n)` time.
53///
54/// A much faster approach is to iterate over the list, comparing each packet first with `[[2]]`.
55/// If the packets are in order, then increment the positions of *both* `[[2]]` and `[[6]]`,
56/// since `[[2]]` is less than `[[6]]`.
57///
58/// If the packet and `[[2]]` are not in order, then also check against `[[6]]`, incrementing only
59/// the second index if the 2 packets are in order.
60///
61/// This obtains the relative indices of `[[2]]` and `[[6]]` efficiently in fewer than `2n` comparisons.
62pub fn part2(input: &[&str]) -> u32 {
63    let mut first = 1;
64    let mut second = 2;
65
66    for packet in input {
67        if compare(packet, "[[2]]") {
68            first += 1;
69            second += 1;
70        } else if compare(packet, "[[6]]") {
71            second += 1;
72        }
73    }
74
75    first * second
76}
77
78/// Compare 2 packets using the rules listed in the module description.
79///
80/// It's faster to use 2 temporary `vec`s to store extra characters, rather than copy each
81/// packet into a mutable [`VecDeque`]. We use the [`or_else`] method on [`Option`] to check
82/// in the temporary `vec` for available characters first.
83///
84/// [`VecDeque`]: std::collections::VecDeque
85/// [`or_else`]: Option::or_else
86fn compare(left: &str, right: &str) -> bool {
87    let mut left = Packet::new(left);
88    let mut right = Packet::new(right);
89
90    while let (Some(a), Some(b)) = (left.next(), right.next()) {
91        match (a, b) {
92            (a, b) if a == b => (),
93            (b']', _) => return true,
94            (_, b']') => return false,
95            (b'[', b) => {
96                right.extra.push(b']');
97                right.extra.push(b);
98            }
99            (a, b'[') => {
100                left.extra.push(b']');
101                left.extra.push(a);
102            }
103            (a, b) => return a < b,
104        }
105    }
106
107    unreachable!();
108}
109
110impl Iterator for Packet<'_> {
111    type Item = u8;
112
113    // Rely on the fact that all input is valid to avoid bounds checks
114    fn next(&mut self) -> Option<Self::Item> {
115        self.extra.pop().or_else(|| {
116            let (index, slice) = (self.index, self.slice);
117
118            // Replace occurences of "10" with "A"
119            if slice[index] == b'1' && slice[index + 1] == b'0' {
120                self.index += 2;
121                Some(b'A')
122            } else {
123                self.index += 1;
124                Some(slice[index])
125            }
126        })
127    }
128}
aoc/year2022/day13.rs

aoc/year2022/
day13.rs
