« posts | «« home

# Day 8: Treetop Tree House

View puzzle page »

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.

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.

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

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.

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

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.

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.

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

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

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