Advent of Code 2023 Day 23
Part 1
Shortest? Psh. Longest path!
Any time I see longest
or shortest
or any simile in the challenge's ultimate question, I cringe.
Because I am not comfortable writing or using any algorithms designed to solve those problems.
But then I read through the challenge.
And I understood one important constraint about the rules for any valid path:
never step onto the same tile twice
That removes my barrier for solving this problem with a strategy I commonly use for these puzzle types!
So, I'm feeling more confident that I can earn a gold star today!
I'll take care of a few initial steps before diving into what is likely to be the writing of a recursive function.
Laying the groundwork for every Long Walk
I need a 2D array representing Snow Island:
input.split('\n').map(line => line.split(''))
I need the start and end tiles, which are the same relative tiles in the example input and my puzzle input:
 One tile right of the topleft tile
 One tile left of the bottomright tile
let start = [0,1]
let end = [input.length  1, input[0].length  2]
I need my usual map of orthogonal tiles:
const adjacents = [
[1,0],
[0,1],
[1,0],
[0,1]
]
I need to track which valid path traversed thus far is the longest:
let winner = 0
Coming up next: Recursion!
Starting the Long Walk
I feel like I'll need to pass along each time:
 Current tile coordinates
 Visited path tiles
That may be it.
Also, I realized that I will need a while
loop inside my recursive function.
"To do what?", you ask?
Well, consider the first few steps of the example input:
#.########
#.......##
#######.##
###.....#.
###v#####.
There is only one valid path: thru the dots.
I don't want to recursive down with each dot.
Only when the cursor comes to a junction.
So, inside the recursive function, I need to move as far as I can down the path until I reach a junction.
I'll do that with a while
loop, checking for more than two possible valid next moves.
The base case: end of walk
The end is clear: the current cell is the end cell.
In that case, I want to compare to winner
and update if appropriate.
function walk(coord, path) {
// Reached the end
if (coord.join(',') == end.join(',')) {
winner = Math.max(winner, path.size)
} else {
}
}
Otherwise...proceed as normal.
Here's the next bit of code, getting the item in each adjacent cell:
let next = adjacents.map(xy => {
let [row,col] = [xy[0] + coord[0], xy[1] + coord[1]]
if (row < 0  row >= grid.length  col < 0  col >= grid[0].length) {
return '#'
} else {
return grid[row][col]
}
})
I return forest for any outofbounds cells, since that's what they practically are.
Now I'm not sure what to look for:
 Just one path character? But that doesn't account for slope characters.
 Three tree characters? But that doesn't account for the path I came from.
I think I know now.
Methodchaining filter
I'll do a series of filter
s:
 Is the next cell outofbounds? Get rid of it
 Has the next cell been visited? Get rid of it
 Is the next cell a
forest
? Get rid of it
let next = adjacents.map(
xy => [xy[0] + coord[0], xy[1] + coord[1]]
)
next = next
.filter(xy => {
return (xy[0] < 0  xy[0] >= grid.length  xy[1] < 0  xy[1] >= grid[0].length) ? false : true
}).filter(xy => path.has(xy.join(',')) ? false : true)
.filter(xy => grid[xy[0]][xy[1]] == '#' ? false : true)
After all this filtering, any coordinates remaining are possible next moves.
If there's only one, then I should just proceed.
If there's more than one, I need to split my path and recurse into each possible next move.
Here's the first working version of my while
loop:
let next = [[1,1]]
do {
path.add(next[0].join(','))
coord = next[0]
next = adjacents.map(
xy => [xy[0] + coord[0], xy[1] + coord[1]]
)
next = next.filter(xy => {
return (xy[0] < 0  xy[0] >= grid.length  xy[1] < 0  xy[1] >= grid[0].length) ? false : true
}).filter(xy => path.has(xy.join(',')) ? false : true)
.filter(xy => grid[xy[0]][xy[1]] == '#' ? false : true)
} while (next.length == 1)
I autostep the first step down. Then I use the loop to move as long as there's only one viable option.
Running this on the example input generates the correct initial steps of the path:
#.########
#.......##
#######.##
###.....#.
###v#####.
'0,1',
'1,1',
'1,2',
'1,3',
'1,4',
'1,5',
'1,6',
'1,7',
'2,7',
'3,7',
'3,6',
'3,5',
'3,4',
'3,3',
'4,3',
'5,3'
Next, handling recursion.
False start: debugging time!
Well, my first thought was just a forEach
that called walk
again.
Boy was I wrong!
Lots to fix:
 I had hardcoded
[1,1]
as the next move, so my path kept starting there and immediately ending  Removing that meant I had to run the same
map
andfilter
twice: once before thewhile
loop and then inside  So, I refactored all that into a function and call it twice
 I'm only adding to my path when I enter the
else
clause, so my path isn't even getting updated appropriately  I pass in my path, but I think I need a copy of it to avoid other paths from leeching off of originating paths
Here's what my algorithm looks like now:
function walk(coord, path) {
if (coord.join(',') == end.join(',')) {
winner = Math.max(winner, path.size)
} else {
let next = getNextCells(coord, path)
while (next.length == 1) {
path.add(next[0].join(','))
coord = next[0]
next = getNextCells(coord, path)
}
next.forEach(xy => {
let fork = new Set(path)
fork.add(xy.join(','))
walk(xy, fork)
})
}
}
It doesn't work quite how I want.
In fact, it never updates winner
.
The missing use case: going the wrong direction on slopes
After looking at the logs for details about the path, I think I know why.
Think of this intersection:
##v#
.>.#
##v#
Coming from the v
in the top row.
Current location is the rightmost .
in the middle row.
Right now, my algorithm would explore two paths:

>
and to the left 
v
and below
But >
means a slope that can't be climbed in this case.
Thus, two situations I haven't accounted for:
 Can't move left onto a
>
 Can't move up onto a
v
I checked the example input and my puzzle input, and there are no ^
or <
characters, so no worries about coming to those from the left or above.
...
But first...
Handling when a path deadends
My algorithm finishes.
But I never see output.
I think that's because I don't handle the case where there are no valid next moves.
I'll account for that now:
if (next.length == 0) {
console.log("Path ended wrong")
}
Viola! I see tons of those lines print.
At least I'm seeing it now.
Back on the path: handling invalid slopes
I need some more filters:
 Are there any
slope
characters in my filtered list?  Are any of them rendered invalid based on my current coordinate in the path?
 If so, get rid of them too!
Here's the new method:
.filter(xy => {
if (grid[xy[0]][xy[1]] == '>' && coord[1] > xy[1]) {
return false
} else if (grid[xy[0]][xy[1]] == 'v' && coord[0] > xy[0]) {
return false
} else {
return true
}
})
Fewer logs, but no right ones. Why not?
I now see exactly six statements. That's how many valid paths there are in the example.
Why am I not seeing my winning clause statement?
Ohhhhhh...
My algorithm only checks for the win condition when the recursive function starts.
But the win condition is likely never to activate there.
Because the previous move is always directly above, where the next move is directly below.
So, I need to move my win condition to after the while
loop finishes, and there are no valid next moves.
Here's my code:
if (next.length == 0) {
if (coord.join(',') == end.join(',')) {
winner = Math.max(winner, path.size)
}
}
I see six messages, and they show path lengths!
But they are one higher than the expected lengths.
Oh, that's because the starting point isn't counted in the path length.
I'll just add a  1
.
Fixed code:
if (next.length == 0) {
if (coord.join(',') == end.join(',')) {
winner = Math.max(winner, path.size  1)
}
}
Now I see the right numbers!
Running it on my puzzle input
Will it work?
Will I see an error?
Is there some scenario I didn't account for?
...
I got the correct answer!
Woohoo!!!
Part 2
Easy adjustment
Wow. I just have to remove or comment out my last filter
.
Running it on the example input generates the correct answer instantly!
Running it on my puzzle input takes...
...longer than that.
A lot longer than that.
Several minutes.
Run. Wait. Watch.
I log any time the path finishes at the target end poinit.
I press run.
I see a number immediately.
I take the dogs for a walk.
16 minutes later I check.
Just the one number still.
18 minutes in, hundreds of numbers start flashing!
It's doing it!
Wait. No. It stopped printing new numbers.
22 minutes in, more numbers!
Then it stopped.
This pattern continues.
At 44 minutes in, I feel like I'm being duped.
So I press stop.
I add a logging statement that just prints the longest hike whenever it changes.
I press run.
I let it run in the background.
56 minutes later, my replit.com server terminated.
I submitted the highest answer printed thus far.
Too low.
Bummer.
Throwing in the towel
I don't know how I would optimize my algorithm to run faster or avoid more short hikes.
I initially thought this Part 2 was too easy.
Sure, accounting for its new rules was easy.
But the waiting.
That's tough.
I'm happily taking my one gold star to Day 24.
It's almost Christmas Eve...three months later!
Top comments (0)