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.

In this article I'll be solving: Advent of code 2021: Day #3.

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[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
}

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 CO₂ scrubber rating. The way to determine both these values is as follows:

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:

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

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₂ 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.

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[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.

17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1