commit 555bb9e26b22625289fd09e6d6797d1965796a63
parent 4558ff0cfc17b0e9b8b2c94001a5f65714cc65e3
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Tue, 14 Dec 2021 19:21:49 -0600
Add 2021 day 14
Diffstat:
| A | 2021/day14/input.txt | | | 102 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2021/day14/main.rs | | | 92 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 194 insertions(+), 0 deletions(-)
diff --git a/2021/day14/input.txt b/2021/day14/input.txt
@@ -0,0 +1,102 @@
+CPSSSFCFOFVFNVPKBFVN
+
+NV -> V
+CF -> O
+BB -> F
+SB -> H
+KF -> O
+SP -> H
+CS -> V
+VF -> F
+PC -> H
+PH -> H
+SF -> F
+CP -> B
+BC -> H
+PB -> V
+KO -> B
+CV -> S
+ON -> B
+PV -> F
+OO -> B
+VV -> B
+NO -> B
+SH -> N
+FC -> C
+VO -> B
+NN -> C
+HH -> S
+CK -> C
+PF -> N
+SN -> K
+OK -> F
+FH -> S
+BP -> K
+HO -> K
+FB -> P
+HC -> N
+FP -> P
+NC -> H
+PK -> O
+BV -> P
+HK -> S
+PP -> N
+VC -> K
+CH -> C
+KS -> V
+KB -> V
+FN -> P
+BS -> O
+PS -> N
+NS -> B
+PN -> N
+NP -> H
+CB -> S
+SV -> O
+OC -> H
+BO -> C
+HN -> N
+HP -> N
+OF -> H
+FS -> S
+KV -> P
+HV -> S
+VS -> P
+BH -> N
+CC -> V
+VN -> H
+NF -> B
+NK -> N
+CN -> F
+FV -> P
+NH -> S
+OV -> H
+KN -> F
+SO -> H
+OP -> N
+KC -> P
+HB -> B
+BN -> V
+VP -> N
+HS -> S
+VK -> C
+VH -> H
+OS -> C
+FO -> B
+NB -> P
+KP -> V
+SS -> O
+BK -> F
+SK -> N
+HF -> O
+PO -> F
+OH -> B
+KK -> O
+FK -> S
+VB -> V
+OB -> C
+KH -> H
+SC -> F
+FF -> H
+CO -> V
+BF -> H
diff --git a/2021/day14/main.rs b/2021/day14/main.rs
@@ -0,0 +1,92 @@
+use std::collections::{HashMap, VecDeque};
+
+#[derive(Debug, Clone)]
+struct InsertionRules {
+ rules: HashMap<(char, char), char>,
+}
+
+impl InsertionRules {
+ fn new(s: &[String]) -> InsertionRules {
+ let mut rules = HashMap::new();
+ for line in s {
+ let mut it = line.split(" -> ");
+ let pair = it.next().unwrap().to_string();
+ let mut pair_it = pair.chars();
+ let left = pair_it.next().unwrap();
+ let right = pair_it.next().unwrap();
+ let insert = it.next().unwrap().chars().next().unwrap();
+ rules.insert((left, right), insert);
+ }
+ Self { rules }
+ }
+
+ fn apply(&self, pairs: HashMap<(char, char), usize>) -> HashMap<(char, char), usize> {
+ let mut new_pairs = HashMap::new();
+ for ((a, b), count) in pairs {
+ if let Some(&c) = self.rules.get(&(a, b)) {
+ new_pairs.insert((a, c), *new_pairs.get(&(a, c)).unwrap_or(&0) + count);
+ new_pairs.insert((c, b), *new_pairs.get(&(c, b)).unwrap_or(&0) + count);
+ }
+ }
+ new_pairs
+ }
+}
+
+fn main() {
+ let input = std::fs::read_to_string("input.txt")
+ .unwrap()
+ .trim()
+ .split('\n')
+ .map(|s| s.to_string())
+ .collect::<Vec<String>>();
+ let template = input[0].chars().collect::<VecDeque<char>>();
+ let rules = InsertionRules::new(&input[2..]);
+ // 3697
+ println!("Part 1: {}", part_1(&template, &rules, 10));
+ // 4371307836157
+ println!("Part 2: {}", part_1(&template, &rules, 40));
+}
+
+fn polymer_to_pairs(mut polymer: VecDeque<char>) -> HashMap<(char, char), usize> {
+ let mut pairs = HashMap::new();
+ let mut prev = None;
+ loop {
+ match (prev, polymer.pop_front()) {
+ (None, Some(b)) => {
+ prev = Some(b);
+ }
+ (Some(a), Some(b)) => {
+ pairs.insert((a, b), *pairs.get(&(a, b)).unwrap_or(&0) + 1);
+ prev = Some(b);
+ }
+ _ => {
+ break;
+ }
+ }
+ }
+ pairs
+}
+
+fn part_1(template: &VecDeque<char>, rules: &InsertionRules, steps: usize) -> usize {
+ let mut pairs = polymer_to_pairs(template.clone());
+ for _ in 0..steps {
+ pairs = rules.apply(pairs);
+ }
+
+ let mut counter = HashMap::<char, usize>::new();
+ for ((a, b), count) in pairs {
+ counter.insert(a, *counter.get(&a).unwrap_or(&0) + count);
+ counter.insert(b, *counter.get(&b).unwrap_or(&0) + count);
+ }
+ let head = template.front().unwrap();
+ let tail = template.back().unwrap();
+ for (k, v) in counter.iter_mut() {
+ if k == head || k == tail {
+ *v = (*v + 1) / 2;
+ } else {
+ *v = *v / 2;
+ }
+ }
+
+ *counter.values().max().unwrap() - *counter.values().min().unwrap()
+}