year2019/
day06.rs

1use utils::parser::{ParseError, Parser};
2use utils::prelude::*;
3
4/// Counting depths and distances in a tree.
5#[derive(Clone, Debug)]
6pub struct Day06 {
7    parents: Vec<u16>,
8    depths: Vec<u16>,
9    you: u16,
10    san: u16,
11}
12
13const RADIX: u16 = 36;
14const LABEL_SPACE: usize = (36 * 36 * 36) + (36 * 36) + (36);
15const LABEL_BYTE_LUT: [Option<u16>; 256] = {
16    let mut result = [None; 256];
17
18    let mut i = 0;
19    while i < 10 {
20        result[(b'0' as usize) + i] = Some(i as u16);
21        i += 1;
22    }
23
24    let mut i = 0;
25    while i < 26 {
26        result[(b'A' as usize) + i] = Some(i as u16 + 10);
27        i += 1;
28    }
29
30    result
31};
32
33const fn encode(label: [u8; 3]) -> u16 {
34    const fn encode_byte(b: u8) -> u16 {
35        LABEL_BYTE_LUT[b as usize].unwrap()
36    }
37    encode_byte(label[0]) * RADIX * RADIX + encode_byte(label[1]) * RADIX + encode_byte(label[2])
38}
39const COM: u16 = encode(*b"COM");
40const YOU: u16 = encode(*b"YOU");
41const SAN: u16 = encode(*b"SAN");
42
43impl Day06 {
44    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
45        let label_byte = parser::byte_lut(
46            &LABEL_BYTE_LUT,
47            ParseError::Custom("expected uppercase letter or digit"),
48        );
49        let label = parser::parse_tree!((a @ label_byte) =>> {
50            (b @ label_byte) =>> {
51                (c @ label_byte) => a * RADIX * RADIX + b * RADIX + c,
52                (parser::noop()) => (RADIX * RADIX * RADIX) + a * RADIX + b,
53            },
54            (parser::noop()) => (RADIX * RADIX * RADIX) + (RADIX * RADIX) + a,
55        });
56        let orbit = label
57            .then(label.with_prefix(")"))
58            .with_consumed()
59            .with_eol();
60
61        let mut label_to_dense = [u16::MAX; LABEL_SPACE];
62        let mut parents = Vec::with_capacity(2048);
63        for item in orbit.parse_iterator(input) {
64            let ((lhs, rhs), line): ((u16, u16), &[u8]) = item?;
65            if rhs == COM {
66                return Err(InputError::new(
67                    input,
68                    line,
69                    "expected COM to have no parent",
70                ));
71            }
72            if lhs == rhs {
73                return Err(InputError::new(
74                    input,
75                    line,
76                    "expected object to not orbit itself",
77                ));
78            }
79
80            let mut intern = |label| {
81                let dense_index = label_to_dense[usize::from(label)];
82                if dense_index == u16::MAX {
83                    let next = parents.len();
84                    parents.push(u16::MAX);
85                    label_to_dense[usize::from(label)] = next as u16;
86                    next as u16
87                } else {
88                    dense_index
89                }
90            };
91            let lhs = intern(lhs);
92            let rhs = intern(rhs);
93
94            if parents[usize::from(rhs)] != u16::MAX {
95                return Err(InputError::new(
96                    input,
97                    line,
98                    "expected each object to have one parent",
99                ));
100            }
101            parents[usize::from(rhs)] = lhs;
102        }
103
104        let com = label_to_dense[usize::from(COM)];
105        if com == u16::MAX {
106            return Err(InputError::new(input, 0, "expected COM object"));
107        }
108        let mut depths = vec![u16::MAX; parents.len()];
109        depths[usize::from(com)] = 0;
110
111        let mut stack = Vec::with_capacity(256);
112        for start in 0..parents.len() {
113            if depths[start] != u16::MAX {
114                continue;
115            }
116
117            let mut current = start;
118            while depths[current] == u16::MAX {
119                stack.push(current as u16);
120
121                if stack.len() > parents.len() {
122                    return Err(InputError::new(input, 0, "expected acyclic orbit graph"));
123                }
124
125                let next = parents[current];
126                if next == u16::MAX {
127                    return Err(InputError::new(
128                        input,
129                        0,
130                        "expected all objects to connect to COM",
131                    ));
132                }
133                current = usize::from(next);
134            }
135
136            let mut depth = depths[current];
137            while let Some(node) = stack.pop() {
138                depth += 1;
139                depths[usize::from(node)] = depth;
140            }
141        }
142
143        Ok(Self {
144            parents,
145            depths,
146            you: label_to_dense[usize::from(YOU)],
147            san: label_to_dense[usize::from(SAN)],
148        })
149    }
150
151    #[must_use]
152    pub fn part1(&self) -> u32 {
153        self.depths.iter().map(|&depth| u32::from(depth)).sum()
154    }
155
156    #[must_use]
157    pub fn part2(&self) -> u32 {
158        assert!(
159            !(self.you == u16::MAX || self.san == u16::MAX),
160            "expected YOU and SAN objects"
161        );
162
163        let mut a = usize::from(self.parents[self.you as usize]);
164        let mut b = usize::from(self.parents[self.san as usize]);
165        let mut distance = 0;
166        while self.depths[a] > self.depths[b] {
167            a = usize::from(self.parents[a]);
168            distance += 1;
169        }
170        while self.depths[b] > self.depths[a] {
171            b = usize::from(self.parents[b]);
172            distance += 1;
173        }
174        while a != b {
175            a = usize::from(self.parents[a]);
176            b = usize::from(self.parents[b]);
177            distance += 2;
178        }
179
180        distance
181    }
182}
183
184examples!(Day06 -> (u32, u32) [
185    {
186        input: "COM)B\nB)C\nC)D\nD)E\nE)F\nB)G\nG)H\nD)I\nE)J\nJ)K\nK)L",
187        part1: 42,
188    },
189    {
190        input: "COM)B\nB)C\nC)D\nD)E\nE)F\nB)G\nG)H\nD)I\nE)J\nJ)K\nK)L\nK)YOU\nI)SAN",
191        part2: 4,
192    },
193]);
year2019/day06.rs

year2019/
day06.rs
