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