67 lines
1.9 KiB
Rust
67 lines
1.9 KiB
Rust
use color_eyre::eyre;
|
|
|
|
|
|
fn most_common_bit(numbers: &Vec<u16>, pos: u16) -> u16 {
|
|
// number of times the bit in question is 1,
|
|
// minus the number of times it's 0
|
|
let mask: u16 = 1 << pos;
|
|
let total: isize = numbers
|
|
.iter()
|
|
.map(|n| if n & mask > 0 {1} else {-1})
|
|
.sum();
|
|
|
|
// if the total is positive, then 1 is more frequent than 0
|
|
if total >= 0 {1} else {0}
|
|
}
|
|
|
|
|
|
fn part1(numbers: &Vec<u16>) -> u64 {
|
|
let gamma = (0..12).reduce(|g, i|
|
|
g | most_common_bit(numbers, i) << i
|
|
).unwrap(); // unwrap is safe here since this iterator will always have elements
|
|
|
|
// epsilon is just the bit inverse of gamma, but since these are really 12-bit numbers
|
|
// we have to clear the 4 spurious 1's that come from inverting the original
|
|
let epsilon = !gamma & (65535 >> 4);
|
|
epsilon as u64 * gamma as u64
|
|
}
|
|
|
|
|
|
fn filter_bit_criteria(numbers: Vec<u16>, bit_pos: u16, bit_value: u16) -> Vec<u16> {
|
|
numbers
|
|
.into_iter()
|
|
.filter(|n| (n >> bit_pos) & 1 == bit_value)
|
|
.collect()
|
|
}
|
|
|
|
|
|
fn part2(numbers: &Vec<u16>) -> u64 {
|
|
let mut oxy = numbers.clone();
|
|
let mut co2 = numbers.clone();
|
|
for pos in (0..12).rev() {
|
|
if oxy.len() > 1 {
|
|
let oxy_bit = most_common_bit(&oxy, pos);
|
|
oxy = filter_bit_criteria(oxy, pos, oxy_bit);
|
|
}
|
|
|
|
if co2.len() > 1 {
|
|
let co2_bit = most_common_bit(&co2, pos) ^ 1; // flip the rightmost bit, giving us the least common instead
|
|
co2 = filter_bit_criteria(co2, pos, co2_bit);
|
|
}
|
|
}
|
|
|
|
// assume both vecs have len == 1 now, since otherwise it means
|
|
// AoC gave us an invalid problem input
|
|
oxy[0] as u64 * co2[0] as u64
|
|
}
|
|
|
|
|
|
|
|
pub fn run(data: &str) -> eyre::Result<(u64, u64)> {
|
|
let mut nums = Vec::new();
|
|
for line in data.lines() {
|
|
nums.push(u16::from_str_radix(line, 2)?);
|
|
}
|
|
|
|
Ok((part1(&nums), part2(&nums)))
|
|
} |