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(())
}