main.rs (2861B)
1 use std::collections::{HashMap, VecDeque};
2
3 #[derive(Debug, Clone)]
4 struct InsertionRules {
5 rules: HashMap<(char, char), char>,
6 }
7
8 impl InsertionRules {
9 fn new(s: &[String]) -> InsertionRules {
10 let mut rules = HashMap::new();
11 for line in s {
12 let mut it = line.split(" -> ");
13 let pair = it.next().unwrap().to_string();
14 let mut pair_it = pair.chars();
15 let left = pair_it.next().unwrap();
16 let right = pair_it.next().unwrap();
17 let insert = it.next().unwrap().chars().next().unwrap();
18 rules.insert((left, right), insert);
19 }
20 Self { rules }
21 }
22
23 fn apply(&self, pairs: HashMap<(char, char), usize>) -> HashMap<(char, char), usize> {
24 let mut new_pairs = HashMap::new();
25 for ((a, b), count) in pairs {
26 if let Some(&c) = self.rules.get(&(a, b)) {
27 new_pairs.insert((a, c), *new_pairs.get(&(a, c)).unwrap_or(&0) + count);
28 new_pairs.insert((c, b), *new_pairs.get(&(c, b)).unwrap_or(&0) + count);
29 }
30 }
31 new_pairs
32 }
33 }
34
35 fn main() {
36 let input = std::fs::read_to_string("input.txt")
37 .unwrap()
38 .trim()
39 .split('\n')
40 .map(|s| s.to_string())
41 .collect::<Vec<String>>();
42 let template = input[0].chars().collect::<VecDeque<char>>();
43 let rules = InsertionRules::new(&input[2..]);
44 // 3697
45 println!("Part 1: {}", part_1(&template, &rules, 10));
46 // 4371307836157
47 println!("Part 2: {}", part_1(&template, &rules, 40));
48 }
49
50 fn polymer_to_pairs(mut polymer: VecDeque<char>) -> HashMap<(char, char), usize> {
51 let mut pairs = HashMap::new();
52 let mut prev = None;
53 loop {
54 match (prev, polymer.pop_front()) {
55 (None, Some(b)) => {
56 prev = Some(b);
57 }
58 (Some(a), Some(b)) => {
59 pairs.insert((a, b), *pairs.get(&(a, b)).unwrap_or(&0) + 1);
60 prev = Some(b);
61 }
62 _ => {
63 break;
64 }
65 }
66 }
67 pairs
68 }
69
70 fn part_1(template: &VecDeque<char>, rules: &InsertionRules, steps: usize) -> usize {
71 let mut pairs = polymer_to_pairs(template.clone());
72 for _ in 0..steps {
73 pairs = rules.apply(pairs);
74 }
75
76 let mut counter = HashMap::<char, usize>::new();
77 for ((a, b), count) in pairs {
78 counter.insert(a, *counter.get(&a).unwrap_or(&0) + count);
79 counter.insert(b, *counter.get(&b).unwrap_or(&0) + count);
80 }
81 let head = template.front().unwrap();
82 let tail = template.back().unwrap();
83 for (k, v) in counter.iter_mut() {
84 if k == head || k == tail {
85 *v = (*v + 1) / 2;
86 } else {
87 *v = *v / 2;
88 }
89 }
90
91 *counter.values().max().unwrap() - *counter.values().min().unwrap()
92 }