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

Programming
1

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

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

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

    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."""
    grid = read_file(file)
    height, width = len(grid), len(grid[0])
    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.

2

Make it work – cleaned code

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:
                new_node.add(neighbor)
                visible.add(neighbor)
    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.

3

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 :man_facepalming:

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[0][row]
      visible << [row, col]
      max_heights[0][row] = grid[row][col]
    end

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

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

    if grid[grid.size - row - 1][col] > max_heights[3][col]
      visible << [grid.size - row - 1, col]
      max_heights[3][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