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