Advent of Code - 2021
This is a solution to Day 8 of Advent of Code 2021.
Day 8 - Seven Segment Search
I gotta be real here, I've read the description half a dozen times and still have no clue what I'm supposed to do or even how to parse and understand the input in my head.
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 ggggSo, 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 bagceBecause 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?
Read input
Once again we have a custom input so we'll need a dedicated transformer function.
from utils import read_input
def transformer(input_line):
notes, output = input_line.split(' | ')
return [notes.split(' '), output.split(' ')]
readings = read_input(8, transformer)
Part 1
There's a lot of lore and explanation in the description that is wholly unnecessary for the first part.
In the first part, we're only interested in output and digits 1, 4, 7 and 8. Since all of those are unique by their length, we can count how many times strings of those lengths appear in the output.
## Amount of different letters in these number displays
one = 2
four = 4
seven = 3
eight = 7
count = 0
for _, output in readings:
for digits in output:
if len(digits) in [one, four, seven, eight]:
count += 1
assert count == 383
print(f'Solution: {count}')
Solution: 383
Part 2
For the second part, the full lore and explanation + a bit more is needed. This took me a few hours to even understand what I was supposed to do but in the end, the solution (at least mine) isn't that complicated.
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 cdbafAfter 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 ccccSo, 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: 1Then, the four digits of the output value can be decoded:
cdfeb: 5 fcadb: 3 cdfeb: 5 cdbaf: 3Therefore, 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: 4315Adding 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?
What I did here is that I picked up a physical notebook and started drawing.
map_to_digits function is where this identification of each sequence to number happens.
First, we already know which ones are for values 1, 4, 7 and 8 from the last section: they all have unique lengths.
Then we have two groups with lengths of 5 and 6. First group is 2, 3 and 5 and the second is 0, 6 and 9.
Let's start by looking at the first group
2: 3: 5:
aaaa aaaa aaaa
. c . c b .
. c . c b .
dddd dddd dddd
e . . f . f
e . . f . f
gggg gggg ggggIf we compare these to a known digit, in this case number 1:
1:
....
. c
. c
....
. f
. f
....We can see that only number 3 overlaps with number 1 in both c and f.
So if we convert the string notations for 2, 3 and 5 to sets and intersect (using set operation & for intersection), we can find that the only intersecting set with length of 2 must be value 3.
We do this same to find out:
- which one from (0, 6, 9) is 6 (by intersecting with 1)
- which one of (2, 5) is 2 (by intersecting with 4)
- and which one of (0, 9) is 9 (by intersecting with a more complex set of (2 & 3 & 4 - 1), which I deduced by drawing a lot of digits to my notebook).
After that, we have all the values. I then create a dictionary with sorted sequences and their corresponding digit values and calculate the output value and sum them.
Sets
Sets are another data structure in Python that comes with some unique features.
A set is a collection of unique items without a set order.
In this puzzle, we create sets from strings or lists:
print(set('abba'))
##{'a', 'b'}
Sets are useful for many things but here we take advantage of set operations that operate on two or more sets:
Intersect
set('abba') & set('advent of code')
##{'a'}
Intersect (&) returns a set of all the common items that can be found on both sets.
Difference
set('abba') - set('b')
##{'a'}
Different (-) returns the first set with all the items from second set removed from it. Here the order of sets is important:
set('b') - set('abba')
## set()
Union
set('abba') | set('cd')
##{'c', 'a', 'b', 'd'}
Union (|) combines all the items from two sets into a new set.
from collections import defaultdict
def map_to_digits(inputs):
values = defaultdict(str)
# Unique by length
values[1] = [value for value in inputs if len(value) == 2][0]
values[4] = [value for value in inputs if len(value) == 4][0]
values[7] = [value for value in inputs if len(value) == 3][0]
values[8] = [value for value in inputs if len(value) == 7][0]
# Common by length
two_or_three_or_five = set(value for value in inputs if len(value) == 5)
zero_or_six_or_nine = set(value for value in inputs if len(value) == 6)
# Find individual values by intersecting sections
values[6] = [s for s in zero_or_six_or_nine if len(set(s) & set(values[1])) == 1][0]
zero_or_nine = zero_or_six_or_nine - set([values[6]])
values[3] = [s for s in two_or_three_or_five if len(set(s) & set(values[1])) == 2][0]
two_or_five = two_or_three_or_five - set([values[3]])
values[2] = [s for s in two_or_five if len(set(s) & set(values[4])) == 2][0]
values[5] = [s for s in two_or_five if len(set(s) & set(values[4])) == 3][0]
values[9] = [s for s in zero_or_nine if len(set(s) & (set(values[2]) & set(values[3]) & set(values[4]) - set(values[1]))) == 1][0]
values[0] = list(zero_or_nine - set([values[9]]))[0]
# Sort the letter segments so they are easier to compare
for k,v in values.items():
values[k] = ''.join(sorted(v))
reverse_mappings = {v: k for k, v in values.items()}
return reverse_mappings
def calculate_output(output, mappings):
output_value = ''
for segment in output:
segment = ''.join(sorted(segment))
digit = mappings[segment]
output_value = f'{output_value}{digit}'
return int(output_value)
outputs_sum = 0
for inputs, output in readings:
mappings = map_to_digits(inputs)
output = calculate_output(output, mappings)
outputs_sum += output
print(f'Solution: {outputs_sum}')
assert outputs_sum == 998900
Solution: 998900
Wrap up
For me, this was not very difficult as programming puzzle but mostly really really difficult to understand what the description meant. I spent a few good hours just trying to understand what the puzzle meant.
Once I figured that part out and draw a lot of digits to my notebook, figuring out the overlapping sections became quite apparent and solving that was not a challenging one for me.
I think this could have been way more fun if the puzzle description was bit easier to understand.
🌟 Earning my 16th star for the year I've set a new personal Advent of Code record, breaking my last year's 15 star achievement.