A Long Walk

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 top-left tile
• One tile left of the bottom-right 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 out-of-bounds 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.

Method-chaining filter

I'll do a series of filters:

1. Is the next cell out-of-bounds? Get rid of it
2. Has the next cell been visited? Get rid of it
3. 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 auto-step 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 hard-coded [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 and filter twice: once before the while 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 right-most . 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:

1. Can't move left onto a >
2. 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 dead-ends

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!