Advent of Code 2022 Day 8
Part 1
- Analyzing each cross-section
- My algorithm in pseudocode
- 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
- Enter: more careful analysis of each tree
- 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
forloops at0instead of1to check every tree - I track fewer variables inside the inner
forloop - I added a third condition to the
whileloop 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
forandwhileloops! - Along with some
map()andreduce()!
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)