Advent of Code 2021 - Day 3: Binary Diagnostic

binary_diagnostic.rs

// bits = width in bits of the input data

fn power_consumption(numbers: &[u64], bits: usize) -> u64 {
    let gamma = (0..bits).fold(0, |gamma, bit| {
        let (ones, zeros) = count(numbers, bit);
        gamma | if ones > zeros { 1 << bit } else { 0 }
    });

    gamma * (!gamma & ((1 << bits) - 1))
}

fn count(numbers: &[u64], bit: usize) -> (u64, u64) {
    let mask = 1 << bit;

    numbers.iter().fold((0, 0), |(ones, zeros), &number| {
        if number & mask != 0 {
            (ones + 1, zeros)
        } else {
            (ones, zeros + 1)
        }
    })
}

fn life_support_rating(numbers: &[u64], bits: usize) -> u64 {
    let oxygen_generator_rating = find_rating(numbers, bits, true);
    let co2_scrubber_rating = find_rating(numbers, bits, false);

    oxygen_generator_rating * co2_scrubber_rating
}

fn find_rating(numbers: &[u64], bits: usize, by_ones: bool) -> u64 {
    let mut numbers = numbers.to_vec();

    for bit in (0..bits).rev() {
        let (ones, zeros) = count(&numbers, bit);

        let by_one = match ones.cmp(&zeros) {
            Ordering::Less => !by_ones,
            Ordering::Equal => by_ones,
            Ordering::Greater => by_ones,
        };

        numbers = numbers
            .into_iter()
            .filter(|&number| ((number & (1 << bit)) != 0) == by_one)
            .collect();

        if numbers.len() == 1 {
            return numbers[0];
        }
    }

    panic!("Failed to find rating");
}