1 files changed, 125 insertions, 0 deletions
diff --git a/2021/src/bin/day_14.rs b/2021/src/bin/day_14.rs
new file mode 100644
index 0000000..e757faf
--- /dev/null
+++ b/2021/src/bin/day_14.rs
@@ -0,0 +1,125 @@
+use nom::{
+    bytes::complete::tag,
+    character::complete::{alpha1, anychar, line_ending},
+    combinator::map,
+    multi::{many0, separated_list1},
+    sequence::tuple,
+    IResult,
+};
+use std::{collections::BTreeMap, fs};
+
+fn main() -> Result<(), Box<dyn std::error::Error>> {
+    let input = fs::read_to_string("inputs/day_14.txt")?;
+    let mut polymer = parse_polymer_expansion(&input).unwrap().1;
+
+    let small_expansion_counts = polymer.count_after_expansions(10);
+    dbg!(small_expansion_counts.most_common() - small_expansion_counts.least_common());
+
+    let big_expansion_counts = polymer.count_after_expansions(40);
+    dbg!(big_expansion_counts.most_common() - big_expansion_counts.least_common());
+
+    Ok(())
+}
+
+#[derive(Debug)]
+struct PolymerExpansion {
+    polymer: Vec<char>,
+    rules: Rules,
+    cache: BTreeMap<(char, char, usize), ElementCount>,
+}
+
+impl PolymerExpansion {
+    fn new(polymer: Vec<char>, rules: Rules) -> PolymerExpansion {
+        PolymerExpansion {
+            polymer,
+            rules,
+            cache: BTreeMap::new(),
+        }
+    }
+
+    fn count_after_expansions(&mut self, expansions: usize) -> ElementCount {
+        let mut counts = ElementCount::default();
+        for i in 0..self.polymer.len() - 1 {
+            counts.add(self.polymer[i]);
+            counts.append(self.count_between(self.polymer[i], self.polymer[i + 1], expansions));
+        }
+        counts.add(self.polymer[self.polymer.len() - 1]);
+        counts
+    }
+
+    fn count_between(
+        &mut self,
+        left: char,
+        right: char,
+        remaining_expansions: usize,
+    ) -> ElementCount {
+        if remaining_expansions == 0 {
+            ElementCount::default()
+        } else if let Some(cached) = self.cache.get(&(left, right, remaining_expansions)) {
+            cached.clone()
+        } else {
+            let mut counts = ElementCount::default();
+            let middle = self.rules.get(&[left, right]).expect("No rule!");
+            counts.add(middle);
+            counts.append(self.count_between(left, middle, remaining_expansions - 1));
+            counts.append(self.count_between(middle, right, remaining_expansions - 1));
+            self.cache
+                .insert((left, right, remaining_expansions), counts.clone());
+            counts
+        }
+    }
+}
+
+#[derive(Debug, Default, Clone)]
+struct ElementCount(BTreeMap<char, u64>);
+
+impl ElementCount {
+    fn add(&mut self, c: char) {
+        *self.0.entry(c).or_insert(0) += 1;
+    }
+
+    fn append(&mut self, other: ElementCount) {
+        for (key, val) in other.0 {
+            *self.0.entry(key).or_insert(0) += val;
+        }
+    }
+
+    fn most_common(&self) -> u64 {
+        self.0.values().max().cloned().unwrap_or(0)
+    }
+
+    fn least_common(&self) -> u64 {
+        self.0.values().min().cloned().unwrap_or(0)
+    }
+}
+
+#[derive(Debug)]
+struct Rules {
+    rules: BTreeMap<[char; 2], char>,
+}
+
+impl Rules {
+    fn get(&self, key: &[char; 2]) -> Option<char> {
+        self.rules.get(key).cloned()
+    }
+}
+
+fn parse_polymer_expansion(input: &str) -> IResult<&str, PolymerExpansion> {
+    let (input, polymer) = map(alpha1, |s: &str| s.chars().collect())(input)?;
+    let (input, _) = many0(line_ending)(input)?;
+    let (input, rules) = parse_rules(input)?;
+    Ok((input, PolymerExpansion::new(polymer, rules)))
+}
+
+fn parse_rules(input: &str) -> IResult<&str, Rules> {
+    map(separated_list1(line_ending, parse_rule), |rules| Rules {
+        rules: rules.into_iter().collect(),
+    })(input)
+}
+
+fn parse_rule(input: &str) -> IResult<&str, ([char; 2], char)> {
+    map(
+        tuple((anychar, anychar, tag(" -> "), anychar)),
+        |(p1, p2, _, r)| ([p1, p2], r),
+    )(input)
+}