Today’s problem was a bit more complex, and required basic knowledge of mathematics (euclidian division or bitwise operators).

Input

A list of 1000 12-bit binary numbers is given. A conversion from Strings to unsigned integers is done, with the from_str_radix() function.

Part 1

For this first part, we must figure out, for each bit position, whether 0 or 1 is the most common. The most common bit is injected in a variable called gamma, and the least common in the epsilon variable.

In order to compute the i-th bit of a number n (starting from the least significant), I used the formula :

bit i(n)=nmod2 i+1/2 i\begin{aligned} bit_i(n) = n mod 2^{i+1} / 2^i \end{aligned}

but using bitwise operators, with the formula

bit i(n)=(n&2 i)/2 i\begin{aligned} bit_i(n) = (n \& 2^i) / 2^i \end{aligned}

was probably more clever.

The counting is simply done with iterator functions filter() and count().

pub fn zeros_count(numbers: &Vec<u64>, bit: u32) -> usize {
    numbers.iter()
        .filter(|&n| (n % 2u64.pow(bit + 1)) / 2u64.pow(bit) == 0)
        .count()
}

pub fn ones_count(numbers: &Vec<u64>, bit: u32) -> usize {
    numbers.iter()
        .filter(|&n| (n % 2u64.pow(bit + 1)) / 2u64.pow(bit) == 1)
        .count()
}

pub fn solve_part1(input: &Vec<String>) -> u64 {
    let mut gamma = 0;
    let mut epsilon = 0;

    let length = input.get(0).unwrap().len() as u32;
    let numbers = binary_numbers(input);

    for bit in 0..length {
        let zeros = zeros_count(&numbers, bit);
        let ones = ones_count(&numbers, bit);

        if ones > zeros {
            gamma += 2u64.pow(bit);
        }
        else {
            epsilon += 2u64.pow(bit);
        }
    }

    gamma * epsilon 
}

Part 2

In this part, we compute 2 new variables called “oxygen generator rating” and “CO2 scrubber rating”. We have to select a number in the input list that fulfills a given condition.

For both variables we start from the most significant bit, and we select numbers that have the most common bit value (for oxygen generator) or the least common bit (for the CO2 scrubbing). We repeat the process with the next bit, until only one number remains.

For this part, we reuse the functions zeros_count() and one_count() defined in the first part, and we add a select_numbers() function

pub fn select(numbers: &Vec<u64>, bit: u32, bit_value: u64) -> Vec<u64> {
    numbers.iter().cloned()
        .filter(|&n| (n % 2u64.pow(bit + 1)) / 2u64.pow(bit) == bit_value)
        .collect()
}

At the end of the main function, we check if there is only one selected number for both variables. Otherwise, the function panics, as the final result (product of oxygen generator rating and CO2 scrubber rating) can’t be calculated.

pub fn solve_part2(input: &Vec<String>) -> u64 {
    let length = input.get(0).unwrap().len() as u32;
    let mut bit = length - 1;

    let mut o2_numbers = binary_numbers(input);
    let mut co2_numbers = binary_numbers(input);

    loop {
        if ones_count(&o2_numbers, bit) >= zeros_count(&o2_numbers, bit) {
            o2_numbers = select(&o2_numbers, bit, 1);
        }
        else {
            o2_numbers = select(&o2_numbers, bit, 0);
        }
        if bit == 0 || o2_numbers.len() == 1 {
            break;
        }
        bit -= 1;
    }

    bit = length - 1;
    loop {
        if ones_count(&co2_numbers, bit) >= zeros_count(&co2_numbers, bit) {
            co2_numbers = select(&co2_numbers, bit, 0);
        }
        else {
            co2_numbers = select(&co2_numbers, bit, 1);
        }
        if bit == 0 || co2_numbers.len() == 1 {
            break;
        }
        bit -= 1;
    }

    if o2_numbers.len() == 1 && co2_numbers.len() == 1 {
        o2_numbers.get(0).unwrap() * co2_numbers.get(0).unwrap()
    }
    else {
        panic!("Non-unique O2 or CO2 numbers");
    }
}

I finshed the part 1 in 50 minutes (taking into account that I started 20 minutes late), and I spent the same amount of time for the part 2.