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
Each tree is represented as a single digit whose value is its height, where 0 is the shortest and 9 is the tallest.
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.
All of the trees around the edge of the grid are visible - since they are already on the edge, there are no trees to block the view. In this example, that only leaves the interior nine trees to consider:
With 16 trees visible on the edge and another 5 visible in the interior, a total of 21 trees are visible in this arrangement.
Consider your map; how many trees are visible from outside the grid?
# Python imports
from pathlib import Path
import numpy as np
test = Path("data/day08_test.txt") # test data
data = Path("data/day08_data.txt") # puzzle data
def parse_input(fpath: Path) -> np.array:
"""Parse puzzle input into
:param fpath: path to puzzle input
"""
with fpath.open() as ifh:
data = np.array([list(_.strip()) for _ in ifh.readlines()])
return data.astype(int)
def count_visible_trees(arr: np.array) -> int:
"""Return the count of visible trees in the passed array
:param arr: numpy array, each element is a tree height
This solution is fairly hacky and brute force. There must be a more
elegant solution!
"""
nrow, ncol = arr.shape # handy for calculations later
# Keep a shadow array with visibility count on all four sides for each tree
# Each element will be incremented by one if a tree is visible from a side
viscount = np.zeros(arr.shape, dtype=int)
# Iterate along array sides, incrementing the shadow array when a tree is
# visible from that side
# Rows first
for ridx, row in enumerate(arr):
rmax = max(row)
# forward
curmax = -1
for cidx, val in enumerate(row):
if val > curmax:
viscount[ridx][cidx] += 1
curmax = val
# reverse
curmax = -1
for cidx, val in enumerate(row[::-1]):
if val > curmax:
viscount[ridx][nrow-cidx-1] += 1
curmax = val
# Then columns
for cidx, col in enumerate(arr.T):
cmax = max(col)
# forward
curmax = -1
for ridx, val in enumerate(col):
if val > curmax:
viscount[ridx][cidx] += 1
curmax = val
# reverse
curmax = -1
for ridx, val in enumerate(col[::-1]):
if val > curmax:
viscount[nrow-ridx-1][cidx] += 1
curmax = val
return (viscount > 0).sum()
def part1(fpath: Path) -> int:
"""Solve the puzzle
:param fpath: path to puzzle input
"""
treegrid = parse_input(fpath)
return count_visible_trees(treegrid)
part1(test)
21
part1(data)
1827
Content with the amount of tree cover available, the Elves just need to know the best spot to build their tree house: they would like to be able to see a lot of trees.
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.)
The Elves don't care about distant trees taller than those found by the rules above; the proposed tree house has large eaves to keep it dry, so they wouldn't be able to see higher than the tree house anyway.
In the example above, consider the middle 5 in the second row:
30373
25512
65332
33549
35390
A tree's scenic score is found by multiplying together its viewing distance in each of the four directions. For this tree, this is 4 (found by multiplying 1 * 1 * 2 * 2).
However, you can do even better: consider the tree of height 5 in the middle of the fourth row:
30373
25512
65332
33549
35390
This tree's scenic score is 8 (2 * 2 * 1 * 2); this is the ideal spot for the tree house.
Consider each tree on your map. What is the highest scenic score possible for any tree?
def calc_dir_score(arr: np.array) -> int:
"""Return the scenic score component in one direction"""
score = 0
for val in arr:
score += 1
if val:
return score
return score
def calc_scenic_score(arr: np.array) -> np.array:
"""Return the scenic score for each tree in the passed array
:param arr: numpy array, elements are heights for each tree
This is a hacky solution. There must be a more elegant
route to the answer!
"""
nrow, ncol = arr.shape # handy for calculations later
# Keep a shadow array with scenic score for each tree
scenics = np.zeros(arr.shape, dtype=int)
# Tree heights can be 0-9; iterate over these values to identify
# the visible landscapes for each tree height
# For each tree at the current height, calculate the scenic score
# from the visible extent in each compass direction
for height in range(10): # iterate over tree heights
trees = (arr == height).astype(int) # trees of current height
harr = (arr >= height).astype(int) # visible extent (1 = view blocked)
for rtree, ctree in np.argwhere(trees): # iterate over trees of given height
score = 1 # instantiate score, multiplied by a factor for each direction
# up
up = harr.T[ctree][:rtree][::-1]
score *= calc_dir_score(up)
# down
down = harr.T[ctree][rtree+1:]
score *= calc_dir_score(down)
# left
left = harr[rtree][:ctree][::-1]
score *= calc_dir_score(left)
# right
right = harr[rtree][ctree+1:]
score *= calc_dir_score(right)
# Update array with total scenic score
scenics[rtree][ctree] = score
return scenics
def part2(fpath: Path):
"""Solve the puzzle
:param fpath: path to puzzle input
"""
treegrid = parse_input(fpath)
scores = calc_scenic_score(treegrid)
return scores.max()
part2(test)
8
part2(data)
335580