Advent of Code 2023 Day 10
Part 1
The trick to calculating the distance to the furthest point
Loop length / 2
It's that simple, really!
Example 1's loop is 8 segments long:
8 / 2 = 4
Example 2's loop is 16 segments long:
16 / 2 = 8
What if the loop is an odd number of segments long?
It can't be!
Smallest loop:
F7
LJ
Another loop:
F-7
|-J
LJ
There's no way to make the loop an odd-segment length.
So the formula holds: Loop length / 2
Codifying each segment type based on its connecting sides
| is a vertical pipe connecting north and south.
Once at this segment type, I know the loop continues only if:
- The segment above is one of
|,F,7 - The segment below is one of
|,L,J
- is a horizontal pipe connecting east and west.
Once at this segment type, I know the loop continues only if:
- The segment to the left is one of
-,F,L - The segment to the right is one of
-,J,7
L is a 90-degree bend connecting north and east.
Once at this segment type, I know the loop continues only if:
- The segment above is one of
|,F,7 - The segment to the right is one of
-,J,7
J is a 90-degree bend connecting north and west.
Once at this segment type, I know the loop continues only if:
- The segment to the left is one of
-,F,L - The segment above is one of
|,F,7
7 is a 90-degree bend connecting south and west.
Once at this segment type, I know the loop continues only if:
- The segment to the left is one of
-,F,L - The segment below is one of
|,J,L
F is a 90-degree bend connecting south and east.
Once at this segment type, I know the loop continues only if:
- The segment to the right is one of
-,J,7 - The segment below is one of
|,J,L
Hmmm. This got complicated much more quickly than I had hoped.
On second thought, it may be much easier.
Especially since I will always know which direction the segment is entered from.
Figuring out what the starting segment is
Here's the first example loop:
-L|F7
7S-7|
L|7||
-L-J|
L|-JF
Focusing on the starting point:
L
7S-
|
Adjacent digits going clockwise:
Above: L
Right: -
Below: |
Left: 7
Incompatible moves:
Above: L - because it can't be entered from below
Left: 7 - because it can't be entered from right
Compatible moves:
Right: -
Below: |
Segment type that can move Right and Down:
F
Manually walking a few steps of the loop
I'll make the first clockwise compatible move: -
At this point, my algorithm should know:
- The starting coordinate
- The coordinate of the point being moved to
- The segment type of the point being moved to
- That both segments are on the loop
With all this state being understood and stored, there's only one possible next move:
Right
The next segment is a 7.
Since a 7 can only go left or down, and it is being entered from the left, there's only one possible next move:
Down
So, it seems I just need to make a legend for each segment that captures the two possible moves. From there, I can eliminate the move that would result in going backwards. What I'll be left with is the only next possible move.
And I can do this until the next move results in returning to the starting position.
Relative coordinates for each segment type's connectors
The four relative coordinates are:
[-1,0]
[0,-1]
[0,1]
[1,0]
F
Connecting segments are indicated by asterisks (*):
...
.F*
.*.
Relative coordinates are:
[0,1]
[1,0]
J
Connecting segments are indicated by asterisks (*):
...
..*
.*J
Relative coordinates are:
[-1,0]
[0,-1]
L
Connecting segments are indicated by asterisks (*):
...
.*.
.L*
Relative coordinates are:
[-1,0]
[0,1]
7
Connecting segments are indicated by asterisks (*):
...
.*7
..*
Relative coordinates are:
[0,-1]
[1,0]
-
Connecting segments are indicated by asterisks (*):
...
*-*
...
Relative coordinates are:
[0,-1]
[0,1]
|
Connecting segments are indicated by asterisks (*):
.*.
.|.
.*.
Relative coordinates are:
[-1,0]
[1,0]
Altogether now
{
F: ['0,1','1,0'],
J: ['-1,0','0,-1'],
L: ['-1,0','0,1'],
7: ['0,-1','1,0'],
-: ['0,-1','0,1'],
|: ['-1,0','1,0']
}
Making the coordinate pairs a string will make things easier to compare for equality.
Writing an algorithm
First, I want to find the start position of the animal:
const input = textFile.split('\n')
let row = input.findIndex(line => line.includes('S'))
let col = input[startRow].indexOf('S')
Next, some seemingly necessary setup that I'll do manually since I'd rather not figure it out programmatically:
const adjacents = {
'F': ['0,1','1,0'],
'J': ['-1,0','0,-1'],
'L': ['-1,0','0,1'],
'7': ['0,-1','1,0'],
'-': ['0,-1','0,1'],
'|': ['-1,0','1,0']
}
let start = [row, col]
let loopLength = 1
let prevSegment = 'F'
let prevMove = '1,0'
Then, queuing up the first next move:
let nextMove = adjacents[prevSegment][1 - adjacents[prevSegment].indexOf(prevMove)]
let [r,c] = nextMove.split(',').map(Number)
let nextCoords = [row + r, col + c]
let nextSegment = input[nextCoords[0]][nextCoords[1]]
Here's some code that will accompany the above snippet in a while loop:
loopLength++
prevSegment = nextSegment
prevMove = nextMove
Speaking of that while loop, I think it should go until the nextCoords are the same as start:
while (nextCoords.join('') !== start.join('')) {
}
Enter: three hours of struggle
My issue:
- Determining the correct next adjacent coordinate to move to
Using the first example:
.....
.S-7.
.|.|.
.L-J.
.....
My next move after S is right, so 0,1, to -.
Referring to my legend:
'-': ['0,-1','0,1']
Those are the directions to go from a - segment.
But how do I know which direction the loop came from to get to the -?
Long story short
I needed another legend that mapped exist directions to entrance directions:
const reversals = {
'0,1': '0,-1',
'0,-1': '0,1',
'-1,0': '1,0',
'1,0': '-1,0'
}
And I needed to use it in combination with my existing calculation of using the other of two coordinates for the correct current segment type.
Using the example again:
- From
S, enter-going0,1 - Reverse
0,1to0,-1 - Use the other coordinate in
-:0,1as the next relative coordinate
This took me a while to diagnose and correct for.
But I did it.
Redundant code inside and outside of a while loop
The while loop checks whether the segment type at the next location is an S in the original input.
I initialize the next segment before the loop and update it inside the loop.
The code is redundant.
There's certainly a smarter way.
But it works.
So I'm sticking with it for the remainder of this challenge.
Off by 1 on loop length
This was an easy fix:
- Set it initially to 0 instead of 1
Re-running and finally celebrating
-
4using the first example! -
8using the second example! - And the correct answer (~7k) using my puzzle input!
That was a hard-earned star that I'm glad I successfully troubleshot and persisted.
Part 2
Well...shoot
I have no idea how I would calculate this programatically.
I do know how I would do it visually.
But that's not really the point, is it?
Still, it could be fun to render just the loop!
Rendering the loop
First, I need to create an empty grid of the same size as the input:
let grid = new Array(input.length).fill(null).map(el => new Array(input[0].length).fill(null).map(el => '.'))
Next, at several spots in my loop generator, I add the current location of the segment on the loop to a list of coordinates.
Then, I fill in the grid with each segment on the loop using an asterisk:
path.forEach(([row,col]) => {
grid[row][col] = "*"
})
Lastly, I render the loop:
console.log(grid.map(line => line.join('')).join('\n'))
And I see this donut-looking beast:
It looks like there is that central hole...
...and tons of 1- and 2-dot holes freckling the rest of the loop.
I really am not sure how to programmatically determine whether any of those holes is inside or outside of the loop.
And doing it manually would probably just require changing my asterisks to the symbols used in the challenge, and carefully inspecting near each hole.
I'm not sure if it's worth it.
Maybe some day when I have a lot of time to spend comparing dots.
But for now, time to move on with one beautiful new star.
Top comments (0)