The Floor Will Be Lava

Advent of Code 2023 Day 16

Part 1

State management of several cursors

That's what I understand to be at the root of this challenge.

Because, as it is described:

• Laser enters top left: total cursors = 1
• Laser continues or rotates 90 degress: total cursors = 1
• Laser splits in two: total cursors = 2

Hence, the easy parts:

• If a split is detected, increment cursors by 1
• Add the current location to a set of locations that have been visited by a cursor and are therefore energized

And...the hard parts:

• Track the orientation of each cursor
• Iterate through each cursor and determine the location of the next move
• Determine whether the next tile is within the game space
• Determine which part of the next tile is being entered

And more that I'm sure I'm forgetting.

This should be a doozy!

One step at a time, as usual.

Building the initial state

The floor is a 2D array:

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

The unique set of energized floor tiles is...a unique set:

energized = new Set()

The beam starts in the top-left cell:

beams = [ [0,0] ]

The beam faces right, which means it's next move is to the cell one greater in the row and equal in its column.

I'll map out each ordinal move's relative change in coordinates:

directions = {
  'right': [0,1],
  'down' : [1,0],
  'left' : [0,-1],
  'up'   : [-1,0]
}

And update beams:

beams = [
  {
    location: [0,0],
    direction: 'right'
  }
]

Wait a minute. The beam's first move is onto the top-left corner. In the example, that's a .. But in my puzzle input, it's a mirror. I better account for the next move being onto the top-left corner:

beams = [
  {
    location: [0,-1],
    direction: 'right'
  }
]

Now the correct first move will be onto 0,0.

Proceeding...slowly...

For each beam:

• Check the contents of the next floor tile
• Do something based on a series of possibilities

In JavaScript:

beams.forEach((beam, index) => {
  let next = floor[
    beam.location[0] + directions[beam.direction][0]
  ][
    beam.location[1] + directions[beam.direction][1]
  ]
})

That's a lot, but hopefully it makes sense. It does to me...but I wrote it.

First check: is next within the floor space?

If it's not, that means I'm attempting to read from an item in an array that is outside of it's boundary.

In this case, for now I'll update the beam's location to null to indicate that it is no longer a beam I need to track:

  if (next == 'undefined') {
    beams[index].location = null
  }

Otherwise, if not undefined, then the next space is a valid floor tile that I need to read the contents of:

  else {
    switch (next) {
      // all the possible cases
    }
  }

This is gonna get complicated.

Oh, and I need to track that it is now energized:

energized.add(
  [beam.location[0] + directions[beam.direction][0],
   beam.location[1] + directions[beam.direction][1]]
   .join(',')
)

That's messy. I'll clean it up later.

Back to all the cases.

Checking all the possible cases

Those cases are:

switch (next) {
  case '.':
    break;
  case '/':
    break;
  case '\\':
    break;
  case '-':
    break;
  case '|':
    break;
}

Easiest first: .

Just keep moving a.k.a. update location with the coordinates of this new cell:

case '.':
  beams[index].location = coords
  break;

Refactoring to run multiple times

I put all this awesome code inside a forEach function.

I need to call the forEach another time to simulate another move.

And I don't want to copy-paste all that code.

So, I'll put all that code in a function that I call inside the forEach:

beams.forEach((beam, index) => {
  moveBeam(beam, index)
})

Now, if I want to simulate two rounds of beam movement, I just have to call the above code snippet twice.

Eventually, I'll put all of this in a while loop. And a step before that I'll put it in a for loop with an arbitrary end condition. But for now, this works to see the next few moves.

Thankfully, I see the next expected floor tile value after two moves: |.

First splitter: |

Enter, more cases: from which direction is the beam entering?

• left or right? Split!
• up or down? Treat like a .

Here is the case at this point:

case '|':
  switch (beam.direction) {
    case 'right':
    case 'left':
      // Add beam
      // Update both beam locations and directions
      break;
    case 'up':
    case 'down':
      beams[index].location = coords
      break;
  }
  break;

I took a break. Then I came back.

I moved a lot around.

And I changed some.

• I added that for loop I mentioned earlier
• I wrapped my forEach loop in a condition that checks for a beam's location's value of null, meaning it has exited the floor and should no longer move
• I added a check for whether the next cell is on the floor. If it isn't, set it's location to null
• I filled in the case for moving to a | tile horizontally: update the current beam's direction and add a beam going the opposite direction at the same location

After 4 iterations, there are two beams: one is no longer on the floor and the other is facing down...as expected!

Second splitter: '-'

This should be pretty simple now that I did the | splitter.

Yup, pretty simple.

Running 12 rounds results in three beams total: one existed a while ago, one just existed to the left, and one is moving right, about to hit the first mirror.

Nice!

And now for the mirrors: \ and /

They're pretty simple, too. Four cases each. One direction change each.

case '/':
  switch (beam.direction) {
    case 'right':
      beams[index].direction = 'up'
      break;
    case 'down':
      beams[index].direction = 'left'
      break;
    case 'left':
      beams[index].direction = 'down'
      break;
    case 'up':
      beams[index].direction = 'right'
      break;
  }
  break;

By now, my algorithm should account for every possible case.

It should also lead to a state where every beam exits the floor.

Before I incorporate a while loop that checks for that state, I'll run my for loop some more times to confirm the beams are moving as expected.

As expected, I got an error related to an out-of-bounds issue with my algorithm.

Turns out, I forgot to use >= instead of > when checking whether a beam was below or right of the floor.

Now that it's fixed, the for loop is running to completion again.

Discovering a tricky truth

I refactored my for loop into a while loop.

Well, I tried at least.

The condition I used was:

• Continue as long as the list of beams isn't full of beams whose location is null

I figured this was enough to stop the program, figuring that every beam eventually exits the floor.

Well, I may not be wrong about that.

But, I overlooked a deeper issue with the way beams move and split:

• Two beams may traverse the same course, having split at the same spot

In the example input:

.|...\....
|.-.\.....
.....|-...
........|.
..........
.........\
..../.\\..
.-.-/..|..
.|....-|.\
..//.|....

When the starting beam hits the - splitter marked by the *:

.|...\....
|.-.\.....
.....|-...
........|.
..........
.........\
..../.\\..
.-.-/..|..
.|....*|.\
..//.|....

It infinitely traverses the path marked by S=+s:

.|...\....
|.-.\.....
.....|-...
........|.
..........
.........\
....+=+\..
.+==+.+|..
.+====S|.\
..//.|....

In my algorithm, that causes the endless generation of beams.

Eventually, my algorithm has hundreds of thousands of beams, many of which have exited the floor.

But it means that I can't trust all beams eventually reaching a null location.

Can I just watch the count of energized cells until it doesn't change?

Yes, for the example input.

No, for my puzzle input.

The number of energized cells creeps slowly toward 7.5k, then crawls 2-3 notches up every few seconds while the number of beams to check likely passes the millions quickly.

In short, I'm not gonna solve the puzzle the way things are.

I may have to save a beam's generation point, and only add new beams if their starting point is different.

That will be my next strategy.

Programming my new strategy

I need another unique set - this time, of starting coordinates and orientations:

let starters = new Set()

In each beam's case, instead of always adding a beam, I check if it's starting coordinate and orientation are a repeat, and only make it if it's a new permutation:

if (!starters.has(coords.join(',') + ',right')) {
  starters.add(coords.join(',') + ',right')
  beams.push({
    location: coords,
    direction: 'right',
    start: coords
  })
}

My while loop is still set up to run forever.

Now I display the counts of energized floor tiles, beams, and starting configurations.

Running again in hopes of faster results

The example input still shows the expected number of energized cells, thankfully.

It also shows single-digit beams and starters. Yay!

My puzzle input quickly gets to over 7.5k energized floor tiles, and stays on a maximum number, finally.

Turns out, that's the correct answer!

Woohoo!!!!

Part 2

And...back to Part 1

Part 2 will require to run my Part 1 algorithm hundreds of times.

Unfortunately, my Part 1 algorithm never ends. I just watch it for a changing value too eventually stop changing.

So, if I want to solve Part 2 in a manner other than manually running it on hundreds of starting coordinates, I need to find a way to make my Part 1 algorithm trigger an end-state for the while loop.

After sleeping on it, I have a brilliant idea.

Splitters always kill the entering beam and optionally spawn two new beams

When a beam first encounters a splitter, I'll update it's location value to null. In its place I'll add two new beams - going in opposite directions.

Then, when any beam encounters that same splitter, that beam will effectively die due to its null location, and no new beams will get created (thanks to the update I made at the end of Part 1 to cut down on the amount of looping beams).

If I can get all this to work, then eventually my factory of beams will stop generating new beams and the beams that exist will all have null as their location values.

And then my condition for checking whether all beams have null as their location will pass, and the while loop will terminate!

I sure hope this works.

Minus one beam, plus two (the first time)

Here's my working JavaScript:

case 'up':
case 'down':
  beams[index].location = null
  if (!starters.has(coords.join(',') + ',left')) {
    starters.add(coords.join(',') + ',left')
    beams.push({
      location: coords,
      direction: 'left'
    })
  }
  if (!starters.has(coords.join(',') + ',right')) {
    starters.add(coords.join(',') + ',right')
    beams.push({
      location: coords,
      direction: 'right'
    })
  }

I did the same for the other splitter.

The while condition

while (
  beams.filter(beam => beam.location !== null).length !== 0
) {
  /// iterate through the beams
}

Essentially:

Continue as long as
The beams array
Contains beams
Whose location values
are not all null

Running on both inputs

Hoping for:

• No errors
• Output that eventually stops...outputting

And...?

It worked!

On both!

It's super quick, now, too!

And it still generates the correct answer!

Woohoo!!

Programmatically generating all starting coordinates and directions

And now back to Part 2.

I need a list of coordinates.

These represent the non-corner edges just beyond the floor.

Visually-speaking, the tiles represented by an * for a floor represented by .s:

 ***
*...*
*...*
*...*
 ***

Maybe I should start smaller to get my model right:

 **
*..*
*..*
 **

The coordinates sorted ascending by row are:

-1, 0
-1, 1
 0,-1
 0, 2
 1,-1
 1, 2
 2, 0
 2, 1

And the directions are:

-1, 0 down
-1, 1 down
 0,-1 right
 0, 2 left
 1,-1 right
 1, 2 left
 2, 0 up
 2, 1 up

If I rearrange to group by direction:

-1, 0 down
-1, 1 down
 0,-1 right
 1,-1 right
 0, 2 left
 1, 2 left
 2, 0 up
 2, 1 up

If I rearrange to group by column:

 0,-1 right
 1,-1 right
-1, 0 down
 2, 0 up
-1, 1 down
 2, 1 up
 0, 2 left
 1, 2 left

Hmm. I'm not yet seeing how I would generate these with nested for loops.

Here's what I want to do:

For rows -1 to length
  For just row -1
    For all columns
      Set direction to down
  For just row length
    For all columns
      Set direction to up
  For all other rows
    For columns -1
      Set direction to right
    For columns length
      Set direction to left

Wow. Writing it out showed me exactly what to do.

Hooray for pseudocode!

Here's that algorithm in JavaScript:

for (let r = -1; r <= floor.length; r++) {
  if (r == -1) {
    for (let c = 0; c < floor[0].length; c++) {
      part2( [r, c] , 'down')
    }
  } else if (r == floor.length) {
    for (let c = 0; c < floor[0].length; c++) {
      part2( [r, c] , 'up')
    }
  } else {
    part2( [r, -1], 'right')
    part2( [r, floor[0].length], 'left')
  }
}

And here's my part2 function:

function part2(coords, dir) {
  beams = [
    {
      location: coords,
      direction: dir
    }
  ]
  energized = new Set()
  starters = new Set()
  while (beams.filter(beam => beam.location !== null).length !== 0) {
    beams.forEach((beam, index) => {
      if (beam.location !== null) {
        moveBeam(beam, index)
      }
    })
  }
  max = energized.size <= max ? max : energized.size
}

Running with fingers crossed

It generates the expected answer for the example input!

And after 5 seconds of running, it generates the correct answer for my puzzle input!

Yeeeehaawwwww!!!

What a rewarding feeling!

That was a super-fun challenge.

Lots of work, but tons of a-ha moments and plenty of proud moments as I worked my way through it.

Things only get harder from here...am i right?!