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 sized 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];
14type Rules = Vec<Rule>;
15
16pub struct Rule {
17    from: usize,
18    to_left: usize,
19    to_right: usize,
20    element: usize,
21}
22
23impl Rule {
24    fn parse([a, b, c]: [u8; 3]) -> Rule {
25        let from = pair(a, b);
26        let to_left = pair(a, c);
27        let to_right = pair(c, b);
28        let element = element(c);
29        Rule { from, to_left, to_right, element }
30    }
31}
32
33pub struct Input {
34    elements: Elements,
35    pairs: Pairs,
36    rules: Rules,
37}
38
39/// Count the initial pairs and elements and parse each instruction into a [`Rule`] struct.
40pub fn parse(input: &str) -> Input {
41    let (prefix, suffix) = input.split_once("\n\n").unwrap();
42    let prefix = prefix.trim().as_bytes();
43
44    let mut elements = [0; 26];
45    prefix.iter().for_each(|&b| elements[element(b)] += 1);
46
47    let mut pairs = [0; 26 * 26];
48    prefix.windows(2).for_each(|w| pairs[pair(w[0], w[1])] += 1);
49
50    let rules: Vec<_> =
51        suffix.bytes().filter(u8::is_ascii_uppercase).chunk::<3>().map(Rule::parse).collect();
52
53    Input { elements, pairs, rules }
54}
55
56/// Apply 10 steps.
57pub fn part1(input: &Input) -> u64 {
58    steps(input, 10)
59}
60
61/// Apply 40 steps.
62pub fn part2(input: &Input) -> u64 {
63    steps(input, 40)
64}
65
66/// Simulate an arbitrary number of steps.
67///
68/// A rule `AC` -> `ABC` implies that for each pair `AC` we create an equal number of pairs
69/// `AB` and `BC`, then increment the amount of element `B`.
70fn steps(input: &Input, rounds: usize) -> u64 {
71    let mut elements = input.elements;
72    let mut pairs = input.pairs;
73    let rules = &input.rules;
74
75    for _ in 0..rounds {
76        let mut next: Pairs = [0; 26 * 26];
77
78        for rule in rules {
79            let n = pairs[rule.from];
80            next[rule.to_left] += n;
81            next[rule.to_right] += n;
82            elements[rule.element] += n;
83        }
84
85        pairs = next;
86    }
87
88    let max = elements.iter().max().unwrap();
89    let min = elements.iter().filter(|&&n| n > 0).min().unwrap();
90    max - min
91}
92
93/// Convert a single uppercase ASCII character to an index between 0 and 25
94fn element(byte: u8) -> usize {
95    (byte - b'A') as usize
96}
97
98/// Convert two uppercase ASCII characters to an index between 0 and 675.
99fn pair(first: u8, second: u8) -> usize {
100    26 * element(first) + element(second)
101}
aoc/year2021/day14.rs

aoc/year2021/
day14.rs
