commit c9d011b4813b1ebc520e9ab5880cec09fa2db76a
parent 4348e9bcc6e5dd2699c24c956be376546a58f7d3
Author: Louis Burda <quent.burda@gmail.com>
Date: Mon, 10 Apr 2023 19:31:26 -0400
Add day 14 solution
Diffstat:
6 files changed, 364 insertions(+), 0 deletions(-)
diff --git a/src/14/Cargo.toml b/src/14/Cargo.toml
@@ -0,0 +1,7 @@
+[package]
+name = "day14"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
+aoc = { path = "../common/aoc" }
diff --git a/src/14/input b/src/14/input
@@ -0,0 +1,103 @@
+VPPHOPVVSFSVFOCOSBKF
+
+CO -> B
+CV -> N
+HV -> H
+ON -> O
+FS -> F
+NS -> S
+VK -> C
+BV -> F
+SC -> N
+NV -> V
+NC -> F
+NH -> B
+BO -> K
+FC -> H
+NB -> H
+HO -> F
+SB -> N
+KP -> V
+OS -> C
+OB -> P
+SH -> N
+BC -> H
+CK -> H
+SO -> N
+SP -> P
+CF -> P
+KV -> F
+CS -> V
+FF -> P
+VS -> V
+CP -> S
+PH -> V
+OP -> K
+KH -> B
+FB -> S
+CN -> H
+KS -> P
+FN -> O
+PV -> O
+VC -> S
+HF -> N
+OC -> O
+PK -> V
+KC -> C
+HK -> C
+PO -> N
+OO -> S
+VH -> N
+CC -> K
+BP -> K
+HC -> K
+FV -> K
+KF -> V
+VF -> C
+HN -> S
+VP -> B
+HH -> O
+FO -> O
+PC -> N
+KK -> C
+PN -> P
+NN -> C
+FH -> N
+VV -> O
+OK -> V
+CB -> N
+SN -> H
+VO -> H
+BB -> C
+PB -> F
+NF -> P
+KO -> S
+PP -> K
+NO -> O
+SF -> N
+KN -> S
+PS -> O
+VN -> V
+SS -> N
+BF -> O
+HP -> H
+HS -> N
+BS -> S
+VB -> F
+PF -> K
+SV -> V
+BH -> P
+FP -> O
+CH -> P
+OH -> K
+OF -> F
+HB -> V
+FK -> V
+BN -> V
+SK -> F
+OV -> C
+NP -> S
+NK -> S
+BK -> C
+KB -> F
+
diff --git a/src/14/part1 b/src/14/part1
@@ -0,0 +1,75 @@
+--- Day 14: Extended Polymerization ---
+
+The incredible pressures at this depth are starting to put a strain on your submarine. The submarine
+has polymerization equipment that would produce suitable materials to reinforce the submarine, and
+the nearby volcanically-active caves should even have the necessary input elements in sufficient
+quantities.
+
+The submarine manual contains instructions for finding the optimal polymer formula; specifically, it
+offers a [1m[97mpolymer template[0m and a list of [1m[97mpair insertion[0m rules (your puzzle input). You just need to
+work out what polymer would result after repeating the pair insertion process a few times.
+
+For example:
+
+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
+
+The first line is the [1m[97mpolymer template[0m - this is the starting point of the process.
+
+The following section defines the [1m[97mpair insertion[0m rules. A rule like AB -> C means that when elements
+A and B are immediately adjacent, element C should be inserted between them. These insertions all
+happen simultaneously.
+
+So, starting with the polymer template NNCB, the first step simultaneously considers all three
+pairs:
+
+
+ - The first pair (NN) matches the rule NN -> C, so element [1m[97mC[0m is inserted between the first N and
+the second N.
+
+ - The second pair (NC) matches the rule NC -> B, so element [1m[97mB[0m is inserted between the N and the C.
+
+ - The third pair (CB) matches the rule CB -> H, so element [1m[97mH[0m is inserted between the C and the B.
+
+
+Note that these pairs overlap: the second element of one pair is the first element of the next pair.
+Also, because all pairs are considered simultaneously, inserted elements are not considered to be
+part of a pair until the next step.
+
+After the first step of this process, the polymer becomes
+N[1m[97mC[0mN[1m[97mB[0mC[1m[97mH[0mB.
+
+Here are the results of a few steps using the above rules:
+
+Template: NNCB
+After step 1: NCNBCHB
+After step 2: NBCCNBBBCBHCB
+After step 3: NBBBCNCCNBBNBNBBCHBHHBCHB
+After step 4: NBBNBNBBCCNBCNCCNBBNBBNBBBNBBNBBCBHCBHHNHCBBCBHCB
+
+This polymer grows quickly. After step 5, it has length 97; After step 10, it has length 3073. After
+step 10, B occurs 1749 times, C occurs 298 times, H occurs 161 times, and N occurs 865 times; taking
+the quantity of the most common element (B, 1749) and subtracting the quantity of the least common
+element (H, 161) produces 1749 - 161 = [1m[97m1588[0m.
+
+Apply 10 steps of pair insertion to the polymer template and find the most and least common elements
+in the result. [1m[97mWhat do you get if you take the quantity of the most common element and subtract the
+quantity of the least common element?[0m
+
+
diff --git a/src/14/part2 b/src/14/part2
@@ -0,0 +1,14 @@
+--- Part Two ---
+
+The resulting polymer isn't nearly strong enough to reinforce the submarine. You'll need to run more
+steps of the pair insertion process; a total of [1m[97m40 steps[0m should do it.
+
+In the above example, the most common element is B (occurring 2192039569602 times) and the least
+common element is H (occurring 3849876073 times); subtracting these produces
+[1m[97m2188189693529[0m.
+
+Apply [1m[97m40[0m steps of pair insertion to the polymer template and find the most and least common elements
+in the result. [1m[97mWhat do you get if you take the quantity of the most common element and subtract the
+quantity of the least common element?[0m
+
+
diff --git a/src/14/src/main.rs b/src/14/src/main.rs
@@ -0,0 +1,146 @@
+use std::collections::HashMap;
+use aoc::debugln;
+
+fn parse_input(input: &String) -> (String, HashMap<String, char>) {
+ let mut rules: HashMap<String, char> = HashMap::new();
+ let mut lines = input.lines();
+ let state = lines.next().unwrap().to_string();
+ for l in lines {
+ if l.is_empty() { continue; }
+ let (pre, rest) = l.split_once(" -> ").unwrap();
+ rules.insert(pre.to_string(), rest.chars().next().unwrap());
+ }
+ return (state, rules);
+}
+
+fn grow_polymer(input: String, rules: &HashMap<String, char>) -> String {
+ let mut output: Vec<char> = Vec::new();
+ let mut s = input.as_str();
+ for i in 0..input.len()-1 {
+ let part = &s[..2];
+ let res = rules.get(part);
+ if i == 0 {
+ output.push(part.chars().nth(0).unwrap());
+ }
+ if res.is_some() {
+ output.push(res.unwrap().clone());
+ output.push(part.chars().nth(1).unwrap());
+ } else {
+ output.push(part.chars().nth(1).unwrap());
+ }
+ s = &s[1..];
+ }
+ return output.into_iter().collect();
+}
+
+fn build_charset(state: &String, rules: &HashMap<String, char>) -> String {
+ let mut charset: HashMap<char, bool> = HashMap::new();
+
+ for c in state.chars() {
+ charset.insert(c, true);
+ }
+ for (pre, post) in rules.iter() {
+ for c in pre.chars() {
+ charset.insert(c, true);
+ }
+ charset.insert(post.clone(), true);
+ }
+
+ return charset.into_iter().map(|(c,_)| c).collect();
+}
+
+fn gen_segments(state: &String) -> HashMap<String, usize> {
+ let mut counts: HashMap<String, usize> = HashMap::new();
+ let mut s = state.as_str();
+ for _ in 0..state.len()-1 {
+ let seg = s[..2].to_string();
+ let cnt = counts.get_mut(&seg);
+ if cnt.is_some() {
+ *cnt.unwrap() += 1;
+ } else {
+ counts.insert(seg, 1);
+ }
+ s = &s[1..];
+ }
+ return counts;
+}
+
+fn add_polymer_segments(seg: String, cnt: usize, segments: &mut HashMap<String,usize>) {
+ let count = segments.get_mut(&seg);
+ if count.is_some() {
+ *count.unwrap() += cnt;
+ } else {
+ segments.insert(seg, cnt);
+ }
+}
+
+fn grow_polymer_segments(segments: &mut HashMap<String,usize>,
+ charcnt: &mut HashMap<char, usize>, rules: &HashMap<String,char>) {
+ let mut new_segments: HashMap<String, usize> = HashMap::new();
+ for (seg,cnt) in segments.iter() {
+ let res = rules.get(seg);
+ let pre: char = seg.as_str().chars().take(1).last().unwrap();
+ let post: char = seg.as_str().chars().last().unwrap();
+ if res.is_some() {
+ let mid = *res.unwrap();
+ let seg1: String = vec![pre, mid].iter().collect();
+ add_polymer_segments(seg1, *cnt, &mut new_segments);
+ let seg2: String = vec![mid, post].iter().collect();
+ add_polymer_segments(seg2, *cnt, &mut new_segments);
+ let ccnt = charcnt.get_mut(&mid);
+ *ccnt.unwrap() += cnt;
+ } else {
+ let seg: String = vec![pre, post].iter().collect();
+ add_polymer_segments(seg, *cnt, &mut new_segments);
+ }
+ }
+ *segments = new_segments;
+}
+
+fn part1(aoc: &mut aoc::Info) {
+ let (mut state, rules) = parse_input(&aoc.input);
+ for _ in 0..10 {
+ state = grow_polymer(state, &rules);
+ debugln!("{}", state);
+ }
+
+ let charset = build_charset(&state, &rules);
+ let min = charset.chars().map(|c| state.chars().filter(|&c2| c2 == c).count()).min().unwrap();
+ let max = charset.chars().map(|c| state.chars().filter(|&c2| c2 == c).count()).max().unwrap();
+
+ aoc.answer = Some(format!("{}", max - min));
+ aoc.solution = Some("2233");
+}
+
+fn part2(aoc: &mut aoc::Info) {
+ let (state, rules) = parse_input(&aoc.input);
+ let mut segments = gen_segments(&state);
+
+ let charset = build_charset(&state, &rules);
+ let mut charcnt: HashMap<char, usize> = HashMap::new();
+ for c in charset.chars() {
+ let ccnt = state.chars().filter(|&c2| c == c2).count();
+ charcnt.insert(c, ccnt);
+ }
+
+ for i in 0..40 {
+ debugln!("Iter {}", i);
+ for (seg,count) in &segments {
+ debugln!("{} -> {}", seg, count);
+ }
+ grow_polymer_segments(&mut segments, &mut charcnt, &rules);
+ }
+
+ let max = charcnt.iter().max_by_key(|(_,&c)| c).unwrap();
+ let min = charcnt.iter().min_by_key(|(_,&c)| c).unwrap();
+
+ debugln!("max {} -> {}", max.0, max.1);
+ debugln!("min {} -> {}", min.0, min.1);
+
+ aoc.answer = Some(format!("{}", max.1 - min.1));
+}
+
+fn main() {
+ aoc::run(part1, part2);
+}
+
diff --git a/src/14/test1 b/src/14/test1
@@ -0,0 +1,19 @@
+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
+
