Advent of Code 2022, Day 8: Treetop Tree House

Part A

On Day 8 we are building a tree house and we need to pick the best location for it, one that has enough tree cover and is not visible from outside. Elves have launched a quadcopter that generated a map of trees planted in a grid. This map contains the height of each tree on this grid:

``````30373
25512
65332
33549
35390
``````

I will just repeat part of description from the source here.

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.

Our task is to answer how many trees are visible from outside the grid.

We can write simple solution to that:

``````@map = File.readlines("8.txt", chomp: true).map { |row| row.split("").map(&:to_i) }
n = @map.size

def tree_visible?(x, y)
height = @map[y][x]

# check if all trees on the left are shorter
left = (0...x).all? { |i| @map[y][i] < height }

# check if all trees on the right are shorter
right = ((x + 1)..(@map.size - 1)).all? { |i| @map[y][i] < height }

# check if all trees aboe are shorter
up = (0...y).all? { |i| @map[i][x] < height }

# check if all trees below are shorter
down = ((y + 1)..(@map.size - 1)).all? { |i| @map[i][x] < height }

left || right || up || down
end

count = 0

n.times do |y|
n.times do |x|
count += 1 if tree_visible?(x, y)
end
end

puts count
``````

For each tree we call `tree_visible?` method to check if it is visible or not. And tree is considered visible if all trees in one direction are shorter.

It is not the solution I used myself, because it of it’s high time complexity. `tree_visible?` is scanning each full row and column and it’s time complexity is O(n). And then we call this method O(n^2) times, so total time complexity is O(n^3).

I wrote the above solution as an exercise while writing this article and compare it with my faster solution. But it turned out the input for this task is quite small and even O(n^3) solution gives answer instantly.

Let’s now explore faster solution. When scanning row or column in one direction we can determine all the trees in such direction.

``````n.times do |y|
highest = -1
n.times do |x|
elem = map[y][x]
if elem > highest
visible.push([x, y])
highest = elem
end
end
end
``````

For each row scanned we maintain the highest tree seen so far. It starts with value of -1 for the tree on the edge. While iterating if a tree is higher than the highest tree so far it is visible from that particular direction. We need to update `highest` value. We can store positions of visible trees in some array.

We need to repeat above operation from all other directions, so we scan each row twice, from left to right and from right to left. And the same for each column.

Our `visible` array contains positions of all visible trees, but it can contain some duplicates. So in the end we need to give the size of unique elements in this array.

Here is the full code:

``````map = File.readlines("8.txt", chomp: true).map { |row| row.split("").map(&:to_i) }
n = map.size
visible = []

# checking from the left

n.times do |y|
highest = -1
n.times do |x|
elem = map[y][x]
if elem > highest
visible.push([x, y])
highest = elem
end
end
end

# checking from the right

n.times do |y|
highest = -1
(n - 1).downto(0) do |x|
elem = map[y][x]
if elem > highest
visible.push([x, y])
highest = elem
end
end
end

# checking from the top

n.times do |x|
highest = -1
n.times do |y|
elem = map[y][x]
if elem > highest
visible.push([x, y])
highest = elem
end
end
end

# checking from the right

n.times do |x|
highest = -1
(n - 1).downto(0) do |y|
elem = map[y][x]
if elem > highest
visible.push([x, y])
highest = elem
end
end
end

puts visible.uniq.size
``````

This solution is O(n^2). We can compare it with the more naive O(n^3) solution on larger data set:

``````File.write("8large.txt", (0...2500).map { (0...2500).map { rand(10) }.join }.join("\n"))
``````
``````\$ time ruby 8a.rb
29526
ruby 8a.rb  1.79s user 0.04s system 99% cpu 1.843 total

\$ time ruby 8brute.rb
29526
ruby 8brute.rb  8.85s user 0.07s system 99% cpu 8.932 total
``````

Part B

After sorting out tree cover problem, Elves want to build tree house at the location with the best scenic score, in other words they want to see a lot of trees.

In the example above, consider the middle 5 in the second row:

``````30373
25512
65332
33549
35390
``````
• Looking up, its view is not blocked; it can see 1 tree (of height 3).
• Looking left, its view is blocked immediately; it can see only 1 tree (of height 5, right next to it).
• Looking right, its view is not blocked; it can see 2 trees.
• Looking down, its view is blocked eventually; it can see 2 trees (one of height 3, then the tree of height 5 that blocks its view).

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
``````
• Looking up, its view is blocked at 2 trees (by another tree with a height of 5).
• Looking left, its view is not blocked; it can see 2 trees.
• Looking down, its view is also not blocked; it can see 1 tree.
• Looking right, its view is blocked at 2 trees (by a massive tree of height 9).

This tree’s scenic score is 8 (2 * 2 * 1 * 2); this is the ideal spot for the tree house.

Our task is to answer what is the highest scenic score possible for any tree.

Here is my solution:

``````map = File.readlines("8.txt", chomp: true).map { |row| row.split("").map(&:to_i) }
n = map.size

results = []
n.times { |i| results[i] = Array.new(n, 1) }

# checking from the left

n.times do |y|
heights = []
n.times do |x|
elem = map[y][x]
distance = x - (heights[elem] || 0)
elem.downto(0) { |height| heights[height] = x }
results[y][x] *= distance
end
end

# checking from the right

n.times do |y|
heights = []
(n - 1).downto(0) do |x|
elem = map[y][x]
distance = (x - (heights[elem] || (n - 1))).abs
elem.downto(0) { |height| heights[height] = x }
results[y][x] *= distance
end
end

# checking from the top

n.times do |x|
heights = []
n.times do |y|
elem = map[y][x]
distance = (y - (heights[elem] || 0)).abs
elem.downto(0) { |height| heights[height] = y }
results[y][x] *= distance
end
end

# checking from the right

max = 0
n.times do |x|
heights = []
(n - 1).downto(0) do |y|
elem = map[y][x]
distance = (y - (heights[elem] || (n - 1))).abs
elem.downto(0) { |height| heights[height] = y }
results[y][x] *= distance

if results[y][x] > max
max = results[y][x]
end
end
end

puts max
``````

It is similar to the solution for Part A. We are scanning each row and column twice from both directions, but this time we maintain the last position of tree of all given heights. When we see a tree with height 7, we store it’s position in the array `heights`, but we also store that at the same position are trees with the heights of 6, 5, 4, 3, 2, 1 and 0. This way when we later see a tree of height 2 we can easily check what was the last tree of height 2 or heigher. If there is no element in `heights` array for given height it means that we didn’t see any tree blocking our view.

We need to repeat this process for all directions. Add the beginning we are creating results array storing scenic scores for all trees. It is initiated with 1 for all trees. When we determine a viewing distance for particular direction we can just multiply the scenic score by this value.

In the end we need to find the highest scenic score in the `results` array.