Advent of Code: Day 8

Numpy arrays and vectorization

Photo by Sebastian Unrau on Unsplash

I’m a bit behind, and I don’t think I’ll finish this year. I’ll try to finish the rest of the problems. However, I stopped after I got sick and am not the best right now, and I’ve been busy with work. For Day 8, we have a field of trees represented by a matrix of values. In Part 1, we need to determine whether trees are visible.

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 expedition comes across a peculiar patch of tall trees all planted carefully in a grid. The Elves explain that a previous expedition planted these trees as a reforestation effort. Now, they're curious if this would be a good location for a tree house.

First, determine whether there is enough tree cover here to keep a tree house hidden. To do this, you need to count the number of trees that are visible from outside the grid when looking directly along a row or column.

The Elves have already launched a quadcopter to generate a map with the height of each tree (your puzzle input). For example:

30373
25512
65332
33549
35390

To determine this, I used NumPy with arrays and used the NumPy vectorizing syntax to determine whether all the trees in one direction were shorter than the current tree.

For the second part, we have to find the maximum scenic score of a tree. The scenic score is the product of all the viewing distances in each direction. This score is calculated for each tree, and then the max is found.

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

To find this, the simplest way was to loop in each direction and break when a tree of equal or greater height was found; the code is written below. Overall the algorithm takes O(N²) in the worst case because we have to go over each tree, and then we might have to go to the end of the input for each. There might be a faster way, but I have yet to find it yet.

import numpy as np
import itertools


def parse_data(data):
    data = data.splitlines()
    arr = np.zeros((len(data), len(data[0])), dtype=np.int32)
    for r in range(len(data[0])):
        for c in range(len(data[1])):
            arr[r, c] = int(data[r][c])
    return arr


# is tree at r, c visible
def is_visible(trees, r, c):
    return (
        r == 0
        or c == 0
        or r == trees.shape[0] - 1
        or c == trees.shape[0] - 1
        or np.all(trees[r, :c] < trees[r, c])
        or np.all(trees[r, c + 1 :] < trees[r, c])
        or np.all(trees[:r, c] < trees[r, c])
        or np.all(trees[r + 1 :, c] < trees[r, c])
    )


def scenic_score(trees, r, c):
    up = down = left = right = 0
    # up direction
    for k in range(r - 1, -1, -1):
        if trees[k, c] >= trees[r, c]:
            up += 1
            break
        up += 1
    # down direction
    for k in range(r + 1, trees.shape[0]):
        if trees[k, c] >= trees[r, c]:
            down += 1
            break
        down += 1
    # left direction
    for k in range(c - 1, -1, -1):
        if trees[r, k] >= trees[r, c]:
            left += 1
            break
        left += 1
    # right direction
    for k in range(c + 1, trees.shape[1]):
        if trees[r, k] >= trees[r, c]:
            right += 1
            break
        right += 1

    print(up, down, left, right)
    return up * down * left * right


def max_scenic_score(forest):
    # Keep track of the maximum scenic score seen so far
    max_score = 0
    for r, c in itertools.product(range(forest.shape[0]), range(forest.shape[1])):
        score = scenic_score(trees, r, c)
        if score > max_score:
            max_score = score
    return max_score


def count_visible(trees):
    return int(
        sum(
            is_visible(trees, r, c)
            for r, c in itertools.product(range(trees.shape[0]), range(trees.shape[1]))
        )
    )


if __name__ == "__main__":
    with open("input.txt") as file:
        data = file.read()
        trees = parse_data(data)
        count = count_visible(trees)
        print(f"Count is {count}")
        max_score = max_scenic_score(trees)
        print(f"Max scenic score is {max_score}")