Advent of Code 2021 in pure TensorFlow - day 2


Day 2 challenge is very similar to the one faced in day 1. In this article, we’ll see how to integrate Python enums with TensorFlow, while using the very same design nuances used for the day 1 challenge.

Day 2: Dive!: part one

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

You are given a dataset in the format

action amount

Where action is a string in the set forward, down, up and the amount is an integer to add/subtract to a dedicated counter. These counters represent the position on the horizontal plane and a depth (in the adventure, we are in a submarine). For example:

forward 5
down 5
forward 8
up 3
down 8
forward 2

forward 5 increases by 5 the horizontal position, down 5 adds 5 to the depth, and up 3 decreases the depth by 3. The objective is to compute the final horizontal position and depth and multiply these values together. In the example, we end up with a horizontal position of 15 and a depth of 15, for a final result of 150.

Design phase

Being very very similar to the task solved for day one, the same considerations about the sequential nature and the statefulness of the TensorFlow program hold.

This puzzle is not only sequential but also involves the creation of a mapping between the action and the counter to increment.

There are many different ways of implementing this mapping, TensorFlow provides us all the tooling needed. For example, we could use a MutableHashTable to map the actions to the counters, but being in the experimental module I’d suggest avoiding using it. Instead, we can implement our own very, very coarse mapping method using a Python Enum.

The peculiarity of the Enum usage in TensorFlow is that we cannot use the basic Enum type, because it has no TensorFlow data-type equivalent. TensorFlow needs to know everything about the data its manipulating, and therefore it prevents the creation of Enums. We, have to use basic TensorFlow types like tf.int64 and, thus, use an Enum specialization like IntEnum.

from enum import IntEnum, auto

class Action(IntEnum):
    """Action enum, to map the direction read to an action to perform."""

    INCREASE_HORIZONTAL = auto()
    INCREASE_DEPTH = auto()
    DECREASE_DEPTH = auto()

Input pipeline

Exactly like during day 1 we can use a TextLineDataset to read all the lines of the input dataset. This time, while we read the lines we need to apply a slightly more complicated mapping function. I defined the _processor function to split every line, map the action string to the corresponding Action enum value, and convert the amount to a tf.int64. The function returns the pair (Action, amount).

def _processor(line):
    splits = tf.strings.split(line)
    direction = splits[0]
    amount = splits[1]

    if tf.equal(direction, "forward"):
        action = Action.INCREASE_HORIZONTAL
    elif tf.equal(direction, "down"):
        action = Action.INCREASE_DEPTH
    elif tf.equal(direction, "up"):
        action = Action.DECREASE_DEPTH
    else:
        action = -1
    #    tf.debugging.Assert(False, f"Unhandled direction: {direction}")

    amount = tf.strings.to_number(amount, out_type=tf.int64)
    return action, amount

dataset = tf.data.TextLineDataset("input").map(_processor)

Note that every function passed to every method of a tf.data.Dataset instances will always be executed in graph mode. That’s why I had to add the action = -1 statement in the last else branch (and I couldn’t use the assertion). In fact, the if statement is converted to a tf.cond by autograph, and since in the true_fn we modify a node (action) defined outside the tf.cond call, autograph forces us to modify the same node also in the else statement, in order to be able to create a direct acyclic graph in every scenario.

Moreover, I can use the -1 without any problem because the IntEnum members are always positive when declared (as I did) with auto(), hence -1 is an always invalid item (and a condition that will never be reached).

Position counter

Similar to the solution of day 1, we define our PositionCounter as a complete TensorFlow program with 2 states (variables). A variable for keeping track of the horizontal position and another for the depth.


class PositionCounter(tf.Module):
    """Stateful counter. Get the final horizontal position and depth."""

    def __init__(self):
        self._horizontal_position = tf.Variable(0, trainable=False, dtype=tf.int64)
        self._depth = tf.Variable(0, trainable=False, dtype=tf.int64)

    @tf.function
    def __call__(self, dataset: tf.data.Dataset) -> Tuple[tf.Tensor, tf.Tensor]:
        """
        Args:
            dataset: dataset yielding tuples (action, value), where action is
                     a valida Action enum.
        Returns:
            (horizontal_position, depth)
        """
        for action, amount in dataset:
            if tf.equal(action, Action.INCREASE_DEPTH):
                self._depth.assign_add(amount)
            elif tf.equal(action, Action.DECREASE_DEPTH):
                self._depth.assign_sub(amount)
            elif tf.equal(action, Action.INCREASE_HORIZONTAL):
                self._horizontal_position.assign_add(amount)
        return self._horizontal_position, self._depth

The call method accepts our tf.data.Dataset that yields tuples and performs the correct action on the states.

Execution

counter = PositionCounter()
horizontal_position, depth = counter(dataset)
result = horizontal_position * depth
tf.print("[part one] result: ", result)

Just create an instance of the PositionCounter and call it over the dataset previously created. Using type annotations while defining our functions simplifies their usage.

A limitation of the type annotation when used with TensorFlow is pretty easy to spot: we only have the tf.Tensor type, and the information of the TensorFlow data type (e.g. tf.int64, tf.string, tf.bool, …) is not available.

A possible (partial) solution is provided by the package tensor_annotations by Deepmind: TensorAnnotations.

Anyway, the execution gives the correct result :) and this brings us to part 2.

Day 2: Dive!: part two

TLDR: there’s a small modification of the challenge, that adds a new state. In short, there’s now to keep track of another variable called aim. Now, down, up, and forward have a different meanings:

  • down X increases your aim by X units.
  • up X decreases your aim by X units.
  • forward X does two things:
    • It increases your horizontal position by X units.
    • It increases your depth by your aim multiplied by X.

Design phase - part two

It’s just a matter of extending the Action enum defined at the beginning, adding the _aim variable, and acting accordingly to the new requirements in the call method. Without rewriting the complete solution, we can just expand the enum as follows

class Action(IntEnum):
    """Action enum, to map the direction read to an action to perform."""

    INCREASE_HORIZONTAL = auto()
    INCREASE_DEPTH = auto()
    DECREASE_DEPTH = auto()
    INCREASE_AIM = auto()
    DECREASE_AIM = auto()
    INCREASE_HORIZONTAL_MUTIPLY_BY_AIM = auto()

And having defined the _aim variable in the same way of the _depth and _horizontal_position, update the call body as follows:

for action, amount in dataset:
    if tf.equal(action, Action.INCREASE_DEPTH):
        self._depth.assign_add(amount)
    elif tf.equal(action, Action.DECREASE_DEPTH):
        self._depth.assign_sub(amount)
    elif tf.equal(action, Action.INCREASE_HORIZONTAL):
        self._horizontal_position.assign_add(amount)
    elif tf.equal(action, Action.INCREASE_HORIZONTAL_MUTIPLY_BY_AIM):
        self._horizontal_position.assign_add(amount)
        self._depth.assign_add(self._aim * amount)
    elif tf.equal(action, Action.DECREASE_AIM):
        self._aim.assign_sub(amount)
    elif tf.equal(action, Action.INCREASE_AIM):
        self._aim.assign_add(amount)
return self._horizontal_position, self._depth

Execution - part two

The execution is identical to the previous one, there’s no need to repeat it here. So, also the second puzzle is gone :)

Conclusion

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

I created two different files for the two different parts, only because I’m lazy. There’s for sure a more elegant solution without 2 different programs, but since the challenge was more or less a copy-paste of the one faced on day 1 I wasn’t stimulated enough to write a single elegant solution.

The day 2 exercise is really easy and almost identical to the one presented on day 1. Also from the TensorFlow side, there are not many peculiarities to highlight.

I showed how to use Enums (in short, we can only use types that are TensorFlow compatible, hence no pure python Enums) and I presented a limitation that’s related to the missing typing of the tf.Tensor in the type annotations, but that’s all.

A possible (partial) solution is provided by the package tensor_annotations by Deepmind: TensorAnnotations - however, this package helps only partially because when creating TensorFlow programs we are interested also in the type and not just to the name of the field (e.g. Batch, Time, Height, …), and it looks like the package doesn’t provide support for what I do really need.

Luckily, I’ve already completed the challenges for days 3 and 4. Both of them are interesting, and in both, we’ll see some interesting features of TensorFlow. A little spoiler, we’ll use the tf.TensorArray :)

The next article about my pure TensorFlow solution for day 3 will arrive soon!

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 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.

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