> [!META]- Inline Metadata > [tags:: #advent-of-code/2022] > [status:: done] > [link::] > [up:: [[Advent of Code 2022 MOC]]] ## Problem 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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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: - The top-left `5` is _visible_ from the left and top. (It isn't visible from the right or bottom since other trees of height `5` are in the way.) - The top-middle `5` is _visible_ from the top and right. - The top-right `1` is not visible from any direction; for it to be visible, there would need to only be trees of height _0_ between it and an edge. - The left-middle `5` is _visible_, but only from the right. - The center `3` is not visible from any direction; for it to be visible, there would need to be only trees of at most height `2` between it and an edge. - The right-middle `3` is _visible_ from the right. - In the bottom row, the middle `5` is _visible_, but the `3` and `4` are not. 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?_ ## Scratchpad We want count of all visible trees. So start with lengths of edges (first and last row, first and last column) to add to count. Then iterate through each line: total_input[1:-1] for each row: row[1:-1] at each item, get a sub-list (column above, column below, row to right, row to left) and see if tree is max. What I ended up doing was generating the subcolumns and sub rows, then checking value agains the max. ### Part 2 This approach is similar, we make the subcolumns and subrows, but reverse the above and behind ones because we will ~~use max~~ to get the index of the nearest tree that's >= the height of the one we're checking. Note: Ended up not using `max()` here, instead used a list comprehension because `max()` doesn't get us what we want. You still have to reverse the subcolumn and subrow because then you can get the nearest taller or equal height tree with the same index no matter which subcolumn or subrow you're examining. If the value (tree in question) is greater than the max of a sublist in any given direction, the score is the length of that list. If it's not, then you have to find the nearest tree height that is >= value ## Solution ```python import math TEST_INPUT = """ 30373 25512 65332 33549 35390 """ def count_visible_trees(grid: str) -> int: rows = grid.split() columns = ["".join(x) for x in zip(*rows)] # Initialize count to count all the outer trees of the grid count = len(rows[0]) * 2 + (len(rows) - 2) * 2 for row_idx, row in enumerate(rows[1:-1]): row_idx += 1 for col_idx, value in enumerate(row[1:-1]): col_idx += 1 # Get subcolumns and subrows non-inclusive of value in question above_subcolumn = columns[col_idx][:row_idx] below_subcolumn = columns[col_idx][row_idx + 1 :] row_behind = row[:col_idx] row_ahead = row[col_idx + 1 :] # Check column above if value > max(above_subcolumn): count += 1 continue # Check column below elif value > max(below_subcolumn): count += 1 continue # Check row behind elif value > max(row_behind): count += 1 continue # Check row ahead elif value > max(row_ahead): count += 1 continue return count def get_best_scenic_score(grid: str) -> int: """ Answers part 2 """ rows = grid.split() columns = ["".join(x) for x in zip(*rows)] scenic_scores = [] for row_idx, row in enumerate(rows[1:-1]): row_idx += 1 for col_idx, value in enumerate(row[1:-1]): col_idx += 1 """ Get subcolumns and subrows non-inclusive of value in question Reversing the list normalizes the above subcolumn and row_behind to be from the perspective of the tree (value) we're examining. This allows us to use a single index ([0]) when getting the nearest taller tree. """ scenic_score = [] above_subcolumn = list(reversed(columns[col_idx][:row_idx])) below_subcolumn = columns[col_idx][row_idx + 1 :] row_behind = list(reversed(row[:col_idx])) row_ahead = row[col_idx + 1 :] for direction in (above_subcolumn, below_subcolumn, row_behind, row_ahead): if value > max(direction): scenic_score.append(len(direction)) else: distance = [ direction.index(tree) for tree in direction if tree >= value ][0] + 1 scenic_score.append(distance) scenic_scores.append(math.prod(scenic_score)) return max(scenic_scores) if __name__ == "__main__": print(f"Expected answer with test input: 21") print(f"Computed answer with test input: {count_visible_trees(grid=TEST_INPUT)}") print(f"Expected answer for part 2 with test input: 8") print(f"Part 2 with test input {get_best_scenic_score(TEST_INPUT)}") with open("input.txt", "r") as f: input_string = f.read() print(f"Part 1 count {count_visible_trees(grid=input_string)}") print(f"Part 2 best scenic score: {get_best_scenic_score(grid=input_string)}") ``` ## Things I Learned