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.
-
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
visiblesvariable is initialized with the number of trees that are for sure visible. Thetf.reduce_sumfunction has been used to sum the width and height (multiplied by 2) of the grid. -
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) continueThe
tf.redudce_allfunction 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. -
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
- Advent of Code 2022 in pure TensorFlow - Days 1 & 2.
- Advent of Code 2022 in pure TensorFlow - Days 3 & 4.
- Advent of Code 2022 in pure TensorFlow - Day 5
- Advent of Code 2022 in pure TensorFlow - Day 6
- Advent of Code 2022 in pure TensorFlow - Day 7
For any feedback or comment, please use the Disqus form below - thanks!