diff options
Diffstat (limited to '2021/rust/day08/src/main.rs')
| -rw-r--r-- | 2021/rust/day08/src/main.rs | 253 |
1 files changed, 253 insertions, 0 deletions
diff --git a/2021/rust/day08/src/main.rs b/2021/rust/day08/src/main.rs new file mode 100644 index 0000000..f4e44bd --- /dev/null +++ b/2021/rust/day08/src/main.rs @@ -0,0 +1,253 @@ +use { + anyhow::{ + anyhow, + Context, + Result, + }, + std::{ + collections::HashSet, + env::args, + fs::File, + hash::{ + Hash, + Hasher, + }, + io::{ + BufRead, + BufReader, + }, + path::Path, + str::FromStr, + }, + thiserror::Error, +}; + +#[derive(Error, Debug)] +enum SegmentError { + #[error("Invalid segment character")] + Invalid(char), +} + +type SegmentResult<T> = std::result::Result<T, SegmentError>; + +#[derive(Clone,Debug,Eq,Hash,Ord,PartialEq,PartialOrd)] +enum Segment { A, B, C, D, E, F, G, } + +#[derive(Clone,Debug,Eq)] +struct Digit { + inner: HashSet<Segment>, +} + +// https://stackoverflow.com/q/36562419/hashset-as-key-for-other-hashset +impl Hash for Digit { + fn hash<H>(&self, state: &mut H) where H: Hasher { + let mut a: Vec<&Segment> = self.inner.iter().collect(); + a.sort(); + for s in a.iter() { + s.hash(state); + } + } + +} + +impl PartialEq for Digit { + fn eq(&self, other: &Digit) -> bool { + self.inner == other.inner + } +} + +impl FromStr for Digit { + type Err = SegmentError; + + fn from_str(s: &str) -> Result<Self, Self::Err> { + let inner = s.chars().map(|c| match c { + 'a' => Ok(Segment::A), + 'b' => Ok(Segment::B), + 'c' => Ok(Segment::C), + 'd' => Ok(Segment::D), + 'e' => Ok(Segment::E), + 'f' => Ok(Segment::F), + 'g' => Ok(Segment::G), + _ => Err(SegmentError::Invalid(c)), + }).collect::<SegmentResult<HashSet<Segment>>>()?; + Ok(Self { + inner, + }) + } +} + +#[derive(Debug)] +struct Signals { + input: Vec<Digit>, + output: Vec<Digit>, +} + +fn read_signals<T: AsRef<Path>>(filename: T) -> Result<Vec<Signals>> { + let reader = BufReader::new(File::open(filename)?); + + reader.lines().map( + |row| { + let r = row?; + let (left, right) = r.split_once('|') + .ok_or_else(|| anyhow!("Missing separator: {}", r))?; + let input = left.split_whitespace().map(|n| n.parse() + .map_err(|err| anyhow!("{}", err))).collect::<Result<Vec<Digit>>>()?; + let output = right.split_whitespace().map(|n| n.parse() + .map_err(|err| anyhow!("{}", err))).collect::<Result<Vec<Digit>>>()?; + Ok(Signals {input, output}) + } + ).collect() +} + +fn part1<'a, I: IntoIterator<Item = &'a Signals>>(signals: I) -> Result<usize> { + // aaaa .... aaaa aaaa .... + // b c . c . c . c b c + // b c . c . c . c b c + // .... .... dddd dddd dddd + // e f . f e . . f . f + // e f . f e . . f . f + // gggg .... gggg gggg .... + // + // 5: 6: 7: 8: 9: + // aaaa aaaa aaaa aaaa aaaa + // b . b . . c b c b c + // b . b . . c b c b c + // dddd dddd .... dddd dddd + // . f e f . f e f . f + // . f e f . f e f . f + // gggg gggg .... gggg gggg + // 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 + let segment_count = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]; + let count = signals.into_iter().map(|s| { + let c: usize = s.output.iter().map(|d| { + match d.inner.len() { + v if v == segment_count[1] || + v == segment_count[4] || + v == segment_count[7] || + v == segment_count[8] => 1, + _ => 0, + } + }).sum(); + c + }).sum(); + + Ok(count) +} + +fn find_digits(input: &[Digit]) -> Result<Vec<Option<Digit>>> { + let segment_count = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]; + + let mut digits: Vec<Option<Digit>> = vec![None; 10]; + let mut unknown = HashSet::new(); + for digit in input.iter() { + unknown.insert(digit.clone()); + } + for unique_segments in [1, 4, 7, 8].into_iter() { + // Digit 1 is found by unique number of segments, as in part 1. + // Digit 4 is found by unique number of segments, as in part 1. + // Digit 7 is found by unique number of segments, as in part 1. + // Digit 8 is found by unique number of segments, as in part 1. + unknown.clone().into_iter().map(|d| if d.inner.len() == segment_count[unique_segments] { + unknown.remove(&d); + digits[unique_segments] = Some(d); + }).last(); + } + // Digit 3 is the only five segmented superset of Digit 1 (and Digit 7). + digits[3] = unknown.clone().into_iter().filter(|d| { + if d.inner.len() == 5 { + if let Some(one) = &digits[1] { + if d.inner.is_superset(&one.inner) { + unknown.remove(d); + return true; + } + } + } + false + }).last(); + // Digit 0 is Digit 8 - (Digit 3 & (Digit 4 - Digit 1)). + digits[0] = unknown.clone().into_iter().filter(|d| { + if let (Some(one), Some(three), Some(four), Some(eight)) = + (&digits[1], &digits[3], &digits[4], &digits[8]) + { + let set_a = four.inner.difference(&(one.inner)).cloned().collect(); + let set_b = three.inner.intersection(&set_a).cloned().collect(); + let set_c = eight.inner.difference(&set_b).cloned().collect(); + if d.inner == set_c { + unknown.remove(d); + return true + } + } + false + }).last(); + digits[9] = unknown.clone().into_iter().filter(|d| { + if d.inner.len() == 6 { + if let Some(three) = &digits[3] { + if d.inner.is_superset(&three.inner) { + unknown.remove(d); + return true + } + } + } + false + }).last(); + // Digit 6 is the only remaining six segmented unknown. + digits[6] = unknown.clone().into_iter().filter(|d| if d.inner.len() == 6 { + unknown.remove(d); + true + } else { + false + }).last(); + // Digit 2 is the one with zero overlap with the difference of Digit 4 - Digit 3. + digits[2] = unknown.clone().into_iter().filter(|d| { + if let (Some(three), Some(four)) = (&digits[3], &digits[4]) { + let set_a = four.inner.difference(&(three.inner)).cloned().collect(); + let set_b: HashSet<Segment> = d.inner.intersection(&set_a).cloned().collect(); + if set_b.is_empty() { + unknown.remove(d); + return true + } + } + false + }).last(); + // Digit 5 is the remaining one. + digits[5] = unknown.into_iter().next(); + Ok(digits) +} + +fn decode_output(output: &[Digit], digits: &[Option<Digit>]) -> Result<usize> { + output.iter().fold(Ok(0), |acc, d| { + let mut acc_val = acc.expect("Bug in decode_output()"); + acc_val *= 10; + (0..=9).filter_map(|n| + match digits.get(n)? { + Some(i) if i.inner == d.inner => Some(acc_val + n), + _ => None, + } + ).next().ok_or(anyhow!("No digit matched")) + }) +} + +fn part2<'a, I: IntoIterator<Item = &'a Signals>>(signals: I) -> Result<usize> { + let res: usize = signals.into_iter().map(|signal| { + let digits = find_digits(&signal.input)?; + decode_output(&signal.output, &digits) + }).collect::<Result<Vec<_>>>()?.into_iter().sum(); + + Ok(res) +} + +fn main() -> Result<()> { + let ( do_part_1, do_part_2 ) = aoc::do_parts(); + + let filename = args().nth(1).ok_or(anyhow!("Missing signals filename"))?; + let signals = read_signals(filename).context("Could not read signals")?; + if do_part_1 { + let solution = part1(&signals).context("No solution for part 1")?; + println!("Part1, solution found to be: {}", solution); + } + if do_part_2 { + let solution = part2(&signals).context("No solution for part 2")?; + println!("Part2, solution found to be: {}", solution); + } + Ok(()) +} |