Add day03, 2021

3 files changed, 189 insertions, 1 deletions

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<DiagnosticValue>,
+}
+
+fn read_input<T: AsRef<Path>>(filename: T) -> Result<Diagnostics> {
+    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<Item = &'a DiagnosticValue> + 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<Item = &'a DiagnosticValue> + 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<DiagnosticValue>
+    where I: IntoIterator<Item = &'a DiagnosticValue> + 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<DiagnosticValue>
+    where I: IntoIterator<Item = &'a DiagnosticValue> + 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(())
+}