The Floor Will Be Lava
Tags: adventofcode, algorithms, javascript, programming
Published: 2024-02-17 16:28:47

## [Advent of Code 2023 Day 16](https://adventofcode.com/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:
```js
floor = input.split('\n').map(line => line.split(''))
```

The unique set of energized floor tiles is...a unique set:
```js
energized = new Set()
```

The beam starts in the top-left cell:
```js
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:
```js
directions = {
  'right': [0,1],
  'down' : [1,0],
  'left' : [0,-1],
  'up'   : [-1,0]
}
```

And update `beams`:
```js
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:
```js
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:
```js
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:
```js
  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:
```js
  else {
    switch (next) {
      // all the possible cases
    }
  }
```

This is gonna get complicated.

Oh, and I need to track that it is now energized:
```js
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:
```js
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:
```js
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`:
```js
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:
```js
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.

```js
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:
```js
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:
```js
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:
```js
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
```js
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:
```js
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:
```js
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?!