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

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.

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

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.