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.

Day 8: Treetop Tree House

You can click on the title above to read the full text of the puzzle. The TLDR version is: a grid is a representation of a plot of land completely filled with trees. Every tree is represented with a number that identifies its height. 0 is the shortest, and 9 is the tallest.

30373
25512
65332
33549
35390

The puzzle clearly defines the concept of tree visibility:

A tree is visible if all of the other trees between it and an edge of the grid are shorter than it. Only consider trees in the same row or column; that is, only look up, down, left, or right from any given tree.

The challenge is to count how many trees are visible from outside the grid.

Design Phase

The problem is quite easy. First thing first, all the trees around the edge of the grid are visible. Thus the number of visible trees will be at least sum(grid_shape * 2) - 4.

Thus, we should analyze only the inner part of the grid. Moreover, the neighborhood to consider is 4-connected (a concept derived from the computer vision pixel connectivity), thus we don’t have to take into account the diagonals and we can process every single pixel of the inner grid by row/column.

That said, we just need to loop over every pixel of the inner grid, and evaluate if the current pixel is visible from the 4 directions. If yes, sum 1 to the variable initialized with sum(grid_shape * 2) - 4.

Part 1 solution

The solution is precisely the TensorFlow implementation of what has been described in the previous section. As usual, we need to use the tf.data.Dataset.map function to transform the raw input into something useful. Thus we first split the line in characters (from 012 to 0,1,2) then convert these characters to numbers, so we can easily apply conditions over the numbers.

dataset = dataset.map(lambda line: tf.strings.bytes_split(line))
dataset = dataset.map(lambda x: tf.strings.to_number(x, tf.int64))

An iterator is not useful when working on a grid, especially if we need to loop back and forth from every position, thus we can convert the whole dataset to a tensor (our grid), so it’s easier to work.

grid = tf.Variable(list(dataset.as_numpy_iterator()))

We now have everything needed to precisely convert the algorithm described in the design phase to code.

  1. Initialization

     visibles = tf.Variable(0, dtype=tf.int64)
     # edges
     grid_shape = tf.shape(grid, tf.int64)
     visibles.assign_add(tf.reduce_sum(grid_shape * 2) - 4)
    

    The visibles variable is initialized with the number of trees that are for sure visible. The tf.reduce_sum function has been used to sum the width and height (multiplied by 2) of the grid.

  2. Looping over the inner grid: searching in the 4-neighborhood.

     # inner
     for col in tf.range(1, grid_shape[0] - 1):
         for row in tf.range(1, grid_shape[1] - 1):
             x = grid[col, row]
    
             visible_right = tf.reduce_all(x > grid[col, row + 1 :])
             if visible_right:
                 visibles.assign_add(1)
                 continue
             visible_left = tf.reduce_all(x > grid[col, :row])
             if visible_left:
                 visibles.assign_add(1)
                 continue
    
             visible_bottom = tf.reduce_all(x > grid[col + 1 :, row])
             if visible_bottom:
                 visibles.assign_add(1)
                 continue
             visible_top = tf.reduce_all(x > grid[:col, row])
             if visible_top:
                 visibles.assign_add(1)
                 continue
    

    The tf.redudce_all function is used to apply the logical and operator to all the boolean values generated by the input inequality. In fact, a tree for being visible requires all the adjacent trees to have a lower height along the considered dimension.

  3. That’s all

    tf.print("part 1: ", visibles)
    

In a few lines, the problem has been perfectly and efficiently solved! Let’s go straight to part 2.

Part 2: scenic distance finding

In the second part of the puzzle, there are 2 new concepts introduced called “viewing distance” and “scenic score”. The puzzle describes the procedure to follow to measure the viewing distance from a given tree.

To measure the viewing distance from a given tree, look up, down, left, and right from that tree; stop if you reach an edge or at the first tree that is the same height or taller than the tree under consideration. (If a tree is right on the edge, at least one of its viewing distances will be zero.)

Every tree has also a scenic score. This score is found by multiplying together its viewing distance in each of the four directions. The challenge for this second part is to find the highest scenic score possible (thus, finding the tree that has this score).

Design and solution

The process to follow is similar to the one used to solve part 1. We still need to loop on every tree of the inner grid, but this time we are interested in the view from the tree along each distance. We can just use broadcasting to create, for every tree, a grid of “views”: keep the height of the tree under consideration and subtract it from the original grid. In this way, when we’ll look for the view along the 4 directions, we can search for views greater than or equal to 0.

Of course, we need to keep track of the views along each dimension for every pixel, thus we need 4 tf.Variable: t for the top view, l for the left view, r for the right view, and b for the bottom view.

The solution, thus, is just the implementation of this simple design.

scenic_score = tf.Variable(0, tf.int64)  #  t * l * b * r
t = tf.Variable(0, tf.int64)
l = tf.Variable(0, tf.int64)
b = tf.Variable(0, tf.int64)
r = tf.Variable(0, tf.int64)
for col in tf.range(1, grid_shape[0] - 1):
    for row in tf.range(1, grid_shape[1] - 1):
        x = grid[col, row]
        views = grid - x

        right = views[col, row + 1 :]
        # the loop is left to right
        left = tf.reverse(views[col, :row], axis=[0])
        # the loop is bottom to top
        top = tf.reverse(views[:col, row], axis=[0])
        bottom = views[col + 1 :, row]

        for tree in right:
            r.assign_add(1)
            if tf.greater_equal(tree, 0):
                break
        for tree in left:
            l.assign_add(1)
            if tf.greater_equal(tree, 0):
                break
        for tree in bottom:
            b.assign_add(1)
            if tf.greater_equal(tree, 0):
                break
        for tree in top:
            t.assign_add(1)
            if tf.greater_equal(tree, 0):
                break
        scenic_node = t * l * b * r
        if tf.greater(scenic_node, scenic_score):
            scenic_score.assign(scenic_node)
        r.assign(0)
        l.assign(0)
        t.assign(0)
        b.assign(0)

tf.print("part 2: ", scenic_score)

Here we go! Day’s 8 problem solved!

Conclusion

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

This article demonstrated how to use the reduce functions for solving a simple puzzle. It’s a very simple solution but it shows, once again, how TensorFlow can be used as a generic programming language.

The next article will be about the solution to problem number 9. It will contain 2 distinct solutions: a solution designed by me, that solves the problem in the imperative style I use to solve all the AoC puzzles in TensorFlow, but it will also contain another solution developed by a fellow GDE that models the problem with a Keras model with 2 layers of convolutions 🤯

The cool thing about solving coding puzzles is that depending on how the problem is modeled the solution can be completely different!

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

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.