path: root/2021/src/bin/day_8.rs

use nom::{
    branch::alt,
    bytes::complete::tag,
    character::complete::{line_ending, space1},
    combinator::{map, map_res, value},
    multi::{many1, separated_list1},
    sequence::tuple,
    IResult,
};
use std::{
    collections::{BTreeMap, BTreeSet},
    fs,
};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let input = fs::read_to_string("inputs/day_8.txt")?;
    let encrypted = parse_encrypted_inputs(&input).unwrap().1;
    let permutations = WiringPermutation::all();

    let unencrypted: Vec<Input> = encrypted
        .into_iter()
        .map(|encrypted_line| {
            for permutation in &permutations {
                if let Ok(input) = encrypted_line.decrypt(&permutation) {
                    return input;
                }
            }
            panic!("Didn't find a solution!")
        })
        .collect();

    let part1_sum: usize = unencrypted
        .iter()
        .map(|input| {
            input
                .plaintext
                .iter()
                .filter(|digit| {
                    digit.value == 1 || digit.value == 4 || digit.value == 7 || digit.value == 8
                })
                .count()
        })
        .sum();
    dbg!(part1_sum);

    let part2_sum: u32 = unencrypted
        .iter()
        .map(|input| {
            input.plaintext[0].value * 1000
                + input.plaintext[1].value * 100
                + input.plaintext[2].value * 10
                + input.plaintext[3].value
        })
        .sum();
    dbg!(part2_sum);
    Ok(())
}

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)]
enum Wire {
    A,
    B,
    C,
    D,
    E,
    F,
    G,
}

impl Wire {
    fn all() -> Vec<Wire> {
        vec![
            Wire::A,
            Wire::B,
            Wire::C,
            Wire::D,
            Wire::E,
            Wire::F,
            Wire::G,
        ]
    }
}

#[derive(Debug)]
struct WiringPermutation {
    mapping: BTreeMap<Wire, Wire>,
}

impl WiringPermutation {
    fn all() -> Vec<WiringPermutation> {
        let all_wires = Wire::all();
        let all_wires_set: BTreeSet<Wire> = all_wires.iter().cloned().collect();
        WiringPermutation::permutations(&all_wires, &all_wires_set)
    }

    fn permutations(
        remaining_starts: &[Wire],
        remaining_ends: &BTreeSet<Wire>,
    ) -> Vec<WiringPermutation> {
        let mut permutations = Vec::new();
        if remaining_starts.is_empty() {
        } else if remaining_starts.len() == 1 {
            for end in remaining_ends {
                let mut permutation = BTreeMap::new();
                permutation.insert(remaining_starts[0], *end);
                permutations.push(WiringPermutation {
                    mapping: permutation,
                });
            }
        } else {
            let start = remaining_starts[0];
            for first_end in remaining_ends {
                let mut inner_remaining_ends = remaining_ends.clone();
                inner_remaining_ends.remove(first_end);
                let inner_permutations =
                    WiringPermutation::permutations(&remaining_starts[1..], &inner_remaining_ends);
                for mut permutation in inner_permutations {
                    permutation.mapping.insert(start, *first_end);
                    permutations.push(permutation);
                }
            }
        }
        permutations
    }
}

#[derive(Debug)]
struct Digit {
    value: u32,
    wires: BTreeSet<Wire>,
}

#[derive(Debug)]
struct Input {
    plaintext: [Digit; 4],
}

#[derive(Debug, thiserror::Error)]
enum WiringError {
    #[error("digit was not a known digit")]
    InvalidDigit,
    #[error("wrong number of numbers")]
    WrongNumberOfNumbers,
}

impl Digit {
    fn new(wires: BTreeSet<Wire>) -> Result<Digit, WiringError> {
        let valid_digits: [BTreeSet<Wire>; 10] = [
            [Wire::A, Wire::B, Wire::C, Wire::E, Wire::F, Wire::G].into(),
            [Wire::C, Wire::F].into(),
            [Wire::A, Wire::C, Wire::D, Wire::E, Wire::G].into(),
            [Wire::A, Wire::C, Wire::D, Wire::F, Wire::G].into(),
            [Wire::B, Wire::C, Wire::D, Wire::F].into(),
            [Wire::A, Wire::B, Wire::D, Wire::F, Wire::G].into(),
            [Wire::A, Wire::B, Wire::D, Wire::E, Wire::F, Wire::G].into(),
            [Wire::A, Wire::C, Wire::F].into(),
            [
                Wire::A,
                Wire::B,
                Wire::C,
                Wire::D,
                Wire::E,
                Wire::F,
                Wire::G,
            ]
            .into(),
            [Wire::A, Wire::B, Wire::C, Wire::D, Wire::F, Wire::G].into(),
        ];

        valid_digits
            .into_iter()
            .position(|digit| digit == wires)
            .map(|pos| Digit {
                value: pos as u32,
                wires,
            })
            .ok_or(WiringError::InvalidDigit)
    }
}

#[derive(Debug)]
struct EncryptedDigit {
    wires: BTreeSet<Wire>,
}

impl EncryptedDigit {
    fn decrypt(&self, permutation: &WiringPermutation) -> Result<Digit, WiringError> {
        let mut fixed_wires = BTreeSet::new();
        for wire in &self.wires {
            fixed_wires.insert(permutation.mapping[wire]);
        }
        Digit::new(fixed_wires)
    }
}

#[derive(Debug)]
struct EncryptedInput {
    digits: [EncryptedDigit; 10],
    ciphertext: [EncryptedDigit; 4],
}

impl EncryptedInput {
    fn decrypt(&self, permutation: &WiringPermutation) -> Result<Input, WiringError> {
        for test_digit in &self.digits {
            let _ = test_digit.decrypt(&permutation)?;
        }

        let plaintext = self
            .ciphertext
            .iter()
            .map(|digit| digit.decrypt(&permutation))
            .collect::<Result<Vec<Digit>, WiringError>>()?;
        Ok(Input {
            plaintext: plaintext
                .try_into()
                .map_err(|_| WiringError::WrongNumberOfNumbers)?,
        })
    }
}

fn parse_encrypted_inputs(input: &str) -> IResult<&str, Vec<EncryptedInput>> {
    separated_list1(line_ending, parse_encrypted_input)(input)
}

fn parse_encrypted_input(input: &str) -> IResult<&str, EncryptedInput> {
    map_res(
        tuple((
            separated_list1(space1, parse_encrypted_digit),
            tag(" | "),
            separated_list1(space1, parse_encrypted_digit),
        )),
        |(digits, _, ciphertext)| {
            let digits = digits
                .try_into()
                .map_err(|_| WiringError::WrongNumberOfNumbers)?;
            let ciphertext = ciphertext
                .try_into()
                .map_err(|_| WiringError::WrongNumberOfNumbers)?;
            let result: Result<EncryptedInput, WiringError> =
                Ok(EncryptedInput { digits, ciphertext });
            result
        },
    )(input)
}

fn parse_encrypted_digit(input: &str) -> IResult<&str, EncryptedDigit> {
    map(many1(parse_wire), |wires| EncryptedDigit {
        wires: wires.into_iter().collect(),
    })(input)
}

fn parse_wire(input: &str) -> IResult<&str, Wire> {
    alt((
        value(Wire::A, tag("a")),
        value(Wire::B, tag("b")),
        value(Wire::C, tag("c")),
        value(Wire::D, tag("d")),
        value(Wire::E, tag("e")),
        value(Wire::F, tag("f")),
        value(Wire::G, tag("g")),
    ))(input)
}