Page Navigation
Problem Intro
We’ve arrived at an area where tall trees are arranged in a rigid grid. The trees are of varying heights.
The locations and heights of the trees is given by our input data, which looks something like this:
30373
25512
65332
33549
35390
Part 1
The elves want to determine if our input area provides sufficient tree cover. A tree in any given position is visible from outside the grid if:
- The tree is on any edge.
- The tree is taller than any trees between this tree and any edge.
How many trees are visible from outside the grid?
We’re told we only have to consider orthogonal directions, i.e. left, right, up and down. We don’t have to worry about diagonals.
Here’s my approach:
- Create a Grid class to hold the locations and heights of the trees. Pass in the rows of int to create it.
- Also store the data in columns, to make life easy.
- Iterate through all trees in the grid.
- If this tree is on an edge, it is visible from the outside.
- If this tree is taller than any trees to the left, right, above or below (as seen in the map), it is visible from the outside. If so, it is visible.
Simple enough!
Let’s read in the data:
with open(INPUT_FILE, mode="rt") as f:
data = f.read().splitlines()
rows = [[int(x) for x in row] for row in data]
Here I’m using a nested comprehension to get each row of numbers, and then for each row, to convert the number to an int.
Next, here is a class to represent any given 2D (x,y) Point. I’m using a dataclass. Nothing new to say about this.
@dataclass(frozen=True)
class Point():
""" Point class """
x: int
y: int
Next, I create a Grid class. This is where all the good stuff happens…
class Grid():
""" Represents a grid of trees heights """
def __init__(self, grid_rows: list) -> None:
""" Expects data in the format... [[3, 0, 3, 7, 3], [2, 5, 5, 1, 2], ...] """
self.rows: list[list[int]] = grid_rows
self.cols = list(zip(*self.rows))
self._width = len(self.cols)
self._height = len(self.rows)
self.size = self._width * self._height
def height_at_point(self, point: Point) -> int:
return self.rows[point.y][point.x]
def is_visible(self, point: Point) -> bool:
""" A tree is visible if it is on any edge,
or if there are no taller trees in the same row or column. """
# check if it's on an edge
if point.x == 0 or point.x == self._width-1:
return True
if point.y == 0 or point.y == self._height-1:
return True
value = self.height_at_point(point)
# Check if taller than any other tree in the row. If so, it is visible.
if value > max(self.rows[point.y][0:point.x]): return True
if value > max(self.rows[point.y][point.x+1:]): return True
# Now check the column.
if value > max(self.cols[point.x][0:point.y]): return True
if value > max(self.cols[point.x][point.y+1:]): return True
return False
def get_hidden_trees(self) -> set[Point]:
""" Returns all locations where trees are hidden from view. """
return {Point(x, y) for x in range(self._height)
for y in range(self._width)
if not self.is_visible(Point(x,y))}
def __repr__(self):
return (f"{self.__class__.__name__}"
+ f"(size={self.size}, rows={len(self.rows)}, cols={len(self.cols)})")
- The
__init__()method:- Takes our
listoflistsofint, and stores it in theself.rowsproperty. - Then uses zip to obtain a new
listthat represents the data as columns rather than rows. - We store the width and height of the
Grid, for convenience.
- Takes our
- The
height_at_point(self, point: Point)simply returns the value stored at the given location. - The
is_visible()method:- Checks whether the
Pointis on an edge, by first checking if itsxcomponent is equal to0or thewidth-1, and by then checking if itsycomponent is equal to0or theheight-1. - Then retrieves the value (height) of our tree.
- Then checks whether our tree is taller than any tree to the left or right. I’m slicing to get left and right.
- Then checks whether our tree is taller than any tree above or below. I’m slicing to get above and below.
- If any of the conditions above are
True, then this tree is visible.
- Checks whether the
- The
get_hidden_trees()method uses a multi-sequence set comprehension as a short hand for iterating through all x, then all y, and then checking whether the value at that location is visible, using hteis_visible()method that we previously defined.
I didn’t actually need to return a set of all the hidden trees. Instead, I could have used the same method to count all the trees that are visible. But I decided to return the entire set of hidden trees, just in case we need them later. Turns out we didn’t!!
Finally, we solve the problem:
grid = Grid(rows)
print(grid)
# Part 1 - How many visible trees?
hidden_trees = grid.get_hidden_trees()
print("Part 1:")
print(f"Number of hidden trees={len(hidden_trees)}")
print(f"Number of visible trees={grid.size - len(hidden_trees)}")
Part 2
The elves are satisfied with the area! Now they want to find the best tree for their treehouse. The best tree is the tree with the highest scenic score.
What is the highest scenic score possible for any tree in our grid?
We’re told:
- Scenic score is given by product of viewing distance in each of the four directions, i.e. left, right, up, down.
- Viewing distance is: how far away is the furthest tree we can see in this direction?
- The viewing distance in any direction is given by: the difference between our location, and the nearest tree that is at least as tall as our tree. I.e. if any tree is as tall as our tree or taller, then we can’t see past it.
- If we’re on an edge looking out, then the viewing distance is 0 in that direction. (And, thus, the scenic score will be 0 for any tree on an edge.)
Here’s my solution…
First, we need to add a couple of methods to our Grid class:
def get_scenic_scores(self) -> list[int]:
""" Returns the scenic scores for every tree in the grid """
scenic_scores = []
# process across then down
for y in range(self._width):
for x in range(self._height):
point = Point(x, y)
score = self.get_scenic_score_for_point(point)
scenic_scores.append(score)
return scenic_scores
def get_scenic_score_for_point(self, point: Point) -> int:
""" Scenic score is given by product of viewing distance in each of the four directions.
Viewing distance is given by how far away is the nearest tree that is at least as tall as this one.
Viewing distance is always 0 when looking out from an edge. """
this_value = self.height_at_point(point)
# Use generators, since we will just keep getting the next tree
# until we reach a tree at least as tall. In theory, this is slightly more efficient than lists.
left = (x for x in reversed(self.rows[point.y][0:point.x]))
right = (x for x in self.rows[point.y][point.x+1:])
up = (y for y in reversed(self.cols[point.x][0:point.y]))
down = (y for y in self.cols[point.x][point.y+1:])
viewing_distances = [] # store our four distances
for direction in (left, right, up, down):
distance = 0 # if we're on the edge, this will be the final score.
for value in direction:
if value < this_value:
distance += 1
else: # this tree is at least as tall as our tree. We can't see past it.
distance += 1 # This is the last tree we can see
break # exit inner for
viewing_distances.append(distance)
return math.prod(viewing_distances)
- The
get_scenic_score_for_point()method:- Creates generators to return all the trees in each direction, i.e. left, right, up and down.
- I’ve used generators, since we don’t need the whole list in each case. We can stop once we’ve found a tree that is at least as tall as our tree. In theory, this will perform a little better.
- Note that I’ve
reversedtheleftandupdirections, since we always want to step away from our tree, one at a time. If we’re going left, that means subtracting one from the x value with each step; and if we’re going up, that means substracting one from the y value with each step.
- Creates generators to return all the trees in each direction, i.e. left, right, up and down.
- We then iterate through each direction one at a time, i.e. left, right, up, down.
- Initialise the viewing distance to 0. (It will stay 0 if we’re looking out from an edge.)
- Return the next tree from generator. If it is shorter than our tree, increment our viewing distance.
- If it is as tall or taller, increment our viewing distance and exit the loop. I.e. we can’t see past this tree.
- Finally, return the product of our four viewing distances.
- The
get_scenic_scores()method calls ourget_scenic_score_for_point()method for each tree in the grid. It stores each score in alist, and returns thelist.
Finally, we solve like this:
# Part 2 - What is the maximum scenic score?
print("\nPart 2:")
scenic_scores = grid.get_scenic_scores()
print(f"Highest score={max(scenic_scores)}")
Simples!!
Results
The final code looks like this:
from dataclasses import dataclass
import math
from pathlib import Path
import time
SCRIPT_DIR = Path(__file__).parent
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
@dataclass(frozen=True)
class Point():
""" Point class """
x: int
y: int
class Grid():
""" Represents a grid of trees heights """
def __init__(self, grid_rows: list) -> None:
""" Expects data in the format... [[3, 0, 3, 7, 3], [2, 5, 5, 1, 2], ...] """
self.rows: list[list[int]] = grid_rows
self.cols = list(zip(*self.rows))
self._width = len(self.cols)
self._height = len(self.rows)
self.size = self._width * self._height
def height_at_point(self, point: Point) -> int:
return self.rows[point.y][point.x]
def is_visible(self, point: Point) -> bool:
""" A tree is visible if it is on any edge,
or if there are no taller trees in the same row or column. """
# check if it's on an edge
if point.x == 0 or point.x == self._width-1:
return True
if point.y == 0 or point.y == self._height-1:
return True
value = self.height_at_point(point)
# Check if taller than any other tree in the row. If so, it is visible.
if value > max(self.rows[point.y][0:point.x]): return True
if value > max(self.rows[point.y][point.x+1:]): return True
# Now check the column.
if value > max(self.cols[point.x][0:point.y]): return True
if value > max(self.cols[point.x][point.y+1:]): return True
return False
def get_hidden_trees(self) -> set[Point]:
""" Returns all locations where trees are hidden from view. """
return {Point(x, y) for x in range(self._height)
for y in range(self._width)
if not self.is_visible(Point(x,y))}
def get_scenic_scores(self) -> list[int]:
""" Returns the scenic scores for every tree in the grid """
scenic_scores = []
# process across then down
for y in range(self._width):
for x in range(self._height):
point = Point(x, y)
score = self.get_scenic_score_for_point(point)
scenic_scores.append(score)
return scenic_scores
def get_scenic_score_for_point(self, point: Point) -> int:
""" Scenic score is given by product of viewing distance in each of the four directions.
Viewing distance is given by how far away is the nearest tree that is at least as tall as this one.
Viewing distance is always 0 when looking out from an edge. """
this_value = self.height_at_point(point)
# Use generators, since we will just keep getting the next tree
# until we reach a tree at least as tall. In theory, this is slightly more efficient than lists.
left = (x for x in reversed(self.rows[point.y][0:point.x]))
right = (x for x in self.rows[point.y][point.x+1:])
up = (y for y in reversed(self.cols[point.x][0:point.y]))
down = (y for y in self.cols[point.x][point.y+1:])
viewing_distances = [] # store our four distances
for direction in (left, right, up, down):
distance = 0 # if we're on the edge, this will be the final score.
for value in direction:
if value < this_value:
distance += 1
else: # this tree is at least as tall as our tree. We can't see past it.
distance += 1 # This is the last tree we can see
break # exit inner for
viewing_distances.append(distance)
return math.prod(viewing_distances)
def __repr__(self):
return (f"{self.__class__.__name__}"
+ f"(size={self.size}, rows={len(self.rows)}, cols={len(self.cols)})")
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read().splitlines()
rows = [[int(x) for x in row] for row in data]
grid = Grid(rows)
print(grid)
# Part 1 - How many visible trees?
hidden_trees = grid.get_hidden_trees()
print("Part 1:")
print(f"Number of hidden trees={len(hidden_trees)}")
print(f"Number of visible trees={grid.size - len(hidden_trees)}")
# Part 2 - What is the maximum scenic score?
print("\nPart 2:")
scenic_scores = grid.get_scenic_scores()
print(f"Highest score={max(scenic_scores)}")
if __name__ == "__main__":
t1 = time.perf_counter()
main()
t2 = time.perf_counter()
print(f"Execution time: {t2 - t1:0.4f} seconds")
The output looks like this:
Part 1:
Number of hidden trees=7981
Number of visible trees=1820
Part 2:
Highest score=385112
Execution time: 0.0712 seconds
Visualisation
Just for fun, let’s render our tree grid as an image. This is pretty easy to do with the Python Imagining Library (PIL). First we need to install Pillow.
py -m pip install Pillow
Here are the code changes…
First:
- Import from PIL.
- Store a boolean that turns on or off the image rendering, as required.
- Decide where we want to put the generated image file.
from PIL import Image
RENDER = True
OUTPUT_FILE = Path(SCRIPT_DIR, "output/output.png")
Next we’ll add a render_iamge() method to our Grid class:
def render_image(self, target_width:int=600) -> Image.Image:
""" Render grid as a heatmap image
Args:
width (int, optional): Target width, in pxiels. Defaults to 600.
"""
scale = target_width // self._width # our original image is only a few pixels across. We need to scale up.
hidden_trees = self.get_hidden_trees()
# Flatten our x,y array into a single list of height values
# If the tree is a hidden tree, set its height to -1 in the flattened array
height_values = [self.height_at_point(Point(x,y))
if Point(x,y) not in hidden_trees else -1
for y in range(self._height)
for x in range(self._width)]
max_height = max(height_values)
# create a new list of RGB values, where each is given by an (R,G,B) tuple.
# To achieve a yellow->amber->red effect, we want R to always be 255, B to always be 0, and G to vary based on height
pixel_colour_map = list(map(
lambda x: (255, int(255*((max_height-x)/max_height)), 0) if x >= 0 else (0, 0, 0),
height_values))
image = Image.new(mode='RGB', size=(self._width, self._height))
image.putdata(pixel_colour_map) # load our colour map into the image
# scale the image and return it
return image.resize((self._width*scale, self._height*scale), Image.Resampling.NEAREST)
This is how it works:
- Take our 2D grid, and convert it to a single flattened list of int values, which are the heights at each location. I.e. all the values from the first row, then all the values from the second row, and so on.
- We’re using a list comprehension to do this.
- Note that our comprehension returns the
heightif the tree is visible, but otherwise returns-1. This is how we’ll identify hidden trees later.
- Create an RGB pixel map, by convert each single height value (which is always going to be in the range 0-9) to an RGB tuple.
- If the tree is not hidden, then our tuple is
(255, x, 0)where the value of x is dependent on the height. - If the tree is hidden, we set our tuple to
(0, 0, 0), i.e. black.
- If the tree is not hidden, then our tuple is
- Create a new PIL
Imageobject, by loading in our pixel map. - Finally, resize the pixel map to something big enough to see!
Lastly, we just need to save the Image as a file. If the parent directory of the file doesn’t exist, then create it:
if RENDER:
dir_path = Path(OUTPUT_FILE).parent
if not Path.exists(dir_path):
Path.mkdir(dir_path)
image = grid.render_image(400)
image.save(OUTPUT_FILE)
With my actual data, the output looks like this:
