DEV Community

Cover image for Treetop Tree House
Robert Mion
Robert Mion

Posted on

Treetop Tree House

#discuss

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:

. . . . . . . . . . . . . . . . . . . . . . . . .
Enter fullscreen mode Exit fullscreen mode

Knowing that all trees on the edge are fine:

* * * * * * . . . * * . . . * * . . . * * * * * *
Enter fullscreen mode Exit fullscreen mode

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

. . . . . . . . . . . . ? . . . . . . . . . . . .
Enter fullscreen mode Exit fullscreen mode

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

. . 1 . . . . 1 . . 4 4 ? 2 2 . . 3 . . . . 3 . .
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

I got confused when writing this bit of code:

(slice[slice.length - 1] || 0)
Enter fullscreen mode Exit fullscreen mode

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!

Top comments (0)