From 57870e0429cbfa85b08d891900ca7999d6ae7b23 Mon Sep 17 00:00:00 2001 From: cos Date: Fri, 3 Dec 2021 10:23:40 +0100 Subject: Add day03, 2021 --- 2021/rust/Cargo.toml | 2 +- 2021/rust/day03/Cargo.toml | 10 +++ 2021/rust/day03/src/main.rs | 178 ++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 189 insertions(+), 1 deletion(-) create mode 100644 2021/rust/day03/Cargo.toml create mode 100644 2021/rust/day03/src/main.rs diff --git a/2021/rust/Cargo.toml b/2021/rust/Cargo.toml index 8609abe..ac7f9ee 100644 --- a/2021/rust/Cargo.toml +++ b/2021/rust/Cargo.toml @@ -2,7 +2,7 @@ members = [ "day01", "day02", -# "day03", + "day03", # "day04", # "day05", # "day06", diff --git a/2021/rust/day03/Cargo.toml b/2021/rust/day03/Cargo.toml new file mode 100644 index 0000000..9922792 --- /dev/null +++ b/2021/rust/day03/Cargo.toml @@ -0,0 +1,10 @@ +[package] +name = "day03" +version = "0.1.0" +edition = "2021" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] +aoc = { path = "../../../common/rust/aoc" } +anyhow = "1.0" diff --git a/2021/rust/day03/src/main.rs b/2021/rust/day03/src/main.rs new file mode 100644 index 0000000..6a2934e --- /dev/null +++ b/2021/rust/day03/src/main.rs @@ -0,0 +1,178 @@ +use { + anyhow::{ + anyhow, + Context, + Result, + }, + std::{ + cmp::Ordering, + env::args, + fs::File, + io::{ + BufRead, + BufReader, + }, + path::Path, + }, +}; + +type DiagnosticValue = usize; + +struct Diagnostics { + bits: usize, + values: Vec, +} + +fn read_input>(filename: T) -> Result { + let reader = BufReader::new(File::open(filename)?); + let mut bit_count = None; + let mut values = Vec::new(); + for row in reader.lines() { + let string = row?; + if bit_count.is_none() { + bit_count = Some(string.len()); + } + let value = usize::from_str_radix(&string, 2) + .map_err(|err| anyhow!("Could not parse input: {}", err))?; + values.push(value); + } + + let bits = bit_count.ok_or(anyhow!(""))?; + Ok(Diagnostics { + bits, + values, + }) +} + +fn find_most_common_bit<'a, I: IntoIterator + Copy>( + input: I, position: usize) -> Ordering +{ + let input_size = (&input).into_iter().count(); + + let mut bit_sum = 0; + for value in input { + let shifted = value >> position; + bit_sum += shifted & 1; + } + + match bit_sum { + _ if bit_sum > (input_size - bit_sum) => Ordering::Greater, + #[allow(clippy::overflow_check_conditional)] // False positive. input_size always >= bit_sum + _ if bit_sum < (input_size - bit_sum) => Ordering::Less, + _ => Ordering::Equal, + } +} + +fn find_gamma_epsilon<'a, I: IntoIterator + Copy>(input: I) -> + (DiagnosticValue, DiagnosticValue) +{ + let diagnostic_count = &input.into_iter().count(); + let mut gamma = 0; + let mut bit_position = 0; + let mut is_done = false; + while !is_done { + is_done = true; + let mut bit_sum = 0; + for diagnostic in input { + let shifted = diagnostic >> bit_position; + bit_sum += shifted & 1; + if shifted >> 1 != 0 { + is_done = false; + } + } + if bit_sum > diagnostic_count / 2 { + gamma += 1 << bit_position; + } + bit_position += 1; + } + + let epsilon = (!gamma) ^ ((!0) << bit_position); + (gamma, epsilon) +} + +fn find_oxygen_generator<'a, I>(input: I, size: usize) -> Option + where I: IntoIterator + Copy +{ + let mut candidates: Vec<_> = input.into_iter().map(|v| v.to_owned()).collect(); + for bit_shift in (0..size).rev() { + let most_common_bit = find_most_common_bit(&candidates, bit_shift); + let mut keep = Vec::new(); + for candidate in &candidates { + let bit_value = (*candidate >> bit_shift) & 1; + match (most_common_bit, bit_value) { + (Ordering::Greater, 1) | + (Ordering::Less, 0) | + (Ordering::Equal, 1) => keep.push(*candidate), + (Ordering::Greater, 0) | + (Ordering::Less, 1) | + (Ordering::Equal, 0) => { }, + (_, _) => panic!("Invalid bit value"), + } + } + candidates = keep; + if (&candidates).len() == 1 { + return candidates.pop(); + } + } + None +} + +fn find_co2_scrubber<'a, I>(input: I, size: usize) -> Option + where I: IntoIterator + Copy +{ + let mut candidates: Vec<_> = input.into_iter().map(|v| v.to_owned()).collect(); + for bit_shift in (0..size).rev() { + let most_common_bit = find_most_common_bit(&candidates, bit_shift); + let mut keep = Vec::new(); + for candidate in &candidates { + let bit_value = (*candidate >> bit_shift) & 1; + match (most_common_bit, bit_value) { + (Ordering::Greater, 0) | + (Ordering::Less, 1) | + (Ordering::Equal, 0) => keep.push(*candidate), + (Ordering::Greater, 1) | + (Ordering::Less, 0) | + (Ordering::Equal, 1) => { }, + (_, _) => panic!("Invalid bit value"), + } + } + candidates = keep; + if (&candidates).len() == 1 { + return candidates.pop(); + } + } + None +} + +fn part1(input: &Diagnostics) -> Result<(DiagnosticValue, DiagnosticValue)> { + let (gamma, epsilon) = find_gamma_epsilon(&input.values); + + Ok((epsilon, gamma)) +} + +fn part2(input: &Diagnostics) -> Result<(DiagnosticValue, DiagnosticValue)> { + let oxygen_generator = find_oxygen_generator(&input.values, input.bits) + .ok_or(anyhow!("Could not find diagnostics for Oxygen generator."))?; + let co2_scrubber = find_co2_scrubber(&input.values, input.bits) + .ok_or(anyhow!("Could not find diagnostics for CO2 scrubber."))?; + + Ok((oxygen_generator, co2_scrubber)) +} + +fn main() -> Result<()> { + let ( do_part_1, do_part_2 ) = aoc::do_parts(); + + let filename = args().nth(1).ok_or(anyhow!("Missing input filename"))?; + let input = read_input(filename).context("Could not read input")?; + if do_part_1 { + let (epsilon, gamma) = part1(&input).context("No solution for part 1")?; + let solution = epsilon * gamma; + println!("Part1, epsilon: {}, gamma: {}. Door answer: {}", epsilon, gamma, solution); + } + if do_part_2 { + let (oxygen, co2) = part2(&input).context("No solution for part 1")?; + let solution = oxygen * co2; + println!("Part2, O₂ code: {}, CO₂ code: {}. Door answer: {}", oxygen, co2, solution); + } + Ok(()) +} -- cgit v1.2.3