Advent of code 2021: Day 14
This article is part of a series where I'll be diving head first into the Advent of code 2021. I'll be documenting the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that, I mean I can't look up any other implementations online.
In this article I'll be solving: Advent of code 2021: Day #14.
Part 1
My submarine goes deeper and deeper, and I need to reinforce the structure of the submarine with a polymer. Luckily enough, I have polymerization equipment on board, so I can make some good and sturdy polymers. There’s a template I can use, of which an example looks like this:
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 template value is at the top (NNCB) and the values below indicate which characters can be put in between two consecutive characters. An example: NNCB has three, two consecutive pairs:
NN
NC
CB
All three are in the polymer list and return C, B and H. The final resulting string should look like:
NCNBCHB
^ ^ ^
1 2 3
With this new string, you can do the same trick again. The puzzle specifies that after 10 of these cycles, you’ll get a string where the following characters counts are supposed to be true:
B 1749
C 298
H 161
N 865
If you take the highest value (B) and reduce the lowest value (H), you’ll get a number, what is that number?
The first step I took was writing a bit of code to take care of the simultaneous insert that happens at each cycle:
fn parse(template: &mut String, rules: &HashMap<&str, char>) {
let mut insertions = vec![];
for i in 0..template.len() - 1 {
let key = &template[i..i + 2];
match rules.get(key) {
Some(c) => insertions.insert(0, (i + 1, c)),
None => ()
}
}
for (i, c) in insertions {
template.insert(i, *c);
}
}
The next bit of code was to count the unique characters in said string and return the difference between the highest and lowest character count value:
fn quantify(template: String) -> usize {
let mut counts = HashMap::new();
for c in template.chars() {
let p = counts.entry(c).or_insert(0);
*p += 1
}
let min = counts.values().min().unwrap();
let max = counts.values().max().unwrap();
max - min
}
To execute this code I wrote:
let mut start = String::from("NNCB");
let parse_rules = HashMap::from([
("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')
]);
for _ in 0..10 {
parse(&mut start, &parse_rules);
}
assert_eq!(start.len(), 3073);
assert_eq!(quantify(start), 1588);
For part 1 this works! Solved.
Part 2
In the second part, it turns out that the polymer wasn’t sturdy enough after 10 steps. I should repeat the cycle 40 times to make it really sturdy. The same question as part 1, what is the resulting difference between the highest and lowest value? The problem with running the code for part 1 for 40 cycles is that the string will get 240 big. There’s no way I have that much memory, and Rust (or any other programming language) will throw a tantrum pretty badly. We have to scrap the code from part 1 and come up with something smarter.
The way I wrote this down on paper was like this:
- Make a hash of all possible rules as keys with a starting value of 0.
- Take the initial template and add 1 to each consecutive two character slice. In our example, that would be (
NN NC CB). - Initialize an empty hash, which counts as the previous iteration of the hash I created at step 1.
- Make a loop that goes from 0 till the amount of cycles (-1).
- Each cycle, check the differences between the empty hash from step 3 with the hash from step 1 and add the differences into a separate hash (the code will explain it hopefully).
- Clone the hash from step 1 in its current state and assign it to the hash from step 3.
- Take the hash from step 5 and add the differences to the hash from step 1.
- After the loop has finished, it’s time to count how many rules you’ve touched and therefor how many characters you would have inserted. Oh, and also don’t forget to add the original characters of the template you started out with.
In code this goes something like this:
fn parse(template: &String,
rules: &HashMap<&str, char>,
count: usize) -> u128 {
let keys: Vec<&&str> = rules.keys().collect();
let mut cycle_counts: HashMap<&str, u128> = HashMap::new();
let mut prev_counts: HashMap<&str, u128> = HashMap::new();
// Initialize the HashMap with values of 0
// for each rule key.
for key in &keys {
cycle_counts.insert(*key, 0);
}
// Set some of the initial rule keys to 1
// Things we're going to touch.
for i in 0..template.len() - 1 {
let key = &template[i..i + 2];
if let Some(p) = cycle_counts.get_mut(key) {
*p += 1
}
}
// Because we have done the setup step already in the loop
// above, we can skip one cycle.
for _ in 0..count-1 {
// The next part is where we create a HashMap to
// resolve the differences between the current
// cycle and the previous cycle.
let mut diff = HashMap::new();
for i in 0..keys.len() {
let k = keys[i];
let v = cycle_counts.get(k).unwrap_or(&0);
let prev_v = prev_counts.get(k).unwrap_or(&0);
if v > prev_v {
diff.insert(k, v - prev_v);
}
}
prev_counts = cycle_counts.clone();
// Each difference we've spotted in the step above we should
// attend to and add on top of the newly formed rules:
for (k, v) in &diff {
let p = rules.get(&k as &str).unwrap();
let l = format!("{}{}", k.chars().nth(0).unwrap(), p);
let r = format!("{}{}", p, k.chars().nth(1).unwrap());
if let Some(p) = cycle_counts.get_mut(&l as &str) {
*p += v
}
if let Some(p) = cycle_counts.get_mut(&r as &str) {
*p += v
}
}
}
let mut counts: HashMap<char, u128> = HashMap::new();
// Count the initial characters of "template"
for c in template.chars() {
let p = counts.entry(c).or_insert(0);
*p += 1
}
// All the code below does is add the amount of times
// I hit rule "XY" and count which character receives which
// amount (if I were to add them).
for (k, v) in &cycle_counts {
if let Some(c) = rules.get(k) {
let p = counts.entry(*c).or_insert(0);
*p += v
}
}
let min = counts.values().min().unwrap();
let max = counts.values().max().unwrap();
max - min
}
It works! However, I was fighting a lot with HashMap and annoying Borrow errors [1] more than I was fighting with thinking about it. I’m still thinking if this can be done a bit nicer, and I might come back to this code to improve upon it.
Improvements
I fiddled with the code a bit more, and figured that instead of using a HashMap, I can equally use two arrays to differentiate between cycles. Another thing I improved upon is splitting the giant method into two. Overall, it’s a lot nicer to look at currently.
Sources
[1] Trait Borrow<String> is not implemented for &str
The full solution is available on GitHub.
