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
orright
? Split! -
up
ordown
? 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 ofnull
, 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?!
Top comments (0)