Reindeer Maze

Advent of Code 2024 Day 16

Part 1

A 'shortest path' that feels doable

I think I can use recursion to explore every possible path from S to E.

That's because I've done it before.

The fun challenge here will be accounting for rotation.

I'm confident I can stumble upon the correct answer to Part 1.

Time to step through the process, as usual.

Setting my stage

Just like any other grid challenge, I have to parse the input into a 2D array:

input = input.split('\n').map(line => line.split(''))

I want to store the coordinates of the start and end positions.

Luckily, it seems like in the example and my input, the start is one diagonal from the bottom left and the end is one diagonal from the top right.

So, instead of iterating through each cell and looking for the S or E, I can calculate their positions through array lengths:

let S = [input.length - 2, 1]
let E = [1, input[0].length - 2]

I can only be facing one of four directions.

First, I face East.

I'll store each direction in an ordered list as 2-item arrays, where each item is the amount to move along each axis - positive is down/right, negative is up/left:

let directions = [
  [0,1],
  [1,0],
  [0,-1],
  [-1,0]
]

And I need to track the score from each successful maze traversal.

It should start as high as possible and get smaller:

let smallestScore = Infinity

Going deep into recursion

Now for the fun part; the true test.

First, the function definition with no parameters:

function mazeMover() {

}

Next, the parameters:

1. The current location of the robot
2. The current score
3. A unique set of visited locations

function mazeMover(loc, score, visited) {

}

Next, the base case(s):

1. Either the robot hits a wall
2. Or it moves to the E
3. Or it moves to a previously visited location

In the cases of 1 and 3, the program should end.

In the case of 2, the program should compare an accumulated score to the global score variable and keep the smaller one.

function mazeMover(loc, score, visited) {
  if (loc.join('.') == E.join('.')) {
    smallestScore = Math.min(smallestScore, score)
    return false
  } else if (visited.has(loc.join('.'))) {
    return false
  } else if (input[loc[0]][loc[1]] == "#") {
    return false
  }
}

The initial function invocation:

• loc is S
• score is 0
• visited is a new Set containing S

mazeMover(S, 0, new Set(S.join('.')))

I wouldn't expect any of the base cases to catch:

• S is not E
• Uh oh, visited has S
• S is not a wall

Ok, my Set should be empty to start.

Then when should I add my current location to the Set?

Maybe just before recursing?

My updated initial function invocation:

mazeMover(S, 0, new Set())

Handling the non-base-case(s):

• Try moving in each of the four available directions
• Add the current location to the Set of visited locations
• Update the score to reflect rotation and movement

Revisiting my rotation understanding

I have an ordered list of directions in clockwise order.

I originally planned to add 1000 to the score each time the robot rotated.

But there's a problem:

• One rotation should add 1000
• Two rotations should add 2000 - since the robot now faces the other way
• But three rotations should only add 1000, not 3000 - since the robot could have turned the other direction one time

So, how should I account for the last direction adding 1000 instead of 3000?

Maybe three manual recursive function calls? It's not as clean as I want, but that isn't my goal. My goal is to get the correct answer.

I think I'm ready to try writing my non-base case now.

Writing the non-base case: rotate, move, recurse

I haven't tested this, but here's my first draft:

visited.add(S.join('.'))
directions.forEach((dir, i) => {
    if (i % 2 == 1) {
        mazeMover([S[0] + dir[0], S[1] + dir[1]], score + 1001, visited)
    } else if (i == 0) {
        mazeMover([S[0] + dir[0], S[1] + dir[1]], score + 1, visited)
    } else if (i % 2 == 0) {
        mazeMover([S[0] + dir[0], S[1] + dir[1]], score + 2001, visited)
    }
})

What I expect it to do:

Add the current cell location to the list of visited locations
Iterate through each of the four directions
For each direction
  If the index is odd
    It means one rotation and a score increase of 1000, plus 1 for the move in that direction
    Also, adjust the coordinates for the new location
    And carry forward the list of visited locations
  If the index is 0
    It means no rotations: add one to score, do the rest the same
  If the index is even
    It means two rotations: add 2000 to the score, plus 1 for the move in that direction, do the rest the same

At least that's what I expect.

Time to run it and see how it actually works.

Running and debugging

Maximum call stack exceeded.

Uh oh. Why?

A few console.log() statements later:

• I only saw one coordinate being visited: S
• I mistakenly referenced S instead of the local variable loc

After replacing S with loc, I saw the log statements I was expecting - for each of the conditions.

I now see the scores my algorithm generates.

They are much bigger than expected.

Hmm.

Oh, I think it is because I don't adjust my ordered list of directions to account for the direction the robot is facing.

And I think I have to account for that in each of my conditions before each recursive function call.

Accounting for a reordering of directions

I got overly cautious and made sure to clone my directions array any time I intended to transform it.

First, I adjusted my recursive function's signature, adding a parameter to account for the current order of directions:

function mazeMover(loc, facing, score, visited) {

}

My initial function invocation now looks like this:

mazeMover(S.slice(), directions.map(i => i.slice()), 0, new Set())

And my non-base case looks like this:

facing.forEach((dir, i) => {
    newFacing = facing.map(i => i.slice())
    if (i % 2 == 1) {
        for (let x = 0; x < i; x++) {
            newFacing.push(newFacing.shift())
        }
        mazeMover([loc[0] + dir[0], loc[1] + dir[1]], newFacing, score + 1001, visited)
    } else if (i == 0) {
        mazeMover([loc[0] + dir[0], loc[1] + dir[1]], newFacing, score + 1, visited)
    } else if (i % 2 == 0) {
        for (let x = 0; x < i; x++) {
            newFacing.push(newFacing.shift())
        }
        mazeMover([loc[0] + dir[0], loc[1] + dir[1]], newFacing, score + 2001, visited)
    }
})

The important new sections looks like this:

for (let x = 0; x < i; x++) {
  newFacing.push(newFacing.shift())
}

Count as many times equal to i, each time shifting the first item to the end of the list.

Running the algorithm again generates a smaller answer, but still not as small as expected.

I wonder what is still not working as well as I want.

More debugging by logging all the things

I want to understand what's happening in each winning path.

I already track the score and the visited coordinates.

I can log them and see what the result looks like.

...

I saw them. There were too many.

That made me think that my Set of visited coordinates isn't working at each local level.

Rather, that each recursive call is referencing a global Set.

That's not good.

The way to change that is to make a new Set in each recursive call.

I updated my call signature's last argument to look like this:

new Set([...visited])

Running again and hoping for accuracy

I ran my algorithm again on the first example input.

It finally generated the correct answer!

Woohoo!!

Will it do the same for the second example input?

Yes! Awesome!!!

Lastly, will it generate the correct answer for my puzzle input?

...

I'm not sure.

It generated two scores right away. Three are the same.

Then it kept running.

And running.

For tens of minutes.

I stopped it.

Then I logged how many times the winning scores recursed.

A little over a thousand times. That's how many cells were traversed by the robot.

My hunch is that the correct answer is lower than the scores I saw.

But I don't know how to see them faster.

Maybe if I track the smallest score accrued at each cell, I can terminate far more recursions early, and see more answers sooner.

Worth a try!

Attempting to short-circuit certain paths

A new dictionary for cells:

let cells = {}

A condition checking for an previous score:

if ((loc.join('.') in cells)) {
    if (cells[loc.join('.')] > score) {
        return false
    }
}

And a storing of the score just after the cell is marked as visited:

visited.add(loc.join('.'))
cells[loc.join('.')] = score

Surprise, but no luck

My algorithm ends in seconds!

But it still generated the same lowest score.

I'm convinced it's not the right answer.

But I have to try submitting it.

...

Nope. Too high.

Bummer!

Rethinking again, still no luck

I studied the first two examples again.

I thought about how two paths would cross the same point, but one with a higher score than the other.

I felt like I understood it well enough to try again.

I put my code back.

I added some logging statements to confirm it worked as expected.

It was!

Example 1: check

Example 2: check

My puzzle input: unfinished, again!

Darn it!

It may be speeding things up, but not enough to fully process the giant maze that is my puzzle input.

I'm really bummed I couldn't get my algorithm to finish running on my puzzle input.

When this all began, I felt confident I would at least get one gold star.

Oh well. I exhausted my toolbelt of CS skills.

Time to move on to Day 17 after dragging my feet no attempting today's puzzle.