Advent of Code 2021 in pure TensorFlow - day 8


The day 8 challenge is, so far, the most boring challenge faced 😅. Designing a TensorFlow program - hence reasoning in graph mode - would have been too complicated since the solution requires lots of conditional branches. A known AutoGraph limitation forbids variables to be defined in only one branch of a TensorFlow conditional if the variable is used afterward. That’s why the solution is in pure TensorFlow eager.

You can click on the title above to read the full text of the puzzle. The TLDR version is:

The input dataset is something like this

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

Where every character (from a to g) represents a segment of a seven-segment display turned on.

On the left of the separator character (|), we find some “visualization attempts”, on the right, instead, we find the display output. Our goal, of part 2, is to decode the 4 digits of the display output.

Unfortunately, the mapping from the segments switches to the display output is broken. Let’s say the correct mapping is the one that follows

 aaaa
b    c
b    c
 dddd
e    f
e    f
 gggg

Segment a turned on, means to turn on all the four a on top, segment g turned on means to turn on all the 4 g at the bottom, and so on.

As you can guess from the last digit of the second line of the example dataset (gc), that line is not a valid digit, in fact, if rendered it looks like this:


     c
     c


 gggg

Note: every line is independent - the segments g on one line, can turn on a different segment on another line.

The challenge presented in part one gives us some hints on how to start decoding the output digits.

Design phase: part one

The first part of the puzzle requires us to count how many 1,4,7, and 8 are in the output digits. These digits are particular since these are the only ones that require to turn on a unique number of segments:

  • One: two segments
  • Four: four segments
  • Seven: three segments
  • Eight: seven segments

All the other numbers are ambiguous and require different decoding - we’ll see it in part two.

Input pipeline

We create a tf.data.Dataset object for reading the text file line-by-line as usual. We can separately consider the “visualization attempts” (also called signal patterns) and the output digits. For solving the first part of the puzzle we only need to focus on the latter.

dataset = (
    tf.data.TextLineDataset("input")
    .map(lambda line: tf.strings.split(line, " | "))
    .map(lambda lines: tf.strings.split(lines, " "))
)

The dataset object is an iterable object that produces pairs of tf.string. The first element contains a tensor with 10 strings (the signal patterns) the second element contains a batch with 4 strings (the output digits).

Decoding and counting

Part one is trivial, we just need a tf.Variable to count the number of 1,4,7, and 8 found in the output digits, and a way to detect them.

The detection is straightforward since we just need to get the lengths of the strings and check if the length (number of turned-on segments) matches the expected one.

count = tf.Variable(0, trainable=False, dtype=tf.int64)
for _, output_digits in dataset:
    lengths = tf.strings.length(output_digits)
    one = tf.gather_nd(lengths, tf.where(tf.equal(lengths, 2)))
    four = tf.gather_nd(lengths, tf.where(tf.equal(lengths, 4)))
    seven = tf.gather_nd(lengths, tf.where(tf.equal(lengths, 3)))
    eight = tf.gather_nd(lengths, tf.where(tf.equal(lengths, 7)))
    count.assign_add(
        tf.cast(
            tf.reduce_sum(
                [tf.size(one), tf.size(four), tf.size(seven), tf.size(eight)]
            ),
            tf.int64,
        )
    )
tf.print("Part one: ", count)

Here we go! Part one has already been completed!

Design phase: part 2

Part two requires fully decoding the output digits and summing them all. For example, let’s way we decoded the output digits presented at the beginning at:

  • fdgacbe cefdb cefbgd gcbe: 8394
  • fcgedb cgb dgebacf gc: 9781

The puzzle goal is to find the sum of all the output digits, in this example: 8394 + 9781 = 18175.

How can we decode these digits? We need to use our knowledge on how to decode the trivial digits (1,4,7,8) and use the visualization attempts to extract some meaningful information.

For example, let’s say we already decoded from the output - or from the visualization attempts - the segments of the digit 4 and we are trying to decode a pattern that contains 5 segments turned on.

The digits that can be rendered with 5 segments are 2, 3, and 5.

The four we already decoded is rendered as follows:

 ....
b    c
b    c
 dddd
.    f
.    f
 ....

We need to compare the 2, 3, and 5 segments with the segments decoded for the 4.

  • A 5 has 3 segments in common with 4.
  • A 3 has 3 segments in common with 4.
  • A 2 has 2 segments in common with 4. Found!

We can, thus, assert that if our input of length 5 has 2 segments in common with the pattern we are trying to decode, we have found the pattern of the number 2.

Finding the common characters is trivial using the TensorFlow sets support.

TensorFlow set operations

The TensorFlow tf.sets module offers the basic functionalities needed for working with sets. It’s possible to compute the difference, the intersection, the union, and compute the number of unique elements in a set.

The sets are just tf.Tensor with the elements placed in the last dimension.

Knowing that we are ready to decode our digits.

Complete decoding

First, we can define a helper function for easily decoding the easy digits (the one univocally identified by the number of segments) and returning the characters decoded.

def search_by_segments(digits_set, num_segments):
    lengths = tf.strings.length(digits_set)
    where = tf.where(tf.equal(lengths, num_segments))
    number = tf.gather_nd(lengths, where)
    if tf.greater(num_found, 0):
        segments = tf.gather_nd(digits_set, where)[0]
    else:
        segments = tf.constant("")
    # segments (a,b,c)
    return tf.strings.bytes_split(segments)

We can loop over every entry of the dataset - that must be independently be decoded - and first, try to decode all the trivial digits (in the output or in the patterns).

For being solvable, every dataset entry must be at least one trivial digit, otherwise, the problem won’t have a solution.

count.assign(0)  # use count for sum

for signal_patterns, output_digits in dataset:
    # reverse because we compute from units to decimals, ...
    output_digits = tf.reverse(output_digits, axis=[0])
    all_digits = tf.concat([output_digits, signal_patterns], axis=0)
    lengths = tf.strings.length(all_digits)

    eight_chars = search_by_segments(all_digits, 7)
    four_chars = search_by_segments(all_digits, 4)
    seven_chars = search_by_segments(all_digits, 3)
    one_chars = search_by_segments(all_digits, 2)
    zero_chars = [""]
    two_chars = [""]
    three_chars = [""]
    five_chars = [""]
    six_chars = [""]
    nine_chars = [""]

Then, we can start searching for all the ambiguous patterns (e.g. the digits with 5 segments) and try to decode them with the info we have (eight_chars, four_chars, seven_chars, one_chars).

# All the 5 segments: 2, 3, 5
five_segments = tf.strings.bytes_split(
    tf.gather_nd(all_digits, tf.where(tf.equal(lengths, 5)))
)
if tf.greater(tf.size(five_segments), 0):
    for candidate in five_segments:
        candidate_inter_seven = tf.sets.intersection(
            tf.expand_dims(candidate, axis=0),
            tf.expand_dims(seven_chars, axis=0),
        )
        candidate_inter_four = tf.sets.intersection(
            tf.expand_dims(candidate, axis=0),
            tf.expand_dims(four_chars, axis=0),
        )
        candidate_inter_one = tf.sets.intersection(
            tf.expand_dims(candidate, axis=0),
            tf.expand_dims(one_chars, axis=0),
        )
        # Use 7 as a reference:

        # A 2 has 2 in common with 7. I cannot identify it only with this
        # because also 2 has 2 in common with 7.

        # A 3 has 3 in common with 7. I can identify the 3 since 2 and 5 have only 2 in common.

        # 5 has 2 in common with 7. Cannot identify because of the 2.

        # Hence for identify a 2/5 I need a 7 and something else.
        # If I have a four:
        # A 2 has 2 in common with 7 and 2 in common with 4. Found!
        # A 5 has 2 in common with 7 and 3 in common with 4. Found!

        # If I have a one
        # A 2 has 2 in common with 7 and 1 in common with 1. Cannot identify.
        # A 5 has 2 in common with 7 and 1 in common with 1. Cannot identify.
        if tf.greater(tf.size(seven_chars), 0):
            if tf.equal(tf.size(candidate_inter_seven), 3):
                three_chars = candidate
            elif tf.logical_and(
                tf.greater(tf.size(four_chars), 0),
                tf.equal(tf.size(candidate_inter_seven), 2),
            ):
                if tf.equal(tf.size(candidate_inter_four), 2):
                    two_chars = candidate
                elif tf.equal(tf.size(candidate_inter_four), 3):
                    five_chars = candidate

        # use 4 as a reference

        # A 2 has 2 in common with 4. Found!
        # A 5 has 3 in common with 4.
        # A 3 has 3 in common with 4.

        # To find a 5,3 i need something else. Useless to check for seven, already done.
        # A 5 has 3 in common with 4 and 1 in common with 1. Found!
        # A 3 has 3 in common with 2 and 2 in common with 1. Found!

        if tf.greater(tf.size(four_chars), 0):
            if tf.equal(tf.size(candidate_inter_four), 2):
                two_chars = candidate
            if tf.logical_and(
                tf.equal(tf.size(candidate_inter_four), 3),
                tf.greater(tf.size(one_chars), 0),
            ):
                if tf.equal(tf.size(candidate_inter_one), 1):
                    five_chars = candidate
                else:
                    three_chars = candidate

The code is commented and explains how to reason. The very same reasoning must be applied to the other ambiguous digits with 6 segments (6,9,0), but it won’t be presented in the article since it’s identical to the code presented above. You can read the complete code here.

In the end, we should decode the output_digits with our accrued knowledge. In practice, we’ll be able to decode an output digit if the intersection between the output digit characters and the decoded digit character is empty.

for position, digit in enumerate(output_digits):
    digit = tf.strings.bytes_split(digit)
    for num, k in enumerate(
        [
            zero_chars,
            one_chars,
            two_chars,
            three_chars,
            four_chars,
            five_chars,
            six_chars,
            seven_chars,
            eight_chars,
            nine_chars,
        ]
    ):
        difference_1 = tf.sets.difference(
            tf.expand_dims(digit, axis=0), tf.expand_dims(k, axis=0)
        )
        difference_2 = tf.sets.difference(
            tf.expand_dims(k, axis=0), tf.expand_dims(digit, axis=0)
        )
        if tf.logical_and(
            tf.equal(tf.size(difference_1), 0),
            tf.equal(tf.size(difference_2), 0),
        ):
            count.assign_add(num * 10 ** position)

Problem 8 completed!

Conclusion

You can see the complete solution in folder 8 on the dedicated Github repository: https://github.com/galeone/tf-aoc.

The challenge in the challenge of using only TensorFlow for solving the problem is slowly progressing, so far I solved all the puzzles up to Day 12 (inclusive). So get ready for at least 4 more articles :) Let’s see when (and if!) TensorFlow alone won’t be enough.

If you missed the articles about the previous days’ solutions, here’s a handy list:

The next article will be about my solution to Day 9 problem. This solution is really interesting IMO because I solved it using lots of computer vision concepts like image gradients and flood fill algorithm. Maybe an unconventional - but working - approach.

For any feedback or comment, please use the Disqus form below - thanks!

Don't you want to miss the next article? Do you want to be kept updated?
Subscribe to the newsletter!

Related Posts

Advent of Code 2021 in pure TensorFlow - day 12

Day 12 problem projects us the world of graphs. TensorFlow can be used to work on graphs pretty easily since a graph can be represented as an adjacency matrix, and thus, we can have a tf.Tensor containing our graph. However, the "natural" way of exploring a graph is using recursion, and as we'll see in this article, this prevents us to solve the problem using a pure TensorFlow program, but we have to work only in eager mode.

Advent of Code 2021 in pure TensorFlow - day 11

The Day 11 problem has lots in common with Day 9. In fact, will re-use some computer vision concepts like the pixel neighborhood, and we'll be able to solve both parts in pure TensorFlow by using only a tf.queue as a support data structure.

Advent of Code 2021 in pure TensorFlow - day 10

The day 10 challenge projects us in the world of syntax checkers and autocomplete tools. In this article, we'll see how TensorFlow can be used as a generic programming language for implementing a toy syntax checker and autocomplete.

Advent of Code 2021 in pure TensorFlow - day 9

The day 9 challenge can be seen as a computer vision problem. TensorFlow contains some computer vision utilities that we'll use - like the image gradient - but it's not a complete framework for computer vision (like OpenCV). Anyway, the framework offers primitive data types like tf.TensorArray and tf.queue that we can use for implementing a flood-fill algorithm in pure TensorFlow and solve the problem.

Advent of Code 2021 in pure TensorFlow - day 7

The day 7 challenge is easily solvable with the help of the TensorFlow ragged tensors. In this article, we'll solve the puzzle while learning what ragged tensors are and how to use them.

Advent of Code 2021 in pure TensorFlow - day 6

The day 6 challenge has been the first one that obliged me to completely redesign for part 2 the solution I developed for part 1. For this reason, in this article, we'll see two different approaches to the problem. The former will be computationally inefficient but will completely model the problem, hence it will be easy to understand. The latter, instead, will be completely different and it will focus on the puzzle goal instead of the complete modeling.

Advent of Code 2021 in pure TensorFlow - day 5

The day 5 challenge is easily solvable in pure TensorFlow thanks to its support for various distance functions and the power of the tf.math package. The problem only requires some basic math knowledge to be completely solved - and a little bit of computer vision experience doesn't hurt.

Advent of Code 2021 in pure TensorFlow - day 4

Using tensors for representing and manipulating data is very convenient. This representation allows changing shape, organizing, and applying generic transformations to the data. TensorFlow - by design - executes all the data manipulation in parallel whenever possible. The day 4 challenge is a nice showcase of how choosing the correct data representation can easily simplify a problem.

Advent of Code 2021 in pure TensorFlow - day 3

A Solution to the AoC day 3 puzzle in pure TensorFlow. This challenge allows us to explore the TensorArray data type and find their limitations when used inside a static-graph context. We'll also use a tf.function experimental (but very useful) feature for avoiding useless retraces and reusing the same graph with tensors of different shapes.

Advent of Code 2021 in pure TensorFlow - day 2

A Solution to the AoC day 2 puzzle in pure TensorFlow. How to use Enums in TensorFlow programs and the limitations of tf.Tensor used for type annotation