aoc/year2018/
day05.rs

1//! # Alchemical Reduction
2//!
3//! ## Part One
4//!
5//! This problem is similar to checking if a parentheses expression is balanced or not.
6//! We use a similar approach, maintaining a stack of unreacted polymer units. Each unit from the
7//! polymer is compared to the head of the stack using bitwise logic. Lowercase and uppercase ASCII
8//! codes for the same lettter are always are 32 apart, which can be checked very quickly using
9//! bitwise XOR. For example:
10//!
11//! ```none
12//!         A = 65 = 01000001
13//!         a = 97 = 01100001
14//!     A ^ a = 32 = 00100000
15//! ```
16//!
17//! If two units are the same type but opposite polarity then they are popped from the stack.
18//!
19//! ## Part Two
20//!
21//! An important optimization is to use the already reacted polymer from part one. This is
22//! approximately 20% of the size of the raw input. Then this smaller polymer is filtered
23//! further for each of the 26 kinds of unit.
24pub fn parse(input: &str) -> Vec<u8> {
25    collapse(input.trim().bytes())
26}
27
28pub fn part1(input: &[u8]) -> usize {
29    input.len()
30}
31
32pub fn part2(input: &[u8]) -> usize {
33    (b'a'..=b'z')
34        .map(|kind| collapse(input.iter().copied().filter(|&b| b | 32 != kind)).len())
35        .min()
36        .unwrap()
37}
38
39fn collapse(polymer: impl Iterator<Item = u8>) -> Vec<u8> {
40    // It's faster to keep the head of the stack in a dedicated variable. 0 is used as a special
41    // sentinel kind to indicate an empty stack as it will never match with any unit kind.
42    let mut head = 0;
43    let mut stack = Vec::with_capacity(10_000);
44
45    for unit in polymer {
46        // Uppercase and lowercase ASCII are always 32 apart.
47        if head ^ unit == 32 {
48            // The head reacts with the unit to annihilate each other so replace with the next unit
49            // from the stack.
50            head = stack.pop().unwrap_or(0);
51        } else {
52            // Don't push sentinel values.
53            if head != 0 {
54                stack.push(head);
55            }
56            head = unit;
57        }
58    }
59
60    if head != 0 {
61        stack.push(head);
62    }
63
64    stack
65}
aoc/year2018/day05.rs

aoc/year2018/
day05.rs
