« posts | «« home

Day 8: Treetop Tree House

View puzzle page »

Skip to the code?

If you’d like to read my solution first, the code is available on GitHub.

Puzzle 1

Day 8’s puzzle presents us with a grid/matrix of ‘trees’ represented as integers and the challenge is to determine which ‘trees’ are ‘visible’ from the edges of the grid, based on whether the integer is higher than the other integers horizontally or vertically out to the edge.

The example below makes this a bit clearer.

30373
25512
65332
33549
35390

The tree ‘5’ at position 1,1 (zero-index) would be visible upwards and leftwards because it’s higher than 0 and 2, while it would be blocked by the two 5’s rightwards and downwards.

Solution

This puzzle gives an opportunity to employ the NumPy library which provides support for handling multi-dimensional arrays (among a number of other mathematical requirments). Since we’re dealing with a large matrix (99x99), this will significantly simplify the task vs. parsing and loading the grid into an array manually.

import numpy as np

with open("day8_input.txt", encoding="utf-8") as f:
    matrix = np.array([list(row.strip()) for row in f], int)

First thing is loading the content of the input file in, by row, and calling strip to get rid of the newline chars on the tail of each line. Then we’re coercing the string (from each row) into a list which gives results in a list of lists. NumPy’s array creates a more powerful multi-dimensional object from an array-like object, in this case our list of lists. We also set a data type in the 2nd argument, saving us the need to coerce each element inside the list comprehension.

We can then use NumPy again to create a second array which reflects the shape of our matrix. We’re going to map whether each tree is visible to this second array, giving as another powerful object to simplify the calculation. NumPy lets us create a new array based on another and also initialise the array with values. Here we want a grid of 0’s.

tree_count = np.zeros_like(matrix, int)

NumPy provides a lot of utilities for manipulating arrays. The one that is particularly useful for us here is rot90 which rotates a multi-dimensional array along it’s axis. The example grid from above, for example, when rotated will become:

32290
71349
35353
05535
32633

Relying on this function enables us to restrict our evaluation to a single direction, instead of trying to review the adjacent values in 4 different directions.

So we want to perform our evaluation for the current status of the matrix and then rotate. We’ll need to repeat this 4 times, once for each edge, so our first step is a 4-iteration loop. Then we’ll expose the horizontal and vertical position of each element using NumPy’s ndindex. This is just a function to return us an n-dimensional iterator based on the shape of the array.

for edge in range(4):
    for h, v in np.ndindex(matrix.shape):

For each h,v pair in the array, we want to deterine whether it is greater than the adjacent values on the vertical axis (ascending by index | descending visually). We can find the values to compare with by slicing the matrix array from the vertical position of the current element.

shorter = [tree < matrix[h, v] for tree in matrix[h, v+1:]]

Now we have a list with True and False values depending on whether any of the compared values were greater than the current element in the loop - True if the compared value is lower, False if it’s greater. We can reduce the values of this list to a single boolean using all, which returns True only if all the elements of the iterable return as True in bool. If all the values are True, then the tree has visibility to the edge.

tree_count[h, v] |= all(shorter)

We perform an in-place bitwise OR using |= (ior). This lets us simultaneously evaluate and set the value of the h,v pair in the secondary array. The ior, similar to an or, will return True when either value is true, otherwise False. In this case, we have an array of zeroes which evaluate to False. So when the result of all(shorter) is False, we keep the False, and when it’s True we switch it.

Once this inner loop completes, we need to rotate both arrays to begin the next edge. We can repeat the rotation on both arrays using map.

matrix, tree_count = map(np.rot90, [matrix, tree_count])

Now our loop will repeat for the remaining three edges and we’ll be left with our tree_count array which has True at all locations where the tree would be visible from the edge. NumPy once again gives us a useful method called sum to get the total of the values in the array. Since False will be 0 and True will be 1, we get a total of all the trees that are visible.

tree_count.sum()

The output of the sum is the answer to puzzle 1.

Puzzle 2

The second puzzle asks to calculate the ‘scenic score’ of any tree. This is the multiplied product of how many other trees separate the tree from an edge or the nearest tree of the same height (inclusive).

Another way to think about this is that we’re counting all the trees shorter than the current tree, until we hit the edge, or a taller or same height tree, and counting that one too. That means we can find the first tree that isn’t shorter and grab its index then add 1. If we hit the edge instead, we just take the length of the list.

Something which is not explicitly mentioned in the puzzle is that you will end up with zero values for the edges because they all have a zero multiplication for the direction out of the grid. This is also why we need to initialise our tree_count array as 1s instead of 0s.

tree_count = np.ones_like(matrix, int)

Working from our logic that we can look for the first tree which isn’t shorter than the current one, we can use the ~ operator to invert the booleans in our list. This means that all the trees which are shorter will be treated as False and the first tree which is the same value or higher will be treated as True.

The index value of the elements in this list represents the distance from our current tree. So we can grab the index of the first True tree and plus one for zero-indexing. This value is then multiplied with the value in our tree_count matrix for the current tree. If we don’t hit a True value, then we’ve reach the edge and we can take the length of the whole list (all trees between current tree and the edge).

tree_count[h, v] *= next((idx + 1 for idx, tree in enumerate(shorter) if ~tree), len(shorter))

As the loop repeats and the matrix is rotated, the distances for the other three directions are multiplied in to the tree_count values.

Once we have our grid of values, we just need to find the greatest, representing the highest scenic score, which we can do with another NumPy array method: max.

tree_count.max()

The result will be the answer to puzzle 2.

Source Code

View the code on GitHub.

Would you like to read something else by me?

« «

» New post coming soon! »

« posts | «« home