Day 8: Seven Segment Search

Day #8 problem description │ Problem input

What an interesting problem! We are asked to deduce the manner in which a computer has been incorrectly hooked up to a seven-segment display (7SD):

A seven-segment display chip with pins showing

We will use the following display schematic, with the segments labeled A–G:

  0:      1:      2:      3:      4:
 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

The computer sends a stream of digits that we see as various patterns of lit segments on the 7SD. The computer has the correct logic to display digits, but its wires to the 7SD got crossed during setup, so the digits it attempts to display end up looking like gibberish to us. But because the computer’s underlying logic still holds, we can still deduce things from its output. For instance, if it lights up only two segments, we know that it is trying to display a 1 (because 1 is the only digit made of exactly two segments), and so the two segments it lit up should be rewired to the two segments CF (although we still don’t know in which order). If it lights up five segments, then it could be trying to display either a 2 (ACDEG), 3 (ACDFG), or 5 (ABDFG). By observing the patterns it lights up, and using our knowledge of how the digits 0–9 should have been displayed, we can deduce the full wiring scheme and how the computer must be rewired to the display in order to function correctly.

The only other wrinkle is we don’t even get to tell the computer which digits to attempt to display; that is entirely up to it. We simply receive a stream of some digits, and from that must deduce the wiring scheme.

The Solution

The strategy is as follows: for each garbled digit we see, record its pattern and the list of candidate digits (those having the same number of segments turned on). Then, by taking set differences and intersections between the patterns seen and their candidates, we can derive more specific information about the rewiring. For instance:

  1. Suppose the computer sends two digits and lights up ABD and AB. ABD only has one candidate, 7 (ACF), because only 7 has three segments turned on. AB only has one candidate, 1 (CF), because only 1 has two segments turned on. Then we take the difference of the displayed segments — ABD − AB = D — and all pairwise differences between their corresponding candidates (just one in this case) — ACF − CF = A — to deduce that D must be rewired to A. We continue this logic, subtracting (say) the map D ➜ A from other display-candidate pairs to narrow them down. We are done when we know the one segment that each segment needs to be rewired to.

  2. Suppose the computer sends ABCDE; its candidates would be 2 (ACDEG), 3 (ACDFG), and 5 (ABDFG). If it then sends DEF, its candidates would be just 7 (ACF). The intersection of the two sent digits is DE. Taking the pairwise intersections between the candidates, and keeping only those with the same length as DE, we see that the candidates for DE are AC and AF. Subtracting D ➜ A from this, we deduce that E must be mapped to either C or F. Subtracting D ➜ A and E ➜ C|F from DEF ➜ ACF, we see that F ➜ C|F as well.

  3. Continuing this way, we can eventually deduce all the mappings.

Setup

First, we model the notion of a digit.

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct Digit {
	segments: [bool; N_SEGMENTS],
	n_on: usize,
}

impl Digit {
	fn new(segments: [bool; N_SEGMENTS]) -> Self {
		Self {
			segments,
			n_on: segments.iter().filter(|&&b| b).count(),
		}
	}

	fn from_str(s: &str) -> Self {
		let mut segments = [false; N_SEGMENTS];
		for c in s.bytes() {
			let i = c - b'a';
			segments[usize::from(i)] = true;
		}
		Self::new(segments)
	}

	fn _bin_op(self, rhs: Self, f: impl Fn(bool, bool) -> bool) -> Self {
		Self::new(self.segments.zip(rhs.segments).map(|(x, y)| f(x, y)))
	}
}

impl std::ops::BitOr for Digit {
	type Output = Self;
	fn bitor(self, rhs: Self) -> Self::Output {
		self._bin_op(rhs, |x, y| x | y)
	}
}

impl std::ops::BitAnd for Digit {
	type Output = Self;
	fn bitand(self, rhs: Self) -> Self::Output {
		self._bin_op(rhs, |x, y| x & y)
	}
}

impl std::ops::Not for Digit {
	type Output = Self;
	fn not(self) -> Self::Output {
		Self::new(self.segments.map(|b| !b))
	}
}

impl From<usize> for Digit {
	fn from(n: usize) -> Self {
		let segments = match n {
			/*
			-----[A, B, C, D, E, F, G]
			*/
			0 => [1, 1, 1, 0, 1, 1, 1],
			1 => [0, 0, 1, 0, 0, 1, 0],
			2 => [1, 0, 1, 1, 1, 0, 1],
			3 => [1, 0, 1, 1, 0, 1, 1],
			4 => [0, 1, 1, 1, 0, 1, 0],
			5 => [1, 1, 0, 1, 0, 1, 1],
			6 => [1, 1, 0, 1, 1, 1, 1],
			7 => [1, 0, 1, 0, 0, 1, 0],
			8 => [1, 1, 1, 1, 1, 1, 1],
			9 => [1, 1, 1, 1, 0, 1, 1],
			_ => panic!("Cannot make digit for n={}", n),
		};
		let segments = segments.map(|i| i != 0);
		Self::new(segments)
	}
}

impl From<Digit> for usize {
	fn from(digit: Digit) -> Self {
		let segments = digit.segments.map(u8::from);
		match segments {
			/*
			[A, B, C, D, E, F, G]
			*/
			[1, 1, 1, 0, 1, 1, 1] => 0,
			[0, 0, 1, 0, 0, 1, 0] => 1,
			[1, 0, 1, 1, 1, 0, 1] => 2,
			[1, 0, 1, 1, 0, 1, 1] => 3,
			[0, 1, 1, 1, 0, 1, 0] => 4,
			[1, 1, 0, 1, 0, 1, 1] => 5,
			[1, 1, 0, 1, 1, 1, 1] => 6,
			[1, 0, 1, 0, 0, 1, 0] => 7,
			[1, 1, 1, 1, 1, 1, 1] => 8,
			[1, 1, 1, 1, 0, 1, 1] => 9,
			_ => panic!("Digit {:?} is not valid", digit),
		}
	}
}
The Algorithm

We repeatedly take the intersection and set-differences between digits, getting a more and more refined mapping until finally we are left with a 1:1 mapping.

use crate::Answer;
use std::collections::{btree_map::Entry as MapEntry, BTreeMap as Map, BTreeSet as Set};

const N_SEGMENTS: usize = 7;
fn get_mapping_from_garbled_digits<D: std::borrow::Borrow<Digit>>(
	garbled_digits: impl Iterator<Item = D>,
) -> Result<Map<Digit, Digit>, Map<Digit, Set<Digit>>> {
	let mut mappings = Map::new();

	{
		let mut grouped_by_n_on = Map::new();
		for n in 0..=9 {
			let digit = Digit::from(n);
			grouped_by_n_on
				.entry(digit.n_on)
				.or_insert_with(Set::new)
				.insert(digit);
		}

		for gd in garbled_digits {
			let gd = *gd.borrow();
			let digits_w_same_n_segments = &grouped_by_n_on[&gd.n_on];
			mappings.insert(gd, digits_w_same_n_segments.clone());
		}
	}

	let identity: &dyn Fn(Digit) -> _ = &(|x| x);
	let bitwise_not: &dyn Fn(Digit) -> _ = &(|x| !x);

	loop {
		let mut new_mappings = Map::new();

		for (i, (&garbled1, choices1)) in mappings.iter().enumerate() {
			for (&garbled2, choices2) in mappings.iter().skip(i + 1) {
				for (op1, op2) in [
					(identity, identity),
					(identity, bitwise_not),
					(bitwise_not, identity),
				] {
					let new_garbled = op1(garbled1) & op2(garbled2);

					if new_garbled.n_on == 0 {
						continue;
					}

					let mut new_good_candidates = Set::new();
					for &good_digit1 in choices1 {
						for &good_digit2 in choices2 {
							let candidate = op1(good_digit1) & op2(good_digit2);
							if candidate.n_on == new_garbled.n_on {
								new_good_candidates.insert(candidate);
							}
						}
					}

					match new_mappings.entry(new_garbled) {
						MapEntry::Vacant(v) => {
							v.insert(new_good_candidates);
						}
						MapEntry::Occupied(mut o) => {
							o.insert(o.get() & &new_good_candidates);
						}
					}
				}
			}
		}

		// Remove all keys that can be written as the disjoint-bitwise-or of two other
		// keys, as they're redundant. This means if e.g., A and BC are present, then
		// remove ABC. But if only AB and BC are present, then do *not* remove ABC (as AB
		// and BC are not disjoint)
		let mut redundant_keys = Set::new();
		let new_garbled_keys = new_mappings.keys().copied().collect::<Set<_>>();
		for (i, &garbled1) in new_garbled_keys.iter().enumerate() {
			for &garbled2 in new_garbled_keys.iter().skip(i + 1) {
				if (garbled1 & garbled2).n_on != 0 {
					continue;
				}
				let segment_union = garbled1 | garbled2;
				if new_garbled_keys.contains(&segment_union) {
					redundant_keys.insert(segment_union);
				}
			}
		}

		for k in &redundant_keys {
			new_mappings.remove(k);
		}

		if mappings.len() == N_SEGMENTS && mappings.values().all(|m| m.len() == 1) {
			return Ok(mappings
				.into_iter()
				.map(|(k, v)| (k, v.iter().next().copied().unwrap()))
				.collect());
		} else if mappings == new_mappings {
			return Err(mappings);
		}

		mappings = new_mappings;
	}
}

fn apply_mapping_to_garbled_digit(mapping: &Map<Digit, Digit>, garbled_digit: Digit) -> usize {
	let mut result = Digit::new([false; 7]);
	for (&k, &v) in mapping {
		if (garbled_digit & k).n_on > 0 {
			result = result | v;
		}
	}
	result.into()
}

fn read_input(input: &str) -> Vec<(Vec<Digit>, Vec<Digit>)> {
	fn whitespace_sepd_strs_to_digits(strs: &str) -> Vec<Digit> {
		strs.trim()
			.split_ascii_whitespace()
			.map(Digit::from_str)
			.collect()
	}
	input
		.lines()
		.filter_map(|line| {
			let line = line.trim();
			if line.is_empty() {
				return None;
			}
			let mut in_out = line.split('|');
			let in_digits = whitespace_sepd_strs_to_digits(in_out.next()?);
			let out_digits = whitespace_sepd_strs_to_digits(in_out.next()?);
			Some((in_digits, out_digits))
		})
		.collect()
}

fn translate_line_to_digits<D: std::borrow::Borrow<Digit>>(
	idod: (impl Iterator<Item = D>, impl Iterator<Item = D>),
) -> Option<Vec<usize>> {
	let (in_digits, out_digits) = idod;

	let mapping = get_mapping_from_garbled_digits(in_digits).ok()?;
	Some(
		out_digits
			.map(|d| apply_mapping_to_garbled_digit(&mapping, *d.borrow()))
			.collect(),
	)
}

fn ans_for_input(input: &str) -> Answer<usize, usize> {
	let in_out_lines = read_input(input);

	let output_digits = in_out_lines
		.iter()
		.map(|(in_d, out_d)| translate_line_to_digits((in_d.iter(), out_d.iter())))
		.collect::<Option<Vec<_>>>()
		.unwrap();
	(8, (pt1(output_digits.iter()), pt2(output_digits.iter()))).into()
}

pub fn ans() -> Answer<usize, usize> {
	ans_for_input(include_str!("input.txt"))
}

Part 1

fn pt1<Nums: AsRef<[usize]>>(out_digits: impl Iterator<Item = Nums>) -> usize {
	out_digits
		.map(|v| {
			v.as_ref()
				.iter()
				.filter(|&n| [1, 4, 7, 8].contains(n))
				.count()
		})
		.sum()
}

Part 2

fn pt2<Nums: AsRef<[usize]>>(out_digits: impl Iterator<Item = Nums>) -> usize {
	out_digits
		.map(|v| {
			v.as_ref()
				.iter()
				.rev()
				.enumerate()
				.map(|(pow10, &val)| val * 10_usize.pow(u32::try_from(pow10).unwrap()))
				.sum::<usize>()
		})
		.sum()
}

This page was built using Antora with a theme forked from the default UI. Search is powered by Lunr.

The source code for this UI is licensed under the terms of the MPL-2.0 license.