You barely reach the safety of the cave when the whale smashes into the cave mouth, collapsing it. Sensors indicate another exit to this cave at a much greater depth, so you have no choice but to press on.
As your submarine slowly makes its way through the cave system, you notice that the four-digit seven-segment displays in your submarine are malfunctioning; they must have been damaged during the escape. You'll be in a lot of trouble without them, so you'd better figure out what's wrong.
Each digit of a seven-segment display is rendered by turning on or off any of seven segments named a through 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
So, to render a 1, only segments c and f would be turned on; the rest would be off. To render a 7, only segments a, c, and f would be turned on.
The problem is that the signals which control the segments have been mixed up on each display. The submarine is still trying to display numbers by producing output on signal wires a through g, but those wires are connected to segments randomly. Worse, the wire/segment connections are mixed up separately for each four-digit display! (All of the digits within a display use the same connections, though.)
So, you might know that only signal wires b and g are turned on, but that doesn't mean segments b and g are turned on: the only digit that uses two segments is 1, so it must mean segments c and f are meant to be on. With just that information, you still can't tell which wire (b/g) goes to which segment (c/f). For that, you'll need to collect more information.
For each display, you watch the changing signals for a while, make a note of all ten unique signal patterns you see, and then write down a single four digit output value (your puzzle input). Using the signal patterns, you should be able to work out which pattern corresponds to which digit.
For example, here is what you might see in a single entry in your notes:
acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab |
cdfeb fcadb cdfeb cdbaf
(The entry is wrapped here to two lines so it fits; in your notes, it will all be on a single line.)
Each entry consists of ten unique signal patterns, a | delimiter, and finally the four digit output value. Within an entry, the same wire/segment connections are used (but you don't know what the connections actually are). The unique signal patterns correspond to the ten different ways the submarine tries to render a digit using the current wire/segment connections. Because 7 is the only digit that uses three segments, dab in the above example means that to render a 7, signal lines d, a, and b are on. Because 4 is the only digit that uses four segments, eafb means that to render a 4, signal lines e, a, f, and b are on.
Using this information, you should be able to work out which combination of signal wires corresponds to each of the ten digits. Then, you can decode the four digit output value. Unfortunately, in the above example, all of the digits in the output value (cdfeb fcadb cdfeb cdbaf) use five segments and are more difficult to deduce.
For now, focus on the easy digits. Consider this larger example:
be cfbegad cbdgef fgaecd cgeb fdcge agebfd fecdb fabcd edb |
fdgacbe cefdb cefbgd gcbe
edbfga begcd cbg gc gcadebf fbgde acbgfd abcde gfcbed gfec |
fcgedb cgb dgebacf gc
fgaebd cg bdaec gdafb agbcfd gdcbef bgcad gfac gcb cdgabef |
cg cg fdcagb cbg
fbegcd cbd adcefb dageb afcb bc aefdc ecdab fgdeca fcdbega |
efabcd cedba gadfec cb
aecbfdg fbg gf bafeg dbefa fcge gcbea fcaegb dgceab fcbdga |
gecf egdcabf bgf bfgea
fgeab ca afcebg bdacfeg cfaedg gcfdb baec bfadeg bafgc acf |
gebdcfa ecba ca fadegcb
dbcfg fgd bdegcaf fgec aegbdf ecdfab fbedc dacgb gdcebf gf |
cefg dcbef fcge gbcadfe
bdfegc cbegaf gecbf dfcage bdacg ed bedf ced adcbefg gebcd |
ed bcgafe cdgba cbgef
egadfb cdbfeg cegd fecab cgb gbdefca cg fgcdab egfdb bfceg |
gbdfcae bgc cg cgb
gcafb gcf dcaebfg ecagb gf abcdeg gaef cafbge fdbac fegbdc |
fgae cfgab fg bagce
Because the digits 1, 4, 7, and 8 each use a unique number of segments, you should be able to tell which combinations of signals correspond to those digits. Counting only digits in the output values (the part after | on each line), in the above example, there are 26 instances of digits that use a unique number of segments (highlighted above).
In the output values, how many times do digits 1, 4, 7, or 8 appear?
# Python imports
from pathlib import Path
from typing import Callable, Dict, Iterable, List, Tuple
# Paths to data
testpath = Path("day08_test.txt")
datapath = Path("day08_data.txt")
We load corresponding signal wire input and digit segment output data as a tuple. From a quick scan of the test data, we can see that the input wire symbol order doesn't necessarily match the output digit segment order, so we also order the symbols alphabetically for each signal and digit.
def load_input(fpath: Path) -> List[Tuple]:
"""Return input signals and output digits as tuples
:param fpath: Path to data file
The signal/digit string symbols are sorted into
alphabetical order, on loading.
"""
data = [] # holds corresponding tuples of signals and digits
with fpath.open("r") as ifh:
for line in [_.strip() for _ in ifh.readlines() if len(_.strip())]:
signals, digits = line.split(" | ")
signals = ["".join(sorted(list(_))) for _ in signals.split()]
digits = ["".join(sorted(list(_))) for _ in digits.split()]
data.append((signals, digits))
return data
I thought the introduction text was a bit sneaky, as the instruction to focus on just counting individual string lengths to decode digits led me to thinking about a fairly inelegant string of logical inferences for sequentially decoding the signals and digits. That slowed me down a lot.
However, a better way to do this is to recognise that, for each digit (combination of segmnts), the count of differently-lit segements - when compared to all other digits - is unique. The lit segments are:
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
and the count of differently-lit segments (considered digit segments minus the other digit segments, in set arithmetic), when sorted, gives a unique code:
So we can identify each digit by its unique sorted difference to all other numbers in the input signals, using a lookup table/dictionary.
def decode_signals(signals: List[str]) -> Dict:
"""Returns dictionary for decoding digit strings
:param signals: list of input signal strings
"""
# This dictionary is a tally table of sorted counts of
# differences between lit segments. These values are a
# unique code that can identify a digit.
decoder = {(0, 1, 1, 2, 2, 2, 3, 3, 4): "0",
(0, 0, 0, 0, 0, 0, 1, 1, 1): "1",
(0, 1, 1, 1, 1, 2, 3, 3, 4): "2",
(0, 0, 1, 1, 1, 1, 2, 2, 3): "3",
(0, 0, 1, 1, 1, 1, 2, 2, 2): "4",
(0, 0, 0, 1, 1, 2, 2, 3, 4): "5",
(0, 1, 1, 1, 2, 2, 3, 4, 5): "6",
(0, 0, 0, 0, 1, 1, 1, 1, 1): "7",
(1, 1, 1, 2, 2, 2, 3, 4, 5): "8",
(0, 1, 1, 1, 1, 2, 2, 3, 4): "9",
}
signal_dict = {} # output dictionary, keyed by signal
# Identify each signal string
for signal in signals:
sigset = set(signal) # signal as string
others = [set(_) for _ in signals if _ != signal]
# How many differences between the signal's lit segments
# and the lit segments of the other signals are there?
# Count them all, and sort them to get the dictionary key.
distances = tuple(sorted([len(sigset.difference(_)) for _ in others]))
digit = decoder[distances]
signal_dict[signal] = digit
return signal_dict
def decode_digits(digits: List[str], signal_dict: Dict) -> List[str]:
"""Returns the decoded digit input
:param digits: list of digit strings
:param signal_dict: dictionary translating digit strings to numbers
"""
return [signal_dict[_] for _ in digits]
def parse_data(data: Tuple[List[str], List[str]]) -> List[str]:
"""Return input data converted to list of (digit) numbers
:param data: input data - (signals, digits)
"""
outputs = []
for item in data:
outputs.append(decode_digits(item[1], decode_signals(item[0])))
return outputs
So we can count the "easy" digits (1, 4, 7, 8) directly.
def count_easy_digits(data: List[List[int]]) -> int:
"""Return count of digits {1,4,7,8} in data
:param data: decoded digit output
"""
count = 0
for output in data:
count += sum([_ in "1478" for _ in output])
return count
Applying this to the test data:
data = load_input(testpath)
outputs = parse_data(data)
count_easy_digits(outputs)
26
Then to the puzzle data:
data = load_input(datapath)
outputs = parse_data(data)
count_easy_digits(outputs)
272
Through a little deduction, you should now be able to determine the remaining digits. Consider again the first example above:
acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab |
cdfeb fcadb cdfeb cdbaf
After some careful analysis, the mapping between signal wires and segments only make sense in the following configuration:
dddd
e a
e a
ffff
g b
g b
cccc
So, the unique signal patterns would correspond to the following digits:
acedgfb: 8
cdfbe: 5
gcdfa: 2
fbcad: 3
dab: 7
cefabd: 9
cdfgeb: 6
eafb: 4
cagedb: 0
ab: 1
Then, the four digits of the output value can be decoded:
cdfeb: 5
fcadb: 3
cdfeb: 5
cdbaf: 3
Therefore, the output value for this entry is 5353.
Following this same process for each entry in the second, larger example above, the output value of each entry can be determined:
fdgacbe cefdb cefbgd gcbe: 8394
fcgedb cgb dgebacf gc: 9781
cg cg fdcagb cbg: 1197
efabcd cedba gadfec cb: 9361
gecf egdcabf bgf bfgea: 4873
gebdcfa ecba ca fadegcb: 8418
cefg dcbef fcge gbcadfe: 4548
ed bcgafe cdgba cbgef: 1625
gbdfcae bgc cg cgb: 8717
fgae cfgab fg bagce: 4315
Adding all of the output values in this larger example produces 61229.
For each entry, determine all of the wire/segment connections and decode the four-digit output values. What do you get if you add up all of the output values?
I laboured a lot over the logic of this because I dived straight into coding, rather than thinking it through ahead of time. But once I realised the decoder dictionary above was a good approach, we need only change how we calculate the final value.
def calculate_sum(data: List[List[int]]) -> int:
"""Return sum of decoded digit output
:param data: decoded digit output
"""
return sum([int("".join(_)) for _ in data])
Applying this to the test data:
data = load_input(testpath)
outputs = parse_data(data)
calculate_sum(outputs)
61229
And to the puzzle data:
data = load_input(datapath)
outputs = parse_data(data)
calculate_sum(outputs)
21.9 ms ± 7.3 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)