summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--2021/rust/Cargo.toml2
-rw-r--r--2021/rust/day08/Cargo.toml10
-rw-r--r--2021/rust/day08/src/main.rs253
3 files changed, 264 insertions, 1 deletions
diff --git a/2021/rust/Cargo.toml b/2021/rust/Cargo.toml
index 49ed1d7..3f73cb5 100644
--- a/2021/rust/Cargo.toml
+++ b/2021/rust/Cargo.toml
@@ -7,7 +7,7 @@ members = [
"day05",
"day06",
"day07",
-# "day08",
+ "day08",
# "day09",
# "day10",
# "day11",
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(())
+}