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.

I lied: one last hail mary

I realized there was one more short-circuit technique that I hadn't used:

• Exit from recursion any time the score has surpassed the current lowest score

I added that new condition to my function:

if (score > smallestScore) { return false }

And pressed Run once more.

Watching the console

I saw the usual two results.

Then I saw new ones within a few seconds!

Oh my gosh! This may actually work!

More lower scores continue to appear.

Minutes go by.

A few more lower scores.

I let the program run, checking on it periodically.

295136 1136
292132 1132
292124 1124
255000 1000
251996 996
250992 992
247988 988
245984 984
243964 964
241960 960
239960 960
239956 956
238952 952
235948 948
235944 944
235920 920
233900 900
231896 896
229896 896
229892 892
228888 888
225884 884
223868 868
223864 864
221864 864
221860 860
220856 856
217852 852
215836 836
215832 832
215828 828
214824 824
211820 820
209792 792
208788 788
205784 784
203780 780
201772 772
200768 768
197764 764
192744 744
189740 740
188736 736
185732 732
185724 724
183720 720
182700 700
179696 696
178692 692
175688 688
175680 680
173676 676
173668 668
171664 664
171660 660
169656 656
169656 656
168652 652
165648 648
163644 644
161620 620
159616 616
157616 616
157612 612
155612 612
155612 612
153608 608
151584 584
149580 580
147580 580
147568 568
145564 564
143564 564
143564 564
143560 560
141596 596
139592 592
139588 588
137584 584
135588 588
133584 584
131580 580
131576 576
129572 572
127572 572
127568 568
125564 564
125564 564
123560 560
123560 560
121556 556
121556 556
121556 556
119552 552
119540 540
119540 540
117540 540
117532 532
117532 532
115532 532
113532 532
113528 528
111528 528
111516 516
111516 516
109516 516

After nearly 45 minutes, it actually finishes.

The lowest logged score is close to 1/3 of the first score logged.

Wow!

Is this my correct answer?

Time to submit...

It is!!!!

Holy smokes!!!!

I did it!!!!

And now, I get to see Part 2.

Part 2

Wow, this now seems doable!

I now know the score of the best path for my puzzle input.

And as part of debugging, my algorithm already builds the path comprised of each coordinate visited.

So, my reasoning is:

• If I add a condition to check for that exact lowest score
• And only add the unique set of points visited on that path to a global set of unique points
• Then by the end of it running again, I should know how many tiles there are along any best path

Time to add a bit of code...and wait another 45 minutes!

Back to never finishing

I adjusted my algorithm to track all tiles visited on the best score path.

I debugged it until I used the correct syntax for iterating the values of a Set.

I tested it on both examples, and got the correct answers.

I had to remove my condition that prevented further recursion when a coordinate had been visited with a lower score. That's because I felt it was mistakenly preventing some paths from completing that would have eventually become the best score.

I pressed 'Run' on my puzzle input.

Then I waited.

And waited.

...

I returned to my computer several times throughout a several-hour period.

Still running.

At least it hasn't timed out. Probably because of my max-score condition.

But at this point, it may be hours before it finishes.

I'm convinced that if it finishes it will display the correct answer.

I guess I can leave it going, and update this article if it ever finishes.

It never finished.

Bummer.

At least I found a way to earn one gold star!