Restroom Redoubt

Advent of Code 2024 Day 14

Part 1

Tracking wrapping movement

There's lots to do here.

And I'm confident I can get it done to earn at least one gold star.

My tasks seemingly include:

• Parse the input for all integers
• Generate the list of robots
• Create the grid
• With the help of modulo, process 100 iterations of movement
• Determine the boundaries of each quadrant
• Review each robot and calculate four sums, one for each quadrant
• Tally the sums

As I would through my algorithm, all of the above is subject to change.

Time to rock n' roll!

One step at a time

Using regex to parse input into robots list

From a line like this:

p=9,5 v=-3,-3

I want to get all four integers, including the negative signs.

I'll use this regular expression:

/-?\d+/g

And a bit of data structure manipulation to get just those values:

let [px, py, vx, vy] = [...robot.matchAll(/-?\d+/g)].map(el => +el[0])

Worked like a charm!

Setting up the grid

As stated, the small example grid is 11x7, while the actual grid is 103x101.

let width = 11
let height = 7
let grid =  new Array(height).fill('.')
 .map(el => new Array(width).fill('.'))

There is no need for the grid, though, honestly.

At the end, I can just check which range of numbers each robot resides in to determine that quadrant's sum.

Still, it's good to know that I can use a grid if I want.

Simple and straightforward.

Handling robot movement and teleportation

Positive X values mean move right (higher index). Negative: left.

Positive Y values mean move down (higher index). Negative: up.

Any time the robot would otherwise go out of bounds, instead have them act like they moved onto a duplicate of the grid in the same direction.

That calculation is made easy thanks to the modulo operator, which gives me a remainder.

Well, that makes moving down and right out of bounds easy.

Moving up and left out of bounds will require subtracting from the width and height of the grid.

Time to codify all this logic!

First, the bones of the loop:

for (let i = 0; i < 100; i++) {
    robots = robots.map(bot => {
        let [px, py, vx, vy] = bot
        if (vx < 0) {

        } else {

        }
        if (vy < 0) {

        } else {

        }
    })
}

Next, handling each condition:

for (let i = 0; i < 100; i++) {
    robots = robots.map(bot => {
        let [px, py, vx, vy] = bot
        if (vx < 0) {
            px += vx
            if (px < 0) {
                px = width - 1 + px
            }
        } else {
            px = (px + vx) % (width - 1)
        }
        if (vy < 0) {
            py += vy
            if (py < 0) {
                py = height - 1 + py
            }
        } else {
            py = (py + vx) % (height - 1)
        }
    })
}

I wrote that without testing it.

Let's see how much I have to debug.

Well, first issue:

• Make sure map returns something!

What a silly mistake.

Next issue:

• In the last else clause, I mistakenly reference vx instead of vy

Another silly mistake!

Thankfully, those appear to be my only errors.

I'm seeing the expected grid amounts now, using this code:

robots.forEach(bot => {
    let [px, py] = bot
    if (grid[py][px] == 1) {
        grid[py][px] = 2
    } else {
        grid[py][px] = 1
    }
})
console.log(grid.map(line => line.join('')).join('\n'))

Tallying up each quadrant

The example grid is 11x7.

Quadrants range from:

0,0 to 0,4
2,0 to 2,4

0,6 to 0,10
2,6 to 2,10

4,0 to 4,4
6,0 to 6,4

4,6 to 4,10
6,6 to 6,10

The numbers are all even.

The numbers are equal to one of:

• Side length divided by two: rounded down & subtract one, or rounded up
• Side length minus one

I could solve this with a very complex series of conditional clauses.

And that I shall:

let quads = [0,0,0,0]
robots.forEach(([px, py]) => {
    if (px <= (Math.floor(width / 2) - 1)) {
        // Left half
        if (py <= (Math.floor(height / 2) - 1)) {
            // Top quadrant
            quads[0]++
        } else if (py >= Math.ceil(height / 2)) {
            // Bottom quadrant
            quads[1]++
        }
    } else if (px >= (Math.ceil(width / 2))) {
        // Right half
        if (py <= (Math.floor(height / 2) - 1)) {
            // Top quadrant
            quads[2]++
        } else if (py >= Math.ceil(height / 2)) {
            // Bottom quadrant
            quads[3]++
        }
    }
})

Finally, the product of each tally:

quads.reduce((a, c) => a * c)

Running and hoping

Does it generate 12 for the example input?

Yes!

Does it generate an answer for my puzzle input?

Yes! It's real high, though.

Let me check each quadrant's value.

Each one is a little over a hundred.

There are 500 robots.

And I'm sure several fell on a horizontal or vertical midpoint.

This number could be right.

Submitting...

It was right!!!

Woohoo!!!

I feel like this will be a checkpoint-style challenge, where Part 2 is the real puzzle.

Can't wait to see.

Part 2

Oh cool, I get to simulate the robots!

Supposedly they form a Christmas tree at some point.

Could be a couple seconds.

Could be hundreds.

Time to build my first simulator of 2024!

Building a simulator

This was pretty easy.

I used Codepen.io.

The grid is very small to fit on a widescreen.

But it works:

Enhancing the simulator

• Pressing the button performs an iteration
• I pressed it a bunch and saw two recurring patterns
• I wondered how many iterations it took for the robots to start again at their initial state
• I used Set() to track each state
• I used setInterval() to auto-iterate at fast pace
• I added a list to display repeat states
• I pressed the button and watched the count climb well into the thousands
• Just after 10k the robots returned to their starting state
• To confirm this, I reversed the polarity of each robot's velocities
• I pressed the button again, watched it climb into the thousands, and saw the same iteration number when the robots started a new loop

I now know that the robots in my puzzle input loop every 10403 iterations.

To cheat, or to strain my eyes

I really don't want to manually step through all 10403 iterations looking for a Christmas tree.

I know that I can submit 4 answers and get a hint about whether my submission is too high or low.

I'm tempted to do four binary searches:

• Submit 5000 and check high or low
• Submit 2500 or 7500 and check high or low
• Submit 1200 or 3700 or 6300 or 8800 and check high or low
• Submit once more and check

Then, I will only have to check several hundred states, not 10000.

And, if it is closer to 10403 than 0, I can account for going backwards by making my count start there and count down.

I'm gonna go for it:

• Submitted 5201: Too low
• Submitted 7803: Too high
• Submitted 6502: Too low

The correct answer is between 6502 and 7803.

That's 1300 states to inspect with my poor eyes.

Better than over 10k, right??!

I saw it!

• I added some buttons to progress fast and then slow
• I sped past 6500 iterations
• Then I watched carefully for the next several hundred
• I tried to blink with one eye so I wouldn't miss the tree
• Then, suddenly, it appeared!
• I paused the timer and saw 7612
• It must have been a few steps prior
• Time to restart and walk manually again starting at, like, 7500

I saw it again!

I had to double back a few times:

• Once because I incorrectly hooked up my new button
• And again because I overshot the sped up iterator

But, eventually, I stopped on the state with the picture:

I've never been happier to see an ASCII Christmas tree.

And my counter was correct - that number was my correct answer.

I have no idea how I would have solved this algorithmically.

But it was really fun solving this way.

Even if I had to leverage wrong submissions to perform a sort of binary search to find the answer.

It's all part of the run, right??!

I'm proudly taking my two gold stars to Day 15.