Add day08, 2021

2 files changed, 263 insertions, 0 deletions

diff --git a/2021/rust/day08/Cargo.toml b/2021/rust/day08/Cargo.toml
new file mode 100644
index 0000000..850590f
--- /dev/null
+++ b/2021/rust/day08/Cargo.toml
@@ -0,0 +1,10 @@
+[package]
+name = "day08"
+version = "0.1.0"
+authors = ["cos <cos>"]
+edition = "2021"
+
+[dependencies]
+aoc = { path = "../../../common/rust/aoc" }
+anyhow = "1.0"
+thiserror = "1.0"
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(())
+}