# [Advent Of Code 2022] Day 8: Treetop Tree House [SPOILERS]

Didn’t we all want a tree house as children?

Python Solution
``````def read_file(file: TextIO):
lines = (line.rstrip() for line in file)
grid = [[int(c) for c in line] for line in lines]
assert all(len(row) == len(grid) for row in grid)
return grid

def part1(file: TextIO) -> int:
"""Solve the first part of the puzzle."""
height, width = len(grid), len(grid)

def generate_larger(positions):
threshold = -1
for pos in positions:
y, x = pos
value = grid[y][x]
if value > threshold:
yield pos
threshold = value

seen = set()
for y in range(height):
seen.update(generate_larger((y, x) for x in range(width)))
seen.update(generate_larger((y, x) for x in reversed(range(width))))
for x in range(width):
seen.update(generate_larger((y, x) for y in range(height)))
seen.update(generate_larger((y, x) for y in reversed(range(height))))
return len(seen)

def scenic_score(grid, y, x):
"""Calculate the scenic score of the tree at (x, y)."""
threshold = grid[y][x]

def count_visible(positions):
count = 0
for pos in positions:
count += 1
y, x = pos
if grid[y][x] >= threshold:
break
return count

north = count_visible((y2, x) for y2 in reversed(range(y)))
south = count_visible((y2, x) for y2 in range(y + 1, len(grid)))
west = count_visible((y, x2) for x2 in reversed(range(x)))
east = count_visible((y, x2) for x2 in range(x + 1, len(grid[y])))
return north * south * west * east

def part2(file: TextIO) -> int:
"""Solve the second part of the puzzle."""
height, width = len(grid), len(grid)
return max(
scenic_score(grid, y, x)
for y in range(height)
for x in range(width))
``````

The problem reminded me of a nice little sudoku-like puzzle called Towers.

People were speculating that the next puzzle might involve Dijkstra’s. I think I got in my head and immediately tried to solve this with Dijkstra’s without thinking it through. It didn’t make a ton of sense. Today was my worst performance so far this year.

How I tried to use Dijkstra's
``````mark edges visible
to_visit = visible
while to_visit:
new_node = []
for node in to_visit:
for neighbor in node.neighbors:
if neighbor is visible from edge through node:
to_visit = new_node
``````
Python solution
``````DIRECTIONS = [-1j ** i for i in range(4)]

def part1(self, board: InputType) -> int:
count = 0
for tree in board:
for direction in DIRECTIONS:
cur = tree + direction
while cur in board:
if board[cur] >= board[tree]:
break
cur += direction
else:
count += 1
break
return count

def part2(self, board: InputType) -> int:
scores = []
for tree in board:
visible = []
for direction in DIRECTIONS:
cur = tree + direction
num = 0
while cur in board:
num += 1
if board[cur] >= board[tree]:
break
cur += direction
visible.append(num)
scores.append(self.mult(visible))
return max(scores)
``````

I got to reuse an existing `Board` from prior years for this.

I had something fancy planned for part 2, but it turned out that I didn’t read the instructions carefully enough so that was wasted effort Ruby Solution
``````require 'set'

grid = File.readlines('inputs/08.txt', chomp: true).map { |line| line.chars.map(&:to_i) }
transposed_grid = grid.transpose

visible = Set.new
max_heights = Array.new(4) { Array.new(grid.size, -1) }
max_scenic_score = 0

grid.size.times do |row|
grid.size.times do |col|
if col.positive? && row.positive? && col < grid.size - 1 && row < grid.size - 1
view_lines = [grid[row][0..col-1].reverse, grid[row][col+1..], transposed_grid[col][row+1..], transposed_grid[col][0..row-1].reverse]
scenic_score = view_lines.map {|heights| heights.find_index { |height| height >= grid[row][col] }&.succ || heights.size}.inject(:*)
max_scenic_score = scenic_score if scenic_score > max_scenic_score
end

if grid[row][col] > max_heights[row]
visible << [row, col]
max_heights[row] = grid[row][col]
end

if grid[row][col] > max_heights[col]
visible << [row, col]
max_heights[col] = grid[row][col]
end

if grid[row][grid.size - col - 1] > max_heights[row]
visible << [row, grid.size - col - 1]
max_heights[row] = grid[row][grid.size - col - 1]
end

if grid[grid.size - row - 1][col] > max_heights[col]
visible << [grid.size - row - 1, col]
max_heights[col] = grid[grid.size - row - 1][col]
end
end
end

a = visible.size
b = max_scenic_score

require 'minitest/autorun'

describe 'day 08' do
it 'part a' do assert_equal 1_794, a end
it 'part b' do assert_equal 199_272, b end
end
``````