Advent Of Code 2021, Day 8: Seven Segment Search

by Abigail

Challenge

   0       1       2       3       4       5       6      7        8       9
 aaaa    ....    aaaa    aaaa    ....    aaaa    aaaa    aaaa    aaaa    aaaa
b    c  .    c  .    c  .    c  b    c  b    .  b    .  .    c  b    c  b    c
b    c  .    c  .    c  .    c  b    c  b    .  b    .  .    c  b    c  b    c
 ....    ....    dddd    dddd    dddd    dddd    dddd    ....    dddd    dddd
e    f  .    f  e    .  .    f  .    f  .    f  e    f  .    f  e    f  .    f
e    f  .    f  e    .  .    f  .    f  .    f  e    f  .    f  e    f  .    f
 gggg    ....    gggg    gggg    ....    gggg    gggg    ....    gggg    gggg

acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab | cdfeb fcadb cdfeb cdbaf

Part One

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

Part Two

Solution

The key to the solution is to determine what is unique about the signals for each number.

Take a look at the table on the right. The first column has the ten digits. The second column, marked with a #, indicates how many segments the digit uses. The next ten columns show how many segments the digit shares with the other nine digits.

We can see that four digits have a unique number of segments: 1 uses two segments, 4 uses four segments, 7 uses three segments, and 8 uses seven segments.

The other digits can be grouped into two groups: 0, 6, and 9 all use six segments, while 2, 3, and 5 all use five segments. We can distinguish between those digits to look at the number of segments they share with digits we have already identified.

Looking at the table, of the group 0, 6, and 9 one of them (6) shares exactly one segment with 1, while the other two share two segments. Having identified 6, we can distinguish between 0, and 9 by comparing them with 4: 0 shares three segments with 4, while 9 shares four segments.

Which leaves use the group of 2, 3, and 5. When we compare those numbers with 1, then 3 has two segments in common, while the other two digits have one segment in common. To distinguish between 2, and 5, we compare them with 9. If they have five segments in common, the digit is a 5, else, it's a 2.

Perl

First thing we do is read a line of input. We will sort the segments in the signals — that way each digit has always the same representation. That is, an 8 will always be representated as abcdefg (all seven segments are on), instead of bdecagf or gfedcba. And if for 7, the segments b, d and f are used, we always represent that as bdf.

chomp;
my ($input, $output) = split /\s*\|\s*/;

my @input  = map {join "" => sort split //} split ' ' => $input;
my @output = map {join "" => sort split //} split ' ' => $output;

Now, @input contains the first ten signals, and @output the signals for the display.

Next, we will group the input signals by their length:

my @buckets;
foreach my $i (@input) {
    push @{$buckets [length $i]} => $i;
}

Since some of the lengths are unique for some digits, we can fill in some digits. @digits maps digits to their signal:

my @digits;
$digits [1] = $buckets [2] [0];
$digits [4] = $buckets [4] [0];
$digits [7] = $buckets [3] [0];
$digits [8] = $buckets [7] [0];

We will create a helper function. Given the signals of two digits, it will return how many segments they have in common:

sub shares ($f, $s) {
    grep {$s =~ /$_/} split // => $f;
}

We can now distinguish between 0, 6, and 9, and between 2, 3, and 5 by comparing the number of shared segments to known digits:

foreach my $try (@{$buckets [6]}) {
    $digits [shares ($try, $digits [1]) == 1 ? 6
           : shares ($try, $digits [4]) == 3 ? 0
           :                                   9] = $try;
}

foreach my $try (@{$buckets [5]}) {
    $digits [shares ($try, $digits [1]) == 2 ? 3
           : shares ($try, $digits [9]) == 5 ? 5
           :                                   2] = $try;
}

We now know the signals for each of the digits. So, we create a lookup table which maps the signals to the digits:

my %display;
$display {$digits [$_]} = $_ for keys @digits;

Now it's just a matter of counting and adding:

$count1 += grep {$display {$_} == 1 ||
                 $display {$_} == 4 ||
                 $display {$_} == 7 ||
                 $display {$_} == 8}      @output;

$count2 += join "" => map {$display {$_}} @output;

And we print the results:

say "Solution 1: ", $count1;
say "Solution 2: ", $count2;

Find the full program on GitHub.