Treetop Tree House

Advent of Code 2022 Day 8

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++
    }
    if (flag) answer++
  }
}
return answer

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))
let answer = 0
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)
    answer = product > answer? product : answer
  }
}
return answer

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!