Advent of code 2021: Day 3

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.

Part 1

I am given a file called input in which there is a list of 1000 binary instructions which represent a diagnostic report to the submarine. The first part is to figure out the gamma_rate and the epsilon_rate. To determine the gamma_rate you’d have to take all the numbers vertically and check if it has more 1’s than 0’s, if it does the first bit is a 1 if it doesn’t, it is a 0. The epsilon rate is determined by taking the least common bit value. Repeat until you’re left with 2 n-digit binaries; multiply both binaries in the base10 number system, and you’ll get your answer.

The way I approached this is by first creating a method, which would count the amount of times, I vertically would encounter a ‘1’, like such:

fn totals(binaries: &Vec<&str>) -> Vec<usize> {
let len = binaries.len();
let mut total_ones = vec![0; len];

for bin in binaries {
for i in 0..len {
let c = bin.chars().nth(i);

if c == Some('1') {
total_ones[i] += 1;
}
}
}

total_ones
}

In the first example this returns: [7, 5, 8, 7, 5]. To get the actual rates, I test if the amount of ‘1’s I encounter are higher than the amount of binary readings I have divided by 2 (if more than half are 1’s). If they are, I add 2_u32.pow(n) to gamma_rate, if they aren’t, I add the amount to epsilon_rate. In the end, I multiply both digits.

fn binary_diagnostic(binaries: &Vec<&str>) -> u32 {
let threshold = binaries.len() / 2;
let total_ones = totals(binaries);

let mut gamma_rate = 0;
let mut epsilon_rate = 0;

for (i, t) in total_ones.iter().enumerate() {
let n = 2_u32.pow((total_ones.len() - 1 - i) as u32);

if *t > threshold {
gamma_rate += n;
} else {
epsilon_rate += n;
}
}

gamma_rate * epsilon_rate
}

Part 2

The second part is where things get a bit (pun intended) more tricky. The puzzle asks to calculate the life support rating, which is obtainable from the diagnostics report by finding the oxygen generator rating and the CO2 scrubber rating. The way to determine both these values is as follows:

00100
11110
10110
10111
10101
01111
00111
11100
10000
11001
00010
01010

With the example above; for the oxygen generator rating; the idea is to take all vertical bits and see that there are more 1’s than 0’s. Filter out all the digits that don’t start with a ‘1’. This will result in the list:

11110
10110
10111
10101
11100
10000
11001

In the next row there are more 0’s than 1’s; so the 0’s persist:

10110
10111
10101
10000

And so on. In the end, you should be left with one digit. If a tie is formed; meaning there are an equal amount of 0’s and 1’s, we can say that the concluding binary (or binaries) should be the one which has a ‘1’ at that position.

The CO2 scrubber rating is obtained; and you guessed it; the other way around. You take the least common bits, until one row remains. If a tie is formed, you pick the binary (or binaries) which have a ‘0’ at that position.

There are multiple ways of achieving this, an expensive way - which is what I currently have - and a potentially cheaper way, which I’ll list under improvements. The current expensive way goes something like this:

fn life_support_rating(binaries: &Vec<&str>) -> u32 {
let oxygen_rating = binary_filter(&binaries, '1');
let co2_scrubber_rating = binary_filter(&binaries, '0');

oxygen_rating * co2_scrubber_rating
}

fn binary_filter(binaries: &Vec<&str>, search: char) -> u32 {
let mut filter = binaries.clone();

let reverse = if search >= '1' {
'0'
} else {
'1'
};

for i in 0..binaries.len() {
let threshold = ((filter.len() as f32) * 5.0) as usize;
let total_ones = totals(&filter);

filter = filter
.iter()
.filter(|&&n| {
let total = total_ones[i] * 10;
let bit = if total >= threshold {
search
} else {
reverse
};

n.chars().nth(i) == Some(bit)
})
.map(|n| *n)
.collect();

if filter.len() == 1 {
break;
}
}

}

We take the original binaries, clone them, and keep on filtering till there’s only a single row left in the filter. That’s the one we parse as a u32, and it will correctly give you the answer. The downside of this approach is that for each filtering, I recalculate the total number of ‘1’s that are in the list of binaries. This is obviously a bit redundant, and I believe this can be done a bit cheaper. Regardless, I gained another two stars ⭐️⭐️.

PS: The threshold is multiplied by 5.0 (10.0 / 2.0) to combat situations where an uneven amount of binaries retain in the group. If I didn’t do this, the threshold sometimes incorrectly equaled to the total amount of ‘1’s. This obviously caused incorrect results.

Improvements

Firstly, I refactored the original method by using Rust’s retain() method. I also made search an array of 2 characters, the one to look for and the reverse. There might be something smarter I can do here, but for now this seems okay. The refactored method looks like this:

fn binary_filter(binaries: &Vec<&str>, search: &[char]) -> u32 {
let mut bins = binaries.clone();
let mut j = 0;

while bins.len() > 1 {
let total_ones = totals(&bins);
let threshold = (bins.len() as f32 * 5.0) as usize;

bins.retain(|&bin| {
let bit = if total_ones[j] * 10 >= threshold {
search
} else {
search
};

bin.chars().nth(j) == Some(bit)
});

j += 1
}