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

aoc/year2022/
day13.rs
