Advent of Code 2022 in pure TensorFlow - Day 6


Solving problem 6 of the AoC 2022 in pure TensorFlow allows us to understand how powerful this framework can be. In particular, problem 6 can be solved with a highly efficient and parallel solution, using just a single feature of tf.data.Dataset: interleave.

Day 6: Tuning Trouble

You can click on the title above to read the full text of the puzzle. The TLDR version is: we need to decode a signal. The signal is a string containing some “random” characters. Decoding a signal means detecting a marker character. A marker character is defined as the first character of a sequence of 4 (part 1) or 14 (part 2) characters without repeater characters inside.

So, given a puzzle input like

mjqjpqmgbljsphdztnvjfqwrcgsmlb

we need to analyze the signal sequentially (left to right) and search for the first sequence of 4 characters that are all different. In this case, we start from the left mjq are the first 3 characters. The 4 characters, however, is a j that’s contained in the mjq sequence, so j is repeated and thus m is not a marker character. The first time a marker appears is after the seventh character arrives. In this case, the last four characters received are jpqm, which are all different. Thus, the result of the analysis is 7.

Part 1 asks us to detect the marker character considering sequences of 4 different characters, part 2 instead requires sequences of 14 different characters.

Design Phase

The problem may look complicated since it requires searching for sequences of different characters on strings that can potentially overlap. For example, given the sample input

mjqjpqmgbljsphdztnvjfqwrcgsmlb

The first search fails. mjqj is not a valid sequence. Thus, we need to restart the search from the first j character of the sequence, finding jqjp that’s once again not correct. We need to repeat this very same algorithm until we don’t find the jpqm string that satisfies the condition.

There’s a thing to note that will help in designing a fast solution for this problem: every search is potentially independent of each other. If we can split the input sequence into various sub-strings like (for part 1, 4 splits, for part 2, 16 splits):

  • [0,4] -> [4,8] -> [8,12] -> ...
  • [1,5] -> [5,9] -> [9-13] -> ...
  • [2,6] -> [6,10] -> [10-14] -> ...
  • [3,7] -> [7,11] -> [11-15] -> ...

and interleave the sub-strings generating the sequence [0,4] -> [1,5] -> [2,6] -> [3,7] -> [4,8] -> ..., we can loop over this sequence and stop when the correct substring meets the criteria (all the characters are different).

Understanding tf.data.Dataset interleave

tf.data.Dataset.interleave is the superhero of data transformation. This is the method signature

interleave(
    map_func,
    cycle_length=None,
    block_length=None,
    num_parallel_calls=None,
    deterministic=None,
    name=None
)

The interleave method allows us to apply a transformation (map_func) to an input dataset, generate a new dataset for every iteration, control the behavior of every dataset, and interleave the results into a single output stream of a new dataset object.

The cycle_length and block_length arguments control the order in which elements are produced. The num_parallel_calls and deterministic parameters control the multi-thread behavior of the transformation. When num_parallel_calls is specified, the cycle_lenght elements produced from the initial dataset, are processed by num_parallel_calls threads. This processed data is then grouped in block_length elements and produced as output.

In short, you can think about the block_length parameter as the number of elements that the interleaved dataset will produce on every iteration, while cycle_length is the number of elements for every generated dataset that will be processed concurrently. You can specify the concurrency level through the num_parallel_calls parameter and with the deterministic parameter you can control that every iteration of the dataset respects your deterministic, intended, behavior. In our case, we are interested in having a deterministic approach, since the position of the marker character is important, but of course, there are problems in which you just want to apply transformations to datasets and interleave the results, without being interested in the order of the interleaving.

Solving the problem

tf.data.Dataset.interleave is all we need to solve this problem. With a correct configuration, it can model exactly the behavior described in the design phase section.

The dataset, however, requires to be converted from a single long string (the input signal) to a real “stream” of characters, that we can use as input dataset for our interleave transformation.

chars = tf.convert_to_tensor(
    next(
        dataset.map(lambda line: tf.strings.bytes_split(line))
        .take(1)
        .as_numpy_iterator()
    )
)

dataset = tf.data.Dataset.from_tensors(tf.reshape(chars, [-1, 1])).unbatch()

dataset now is a tf.data.Dataset that produces characters on every iteration (a real stream!). So, how can we create an interleaved version of this dataset that produces the sequence of sub-strings we are interested in?

We should be able to produce 4 (or 16 for part 2) new datasets, each of them starting from a different offset.

  • Dataset 1. Offset 0: mjqj - pqmg - bljs
  • Dataset 2: Offset 1: jqjp - qmgb - ljsp
  • Dataset 3: Offset 2: qjpq - mgbl - jsph
  • Dataset 4: Offset 3: jpqm - gblj - sphd

Using the interleave method is quite easy: we just need to create the right dataset of offsets and generate the interleaved datasets. This dataset will be then used by the interleave method, as specified by its configuration, to produce the desired result.

interleaved = tf.data.Dataset.range(4).interleave(
    lambda offset: dataset.skip(offset).batch(4),
    cycle_length=4,
    block_length=1,
    num_parallel_calls=4,
    deterministic=True,
)

Yes, it really is that easy! With tf.data.Dataset.range(4) we are generating the dataset that produces the values from 0 to 4 sequentially. This dataset is used to produce the offset value for the dataset.skip method invoked as the transformation to the input dataset. So, our map_func produces a new tf.data.Dataset on every iteration of the range-dataset. Every dataset then extracts a batch of 4 elements (the substrings).

The configuration, allows us to iterate over the interleaved 4 datasets, in a deterministic way, extracting on every iteration a batch of 4 elements for each created dataset, interleaved as we expect.

Thus, to completely solve the problem we have to loop over this dataset, check for the uniqueness of the elements in the loop, and get the char’s index:

for count, b in enumerate(interleaved):
    y, _ = tf.unique(tf.reshape(b, -1))
    if tf.equal(tf.shape(y)[0], 4):
        tf.print(y)
        # 1: starts from 0
        # 3: the remaining chars in the sequence
        tf.print("unique found at char: ", count + 4)
        break

Here we go, day 6 problem solved in pure TensorFlow! Solving part 2 is identical, just replace every occurrence of 4 with 14.

Give a look at the complete solution.

Conclusion

You can see the complete solutions in folder 6 in the dedicated GitHub repository (in the 2022 folder): https://github.com/galeone/tf-aoc.

Solving problem 6 allowed us to use a very powerful feature of tf.data.Dataset: interleave. In a few lines, this method allows us to define a complete, highly parallel, and efficient data transformation pipeline, that allows us to transform and group data gathered from different datasets. The expressive power of this method, moreover, allowed us to solve the problem in a very elegant way IMHO.

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

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 2022 in pure TensorFlow - Day 9

In this article, we'll show two different solutions to the Advent of Code 2022 day 9 problem. Both of them are purely TensorFlow solutions. The first one, more traditional, just implement a solution algorithm using only TensorFlow's primitive operations - of course, due to some TensorFlow limitations this solution will contain some details worth reading (e.g. using a pairing function for being able to use n-dimensional tf.Tensor as keys for a mutable hashmap). The second one, instead, demonstrates how a different interpretation of the problem paves the way to completely different solutions. In particular, this solution is Keras based and uses a multi-layer convolutional model for modeling the rope movements.

Advent of Code 2022 in pure TensorFlow - Day 8

Solving problem 8 of the AoC 2022 in pure TensorFlow is straightforward. After all, this problem requires working on a bi-dimensional grid and evaluating conditions by rows or columns. TensorFlow is perfectly suited for this kind of task thanks to its native support for reduction operators (tf.reduce) which are the natural choice for solving problems of this type.

Advent of Code 2022 in pure TensorFlow - Day 7

Solving problem 7 of the AoC 2022 in pure TensorFlow allows us to understand certain limitations of the framework. This problem requires a lot of string manipulation, and TensorFlow (especially in graph mode) is not only not easy to use when working with this data type, but also it has a set of limitations I'll present in the article. Additionally, the strings to work with in problem 7 are (Unix) paths. TensorFlow has zero support for working with paths, and thus for simplifying a part of the solution, I resorted to the pathlib Python module, thus not designing a completely pure TensorFlow solution.

Advent of Code 2022 in pure TensorFlow - Day 5

In the first part of the article, I'll explain the solution that solves completely both parts of the puzzle. As usual, focusing on the TensorFlow features used during the solution and all the various technical details worth explaining. In the second part, instead, I'll propose a potential alternative solution to the problem that uses a tf.Variable with an undefined shape. This is a feature of tf.Variable that's not clearly documented and, thus, widely used. So, at the end of this article, we'll understand how to solve the day 5 problem in pure TensorFlow and also have an idea of how to re-design the solution using a tf.Variable with the validate_shape argument set to False.

Advent of Code 2022 in pure TensorFlow - Days 3 & 4

The solutions in pure TensorFlow I designed for days 3 and 4 are both completely based upon the tf.data.Dataset object. In fact, both problems can be seen as the streaming manipulation of the data that's being read from an input dataset.

Advent of Code 2022 in pure TensorFlow - Days 1 & 2

Let's start a tradition. This is the second year in a row I try to solve the Advent of Code (AoC) puzzles using only TensorFlow. This article contains the description of the solutions of the Advent of Code puzzles 1 and 2, in pure TensorFlow.

Integrating third-party libraries as Unreal Engine plugins: ABI compatibility and Linux toolchain

The Unreal Build Tool (UBT) official documentation explains how to integrate a third-party library into Unreal Engine projects in a very broad way without focusing on the real problems that are (very) likely to occur while integrating the library. In particular, when the third-party library is a pre-built binary there are low-level details that must be known and that are likely to cause troubles during the integration - or even make it impossible!

Code Coverage of Unreal Engine projects

Code coverage is a widely used metric that measures the percentage of lines of code covered by automated tests. Unreal Engine doesn't come with out-of-the-box support for computing this metric, although it provides a quite good testing suite. In this article, we dive into the Unreal Build Tool (UBT) - particularly in the Linux Tool Chain - to understand what has to be modified to add the support, UBT-side, for the code coverage. Moreover, we'll show how to correctly use the lcov tool for generating the code coverage report.

Wrap up of Advent of Code 2021 in pure TensorFlow

A wrap up of my solutions to the Advent of Code 2021 puzzles in pure TensorFlow

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.