1 files changed, 262 insertions, 0 deletions
diff --git a/2021/src/bin/day_8.rs b/2021/src/bin/day_8.rs
new file mode 100644
index 0000000..6dc2bed
--- /dev/null
+++ b/2021/src/bin/day_8.rs
@@ -0,0 +1,262 @@
+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)
+}