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 #3.

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[0].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
}
```

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 CO_{2} 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 CO_{2} 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[0].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;
}
}
u32::from_str_radix(filter[0], 2).unwrap()
}
```

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.

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[1]
} else {
search[0]
};
bin.chars().nth(j) == Some(bit)
});
j += 1
}
u32::from_str_radix(bins[0], 2).unwrap()
}
```

This is a lot cleaner than it was before. I can also get rid of `total`

; because it currently counts the ‘1’s for each vertical row. However, we’re only interested in the amount of ‘1’s at position `j`

. With some filter magic `total_ones`

can also be written as such:

```
let total_ones = bins
.iter()
.filter(|&&b| b.chars().nth(j) == Some('1'))
.count();
```

I don’t think it can be more optimized than this. The performance is already pretty great, especially because it only has to go over 1000 strings, which is not that many.

**
The full solution is available on
GitHub.
**