From 6d72191e2ce5d423ca03c894d2dad1d3061bd4f3 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Tue, 19 Apr 2022 20:27:29 +0200 Subject: Refile for merging repos --- 2021/src/bin/day_8.rs | 262 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 262 insertions(+) create mode 100644 2021/src/bin/day_8.rs (limited to '2021/src/bin/day_8.rs') 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> { + 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 = 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 { + vec![ + Wire::A, + Wire::B, + Wire::C, + Wire::D, + Wire::E, + Wire::F, + Wire::G, + ] + } +} + +#[derive(Debug)] +struct WiringPermutation { + mapping: BTreeMap, +} + +impl WiringPermutation { + fn all() -> Vec { + let all_wires = Wire::all(); + let all_wires_set: BTreeSet = all_wires.iter().cloned().collect(); + WiringPermutation::permutations(&all_wires, &all_wires_set) + } + + fn permutations( + remaining_starts: &[Wire], + remaining_ends: &BTreeSet, + ) -> Vec { + 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, +} + +#[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) -> Result { + let valid_digits: [BTreeSet; 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, +} + +impl EncryptedDigit { + fn decrypt(&self, permutation: &WiringPermutation) -> Result { + 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 { + for test_digit in &self.digits { + let _ = test_digit.decrypt(&permutation)?; + } + + let plaintext = self + .ciphertext + .iter() + .map(|digit| digit.decrypt(&permutation)) + .collect::, WiringError>>()?; + Ok(Input { + plaintext: plaintext + .try_into() + .map_err(|_| WiringError::WrongNumberOfNumbers)?, + }) + } +} + +fn parse_encrypted_inputs(input: &str) -> IResult<&str, Vec> { + 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 = + 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) +} -- cgit v1.2.3