day14

2 files changed, 211 insertions, 0 deletions

diff --git a/inputs/day14 b/inputs/day14
new file mode 100644
index 0000000..e84aae5
--- /dev/null
+++ b/inputs/day14
@@ -0,0 +1,102 @@
+SNPVPFCPPKSBNSPSPSOF
+
+CF -> N
+NK -> B
+SF -> B
+HV -> P
+FN -> S
+VV -> F
+FO -> F
+VN -> V
+PV -> P
+FF -> P
+ON -> S
+PB -> S
+PK -> P
+OO -> P
+SP -> F
+VF -> H
+OV -> C
+BN -> P
+OH -> H
+NC -> F
+BH -> N
+CS -> C
+BC -> N
+OF -> N
+SN -> B
+FP -> F
+FV -> K
+HP -> H
+VB -> P
+FH -> F
+HF -> P
+BB -> O
+HH -> S
+PC -> O
+PP -> B
+VS -> B
+HC -> H
+NS -> N
+KF -> S
+BO -> V
+NP -> S
+NF -> K
+BS -> O
+KK -> O
+VC -> V
+KP -> K
+CK -> P
+HN -> F
+KN -> H
+KH -> N
+SB -> S
+NO -> K
+HK -> H
+BF -> V
+SV -> B
+CV -> P
+CO -> P
+FC -> O
+CP -> H
+CC -> N
+CN -> P
+SK -> V
+SS -> V
+VH -> B
+OS -> N
+FB -> H
+NB -> N
+SC -> K
+NV -> H
+HO -> S
+SO -> P
+PH -> C
+VO -> O
+OB -> O
+FK -> S
+PN -> P
+VK -> O
+NH -> N
+OC -> B
+BP -> O
+PF -> F
+KB -> K
+KV -> B
+PO -> N
+NN -> K
+CH -> O
+KC -> P
+OP -> V
+VP -> F
+OK -> P
+FS -> K
+CB -> S
+HB -> N
+KS -> O
+BK -> C
+BV -> O
+SH -> H
+PS -> N
+HS -> K
+KO -> N
diff --git a/src/bin/day14.rs b/src/bin/day14.rs
new file mode 100644
index 0000000..0f0d29c
--- /dev/null
+++ b/src/bin/day14.rs
@@ -0,0 +1,109 @@
+use std::collections::HashMap;
+
+fn main() {
+    let input = advent::read_lines(14);
+    println!("14a: {}", result_after(&input, 10));
+    println!("14b: {}", result_after(&input, 40));
+}
+
+struct Polymerizer {
+    template: String,
+    rules: HashMap<(char,char), char>,
+    pairs: HashMap<(char,char), usize>,
+}
+
+impl Polymerizer {
+    fn new<T: AsRef<str>>(input: &[T]) -> Polymerizer {
+        let template = String::from(input[0].as_ref());
+
+        let mut rules = HashMap::new();
+        for line in input.iter().skip(2) {
+            let (left, right) = line.as_ref().split_once(" -> ").unwrap();
+            let mut rule_chars = left.chars();
+
+            let right = right.chars().next().unwrap();
+            let left = (rule_chars.next().unwrap(), rule_chars.next().unwrap());
+            rules.insert(left, right);
+        }
+
+        let mut pairs = HashMap::new();
+        for (i, c) in template.chars().enumerate().skip(1) {
+            let mut pair = template.chars().skip(i-1);
+            let pair = (pair.next().unwrap(), c);
+            let entry = pairs.entry(pair).or_insert(0);
+            *entry += 1;
+        }
+
+        Polymerizer { template, rules, pairs }
+    }
+
+    fn step(&mut self) {
+        let mut new_pairs = HashMap::new();
+
+        for (pair, count) in &self.pairs {
+            let out = *self.rules.get(pair).unwrap();
+            let pair1 = (pair.0, out);
+            let pair2 = (out, pair.1);
+
+            let count1 = new_pairs.entry(pair1).or_insert(0);
+            *count1 += count;
+            let count2 = new_pairs.entry(pair2).or_insert(0);
+            *count2 += count;
+        }
+
+        self.pairs = new_pairs;
+    }
+
+    fn score(&self) -> usize {
+        let mut chars = HashMap::new();
+        chars.insert(self.template.chars().last().unwrap(), 1);
+
+        /* count first element of every pair */
+        for (pair, pair_count) in &self.pairs {
+            let char_count = chars.entry(pair.0).or_insert(0);
+            *char_count += pair_count;
+        }
+        let max = chars.values().max().unwrap();
+        let min = chars.values().min().unwrap();
+        max - min
+    }
+}
+
+fn result_after<T:AsRef<str>>(input: &[T], n: usize) -> usize {
+    let mut polymerizer = Polymerizer::new(input);
+    for _ in 0 .. n {
+        polymerizer.step();
+    }
+    polymerizer.score()
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test() {
+        let input = [
+            "NNCB",
+            "",
+            "CH -> B",
+            "HH -> N",
+            "CB -> H",
+            "NH -> C",
+            "HB -> C",
+            "HC -> B",
+            "HN -> C",
+            "NN -> C",
+            "BH -> H",
+            "NC -> B",
+            "NB -> B",
+            "BN -> B",
+            "BB -> N",
+            "BC -> B",
+            "CC -> N",
+            "CN -> C",
+        ];
+        assert_eq!(result_after(&input, 10), 1588);
+        assert_eq!(result_after(&input, 40), 2188189693529);
+    }
+}