Robert Mion

Posted on

# Treetop Tree House

## Part 1

1. Analyzing each cross-section
2. My algorithm in pseudocode
3. My algorithm in JavaScript

### Analyzing each cross-section

Given a grid of trees:

``````. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
``````

Knowing that all trees on the edge are fine:

``````* * * * *
* . . . *
* . . . *
* . . . *
* * * * *
``````

For each non-edge tree - for example, the center tree:

``````. . . . .
. . . . .
. . ? . .
. . . . .
. . . . .
``````

I need to separately analyze each slice of its cross-section:

``````. . 1 . .
. . 1 . .
4 4 ? 2 2
. . 3 . .
. . 3 . .
``````

As long as all values in any slice are less than the source tree, I can consider it `visible` like the ones on the edge.

How might I do this programmatically?

### My algorithm in pseudocode

Iterating through all non-edge trees in the grid:

``````Track the amount of trees visible - accounting for all edge trees
For each tree from the second row to the second-to-last
For each tree from the second column to the second-to-last
Set flag to false
Set directions to a 4-element array of relative (x,y) coordinates
Set index to 0
While flag is false and index is less than the length of directions
Generate a list of values originating from the current tree in a straight line stepping in the direction of the relative coordinate at the current index
If the maximum value in the list is less than the current tree's value
Set flag to true
Else
Increment index by 1
If flag is true
Increment the amount of trees visible by 1
Else
Don't increment the amount of trees visible
Return the amount of trees visible
``````

I wonder how close this will end up being to my actual algorithm.

Here I go!

### My algorithm in JavaScript

• It very closely matches my pseudocode
• The bulk of it is the part where I walk each slice of the cross-section
``````let grid = input
.split('\n')
.map(row => row.split('').map(Number))
let answer = grid.length * 4 - 4
for (let row = 1; row < grid.length - 1; row++) {
for (let col = 1; col < grid[row].length - 1; col++) {
let flag = false
let index = 0
let coords = [[-1,0],[0,1],[1,0],[0,-1]]
while (!flag && index < coords.length) {
let slice = []
let y = row + coords[index][0]
let x = col + coords[index][1]
while (
(y >= 0 && y < grid.length) &&
(x >= 0 && x < grid[y].length)
) {
slice.push(grid[y][x])
y += coords[index][0]
x += coords[index][1]
}
if (Math.max(...slice) < grid[row][col]) {
flag = true
}
index++
}
}
}
``````

## Part 2

1. Enter: more careful analysis of each tree
2. My algorithm in JavaScript

### Enter: more careful analysis of each tree

• It's no longer enough to spot a tree of equal or greater height
• My algorithm from Part 1 seems well set to adjust to this new requirement of checking nearby trees

### My algorithm in JavaScript

• I start both `for` loops at `0` instead of `1` to check every tree
• I track fewer variables inside the inner `for` loop
• I added a third condition to the `while` loop that causes it to break as soon as a number equal to or higher than the current tree is discovered
``````let grid = input
.split('\n')
.map(row => row.split('').map(Number))
for (let row = 0; row < grid.length; row++) {
for (let col = 0; col < grid[row].length; col++) {
let coords = [[-1,0],[0,1],[1,0],[0,-1]]
let scores = coords.map(coord => {
let slice = []
let y = row + coord[0]
let x = col + coord[1]
while (
(y >= 0 && y < grid.length) &&
(x >= 0 && x < grid[y].length) &&
(slice[slice.length - 1] || 0) < grid[row][col]
) {
slice.push(grid[y][x])
y += coord[0]
x += coord[1]
}
return slice.length
})
let product = scores.reduce((sum, score) => sum * score)
}
}
``````

I got confused when writing this bit of code:

``````(slice[slice.length - 1] || 0)
``````

It is designed to account for an empty list whose length would be 0 and therefore would not have an item at index `-1`.

## I did it!!

• I solved both parts!
• By using several nested `for` and `while` loops!
• Along with some `map()` and `reduce()`!

This ended up being a delightfully challenging twist on the now-common grid-themed puzzle!

I'm very glad I have accrued all my skills working with this type of puzzle from similar puzzles in years past.

It made solving this one much easier: I could focus on other parts of the problem...besides relative coordinates!