aoc/year2021/
day14.rs

1//! # Extended Polymerization
2//!
3//! The key insight to this problem is the same as [`Day 6`]. We track the *total* number of
4//! each pair as the positions don't affect the final result.
5//!
6//! Fixed-size arrays are used for speed as we know that the elements are limited to 26 values
7//! and the possible pairs to 26 × 26 values.
8//!
9//! [`Day 6`]: crate::year2021::day06
10use crate::util::iter::*;
11
12type Elements = [u64; 26];
13type Pairs = [u64; 26 * 26];
14
15struct Rule {
16    from: usize,
17    to_left: usize,
18    to_right: usize,
19    element: usize,
20}
21
22impl Rule {
23    fn parse([a, b, c]: [u8; 3]) -> Self {
24        Self { from: pair(a, b), to_left: pair(a, c), to_right: pair(c, b), element: element(c) }
25    }
26}
27
28pub struct Input {
29    elements: Elements,
30    pairs: Pairs,
31    rules: Vec<Rule>,
32}
33
34/// Count the initial pairs and elements and parse each instruction into a [`Rule`] struct.
35pub fn parse(input: &str) -> Input {
36    let (prefix, suffix) = input.split_once("\n\n").unwrap();
37    let prefix = prefix.trim().as_bytes();
38
39    let mut elements = [0; 26];
40    prefix.iter().for_each(|&b| elements[element(b)] += 1);
41
42    let mut pairs = [0; 26 * 26];
43    prefix.array_windows().for_each(|&[a, b]| pairs[pair(a, b)] += 1);
44
45    let rules =
46        suffix.bytes().filter(u8::is_ascii_uppercase).chunk::<3>().map(Rule::parse).collect();
47
48    Input { elements, pairs, rules }
49}
50
51/// Apply 10 steps.
52pub fn part1(input: &Input) -> u64 {
53    steps(input, 10)
54}
55
56/// Apply 40 steps.
57pub fn part2(input: &Input) -> u64 {
58    steps(input, 40)
59}
60
61/// Simulate an arbitrary number of steps.
62///
63/// A rule `AC` -> `ABC` implies that for each pair `AC` we create an equal number of pairs
64/// `AB` and `BC`, then increment the amount of element `B`.
65fn steps(input: &Input, rounds: usize) -> u64 {
66    let mut elements = input.elements;
67    let mut pairs = input.pairs.to_vec();
68    let mut next = vec![0; 26 * 26];
69
70    for _ in 0..rounds {
71        next.fill(0);
72
73        for rule in &input.rules {
74            let n = pairs[rule.from];
75            next[rule.to_left] += n;
76            next[rule.to_right] += n;
77            elements[rule.element] += n;
78        }
79
80        (pairs, next) = (next, pairs);
81    }
82
83    let max = elements.iter().max().unwrap();
84    let min = elements.iter().filter(|&&n| n > 0).min().unwrap();
85    max - min
86}
87
88/// Convert a single uppercase ASCII character to an index between 0 and 25.
89fn element(byte: u8) -> usize {
90    usize::from(byte - b'A')
91}
92
93/// Convert two uppercase ASCII characters to an index between 0 and 675.
94fn pair(first: u8, second: u8) -> usize {
95    26 * element(first) + element(second)
96}
aoc/year2021/day14.rs

aoc/year2021/
day14.rs
