Source: Seven Segment Search

Part 1: Simulate a seven segment displey where you do not know which input wire controls which segment. Given the wires used in all ten digits and four output digits, count how many times 1, 4, 7, and 8 are outputted.

This one took me far longer to work out than I’d care to admit. And it wasn’t at all because I had the wrong approach (I went for brute force again), but rather because I had mistyped one character in my input. Bah humbug. That’s why you write tests… Oy.

Like I mentioned, I’m just going to try to brute force this problem. It will be slower than using their advice (the advice being that there is always 1 input with two segments (one) and 1 with 3 (seven). Instead, brute forcing all ten digits makes for much cleaner code. First, let’s set up some constants:

# Seven segment display
#   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

SEGMENTS = [
    {'a', 'b', 'c', 'e', 'f', 'g'},
    {'c', 'f'},
    {'a', 'c', 'd', 'e', 'g'},
    {'a', 'c', 'd', 'f', 'g'},
    {'b', 'c', 'd', 'f'},
    {'a', 'b', 'd', 'f', 'g'},
    {'a', 'b', 'd', 'e', 'f', 'g'},
    {'a', 'c', 'f'},
    {'a', 'b', 'c', 'd', 'e', 'f', 'g'},
    {'a', 'b', 'c', 'd', 'f', 'g'},
]

ALPHABET = 'abcdefg'
MAPPINGS = [
    dict(zip(ALPHABET, ordering))
    for ordering in itertools.permutations(ALPHABET)
]

The SEGMENTS define a set of correctly labeled wires goes to each segment (in order). So 0 uses all of them but d, 1 uses only c and f, etc.

MAPPINGS is a neat trick. Using itertools.permutations , we can generate all possible arrangements of the 7 letters in ALPHABET. We then zip each ordering up with ALPHABET, convert to a dict and we have a conversion. For example:

>>> MAPPINGS[286]
{'a': 'a', 'b': 'd', 'c': 'c', 'd': 'g', 'e': 'f', 'f': 'b', 'g': 'e'}
>>> MAPPINGS[286]['a']
'a'
>>> MAPPINGS[286]['g']
'e'

In this case, input wire a maps to output a, but g maps to e, etc.

Okay. Fun part. For each input, we have all ten digits, with the input wires that makes those up, but we don’t know which mapping matches. But we do know if a mapping is valid, it will have to turn each of those ten inputs into one of the possible SEGMENTS. So we can do this:

def load(file: TextIO) -> Generator[List[int], None, None]:
    '''
    Load an input file with a scrambled set of 7 segment displays than 4 output digits.'''

    for line in file:
        raw_inputs, raw_outputs = line.split(' | ')
        inputs = [set(input) for input in raw_inputs.split()]
        outputs = [set(output) for output in raw_outputs.split()]

        for mapping in MAPPINGS:
            if any(
                {mapping[v] for v in input} not in SEGMENTS
                for input in inputs
            ):
                continue

            yield [
                SEGMENTS.index({mapping[v] for v in output})
                for output in outputs
            ]

We’ll take the input (which looks like acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab | cdfeb fcadb cdfeb cdbaf), split the input and output, and then go through each mapping. The line {mapping[v] for v in input} creates the output given the mapping, so we apply that to every input in inputs and check for any not in SEGMENTS. If that’s the case, the mapping isn’t valid, so skip it. We should have exactly 1 mapping that’s valid, so decode the outputs (using that same mapping) and yield the resulting digits.

I expect that’s overkill / already implementing part 2… but that’s okay!

Since we have the digits, count up the 1, 4, 7, and 8 (they’re the easiest to determine).

def part1(file: typer.FileText):
    print(sum(
        1 if digit in (1, 4, 7, 8) else 0
        for digits in load(file)
        for digit in digits
    ))

Yeah… that’s it!

$ python3 seven-segment-demystifier.py part1 input.txt
349

Part 2: Calculate the sum of all of the 4 digit output numbers.

Yeah… in brute forcing the entire problem rather than just solving the ’easy’ 4 digits, this is already done:

def part2(file: typer.FileText):
    print(sum(
        int(''.join(str(digit) for digit in digits))
        for digits in load(file)
    ))

So easy!

$ python3 seven-segment-demystifier.py part2 input.txt
1070957

Testing

So. The error I originally had was that I was missing one segment for the zero. That meant that there was never a mapping that worked. In order to debug that, I ended up writing this:

if any(
    any(
        mapping[letter] not in dst
        for letter in src
    )
    for src, dst in [('ab', 'cf'), ('dab', 'acf'), ('eafb', 'bcdf')]
):
    continue

print(mapping)
failed = 0
for input in inputs:
    mapped_input = {mapping[v] for v in input}
    if mapped_input not in SEGMENTS:
        print('failed', input, '->', mapped_input)
        failed += 1

print('failed', failed)
print()

That way, I’m basically solving the faster mode (see below) for the single example given above (with one being ab -> cv, seven being dab -> acf, and the rest as such). That way when I printed it out… I found the single number failing. Oy vey. Anyways!

Timing

So… this is where it’s starting to get a bit slower:

--- Day 8: Seven Segment Search ---

$ python3 seven-segment-demystifier.py part1 input.txt
349
# time 753413083ns / 0.75s

$ python3 seven-segment-demystifier.py part2 input.txt
1070957
# time 845831292ns / 0.85s

Still under a second… so fast enough. But I wonder if that could be optimized a bit by using the tricks they mentioned.

For example, if you have the input:

acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab

• You know that ab is a one (it’s the only one with two segments) and maps to cf.
• Likewise, you know dab is seven and maps to acf.
• Between the two, that means that the top segment has to be the input: d, output: a (it’s the only one not in both).

So one part of the mapping (d -> a) is set and another two a/b -> c/f has only two remaining options. That reduces the number of possible permutations from P(7, 7) = 5040 to P(2, 2) * P(4, 4) = 48 ! That’s amazing and probably worth it.

Okay, let’s write a more complicated (but faster) load function:

def load2(file: TextIO) -> Generator[List[int], None, None]:
    '''
    Load an input file with a scrambled set of 7 segment displays than 4 output digits.

    Use the fact that there's only 1 possibility for one, 1 (overlapping) for seven to limit the number of permutations from 5040 to 48. 
    '''

    for line in file:
        raw_inputs, raw_outputs = line.split(' | ')
        inputs = [set(input) for input in raw_inputs.split()]
        outputs = [set(output) for output in raw_outputs.split()]

        for input in inputs:
            if len(input) == 2:
                one = input
            elif len(input) == 3:
                seven = input

        # The output that is in seven but not one maps to a
        # I wish there were a better way to get the only value out of a set
        mapping = {
            list(seven.difference(one))[0]: 'a'
        }

        # The other two values in one have to map to c and f
        for one_permutation in itertools.permutations(one):
            mapping.update(dict(zip(one_permutation, 'cf')))

            # And all the values not in seven permute the last output
            for rest_permutation in itertools.permutations(set('abcdefg') - seven):
                mapping.update(dict(zip(rest_permutation, 'bedg')))

                if any(
                    {mapping[v] for v in input} not in SEGMENTS
                    for input in inputs
                ):
                    continue

                yield [
                    SEGMENTS.index({mapping[v] for v in output})
                    for output in outputs
                ]

So we’re going to still iterate through the mappings, but generate them in three parts. The value that’s in seven but not one (the initial mapping), the one_permutation of values only in one and the rest_permutation of the 4 values not in seven.

One bit of weirdness is that I’m always using the mutation’y dict.update function. That modifies the dictionary, which you think would mess things up… but turns out it can’t. We are always using permutations of the same two/four values, so always overwriting in each iteration. Good times!

In order to hook this up, I used a typer callback:

@app.callback()
def useLoad2(fast: bool = False):
    global load, load2

    if fast:
        load = load2

That’s actually surprisingly simple… Does it work?

``bash — Day 8: Seven Segment Search —

$ python3 seven-segment-demystifier.py part1 input.txt 349

time 737720459ns / 0.74s

$ python3 seven-segment-demystifier.py part2 input.txt 1070957

time 728406083ns / 0.73s

$ python3 seven-segment-demystifier.py –fast part1 input.txt 349

time 49562583ns / 0.05s

$ python3 seven-segment-demystifier.py –fast part2 input.txt 1070957

time 49386709ns / 0.05s

Heck yes it does. That's an order of magnitude speedup! And I would argue the code is not *that* much worse (although it *is* worse). Cool times.