Module advent_of_code_2021::day_8 [−][src]
Expand description
This is my solution for Advent of Code - Day 8 - Seven Segment Search
Today had a lot of description for a relatively simple part one, that seemed to be leading into a much harder part two. The puzzle input is a sequence of lines in two parts, ten unique digits (i.e. 0-9) in a random order, then 4 other digits. But each digit is shown as the set of bars they light up on a digital display, each bar represented by a letter a-g, in a random order. To further complicate things, the wires that light up the bars have got swapped around - and the actual bars that light up is only consistent for each line.
To show some examples:
Wiring correct - Order: a,b,c,d,e,f,g
1: 4: 8: Sets shown when labelled in reading order
.... .... aaaa 1: cf, fc
. c b c b c 4: bcfd, cdbf, ...
. c b c b c 8: abcdefg, gfacbed, ...
.... dddd dddd
. f . f e f
. f . f e f
.... .... gggg
Wiring mixed up - Order: e,c,d,g,f,a,b
1: 4: 8: Example sets that could be shown when labelled in reading order
.... .... eeee 1: be, eb
c . c d c d 4: bceg, gcbe, ...
c . c d c d 8: abcdefg, gfacbed, ... // doesn't change all are lit up
.... .... gggg
f . f . f a
f . f . f a
.... bbbb bbbbThe overall puzzle seemed to be leaning towards working out what numbers were showing on each line. For part one it was noted that digits 1, 4, 7 and 8 each light up a unique number of bars. Due to this they can be identified by just counting the bars in the set. After all that preamble the challenge for part one was simple - count the number of digits in the output strings that are known to be 1, 4, 7, or 8 by their length.
One way to solve this would be to just discard the set of ten unique combinations, reduce the
outputs to their sizes filter out those of size 2 (1s), size 3 (7s), size 4 (4s), and size 7
(8s). I felt this would be wasted work however as for part two I was going to need to identify
which of the digits was which. I instead decided to implement an internal representation of each
line as a Display that had a map of the character set to the integer digit, plus the unknown
digits for later analysis. To implement the minimum needed for part one, just the map entries
for 1, 4, 7 and 8 would need to be created. The solution for part one is to filter the output
lists to those that map to 1, 4, 7, or 8 in the digit map, count each of those and sum those
counts for all displays. count_unique implements this.
The key piece of functionality, where all the hard work for part one and two is done is
parse_line. This takes the string line, and builds that map of known character sets to
integer digits. I’d originally implemented the digits as HashSet<char>s. It needs to be a type
where the order of the characters doesn’t matter. I also suspect it needs to be able to do
efficient intersections of the sets, as whilst getting to grips with the specification I’d
already noticed you can work out 0, 6 and 9 once you know 1 and 4 because 4 is a subset of 9,
and 1 is a subset of 0 and 9. This hit a snag in that a HashSet doesn’t itself implement
Hash so can’t be used as a key. I pondered sorting the strings and using that as the key, but
the logic to calculate their intersections is pretty complex in Rust. Then I remembered
crate::day_3 and went with representing each of the 7 lines as a bit (giving a unique number
for each set). Further, bitwise & can be used to efficiently do the intersections. I gave this
it’s own type Digit, and hooked into the built-in FromStr trait to make creating these from
the input cleaner. For part one only the first pass through the 10 digits was implemented, but
I’m happy to report that my plan worked and I did not need to change my implementation of part
one to cope with the changes added to solve part two.
Part two required working out the remaining six digits, interpreting the four output digits as a 4 digit decimal number, and summing those to get the puzzle solution. My implementation for part one was a good start to this. As noted above, 0, 6 and 9 can be worked out from 1 and 4. So I added a second pass through the unique digits to grab the three with length 6 that correspond to 0, 6 and 9 in some order. These could then be tested as follows:
- Intersect the set of digits for #4 with the current set. If that’s unchanged, #4 is a subset and the current digit must be 9.
- Intersect the set of digits for #1 with the current set. If unchanged it’s either 0 or 9, and it can’t be 9 as it failed the first check. It must be 0.
- Otherwise it’s 6 by process of elimination.
I added these to the test suite and confirmed it was all working.
For 2, 3, and 5 a similar argument can be made, so a third loop was made just considering the digits with sets of length 5.
- 1 is a subset of 3, but not 2 or 5 so intersect with the set for #1, if unchanged it must be 3
- 5 is a subset of 9, but 2 (and 3) are not. This still intersects the current set with the set for #9, but instead check that the result is the same as the current set, since 5 is the subset.
- Again we can otherwise assume the current set represents 2 by process of elimination.
Again this was added to the test suite and implemented. All ten digits are now known, so the
final step was to implement Display::get_output that converted the four output digits into
the equivalent decimal usize, and I used built in iterate -> map -> sum to reduce the input
to the solution.
Structs
Functions
Given a list of parsed displays, count the total number of 1s, 4s, 7s, and 8s in their outputs
Utility for the whole puzzle input that just defers to parse_line for each line of the
input.
This does all of the hard work. Once the input is turned into a Display the puzzle solution
is easy to calculate. The string is split up by the | and ’ ’ delimeteters and the resulting 14
digits are parsed using Digit::from_str. Then there are the three loops discussed in the
preamble that identify 1, 4, 7 and 8; 0, 6 and 9, then finally 2, 3, and 5. Building the digits
map needed for Display as numbers are found.
The entry point for running the solutions with the ‘real’ puzzle input.