As I understand it:
Here's a visual:
........... ........... ...X....... ........... .....Y..... <---1N from top X, 2N from bottom X ........... .......Y... <---2N from top X, 1N from bottom X ........... .........X. ...........
It's clear visually.
How could I determine it algorithmically?
Here's the example grid:
............ ........0... .....0...... .......0.... ....0....... ......A..... ............ ............ ........A... .........A.. ............ ............
I'll focus on the 0s:
Comparing the first two:
1,8 vs. 2,5 1 row apart 3 col apart 2 possible antinodes: 0,11: 0 = min(1,2) - 1 3,2 For 0,11 0 = min(1,2) - 1 11 = ....
I realized while writing that I really need to know the slope of the line connecting the pair of points.
That way I can know whether to add or subtract from each axis to determine where the antinode is.
The formula is:
(y2 - y1) / (x2 - x1)
The outcome will be one of these four:
Returning to the example:
1,8 and 2,5 (5 - 8) / (2 - 1) = -3 / 1 = -3
What? A negative slope? No, that line has positive slope!
Oh...I see.
Array indexing counts up, but visually is moving down.
I need to count indices in reverse.
Instead of like this:
0 ............ 1 ........0... 2 .....0...... 3 .......0.... 4 ....0....... 5 ......A..... 6 ............ 7 ............ 8 ........A... 9 .........A.. ............ ............ 0123456789
I need to count like this:
............ ........0... 9 .....0...... 8 .......0.... 7 ....0....... 6 ......A..... 5 ............ 4 ............ 3 ........A... 2 .........A.. 1 ............ 0 ............ 0123456789
It should just require a bit more math:
array length - current row/col index
I'll try.
For the top-most 0:
12 rows Row index: 1 12 - 1 = 11 Column index: 8 Coordinates: 8,11
For the 0 in the next row:
Row index: 2 12 - 2 = 10 Column index: 5 Coordinates: 5,10
And the slope:
(10 - 11) / (5 - 8)
-1 / -3
1/3
A positive slope! That's correct!
An empty object filled with a nested for loop:
let graph = input.split('\n').map(el => el.split(''))
let antennas = {}
for (let y = 0; y < graph.length; y++) {
for (let x = 0; x < graph[0].length; x++) {
if (graph[y][x] !== '.') {
if (!(graph[y][x] in antennas)) {
antennas[graph[y][x]] = []
}
antennas[graph[y][x]].push([graph.length - y,x])
}
}
}
<p>Creates this object for the example input:<br>
</p>
<pre class="brush:php;toolbar:false">{
'0': [ [ 11, 8 ], [ 10, 5 ], [ 9, 7 ], [ 8, 4 ] ],
A: [ [ 7, 6 ], [ 4, 8 ], [ 3, 9 ] ]
}
Looks great!
Next, calculating slope.
My scope function is simple:
function getScope(p1,p2) {
return (p2[0] - p1[0]) / (p2[1] - p1[1])
}
It expects two arrays and returns the scope using all four coordinates.
I'll want to call this function when comparing all pairs of similar-frequency coordinates.
That comparison happens in this super-nested for loop:
for (let freq in antennas) {
let f = antennas[freq]
for (let i = 0; i < f.length; i++) {
for (let j = i + 1; j < f.length; j++) {
// Comparing two antennas of the same frequency
}
}
}
Confirming it works on the example input:
[ 11, 8 ] [ 10, 5 ] [ 11, 8 ] [ 9, 7 ] [ 11, 8 ] [ 8, 4 ] [ 10, 5 ] [ 9, 7 ] [ 10, 5 ] [ 8, 4 ] [ 9, 7 ] [ 8, 4 ] [ 7, 6 ] [ 4, 8 ] [ 7, 6 ] [ 3, 9 ] [ 4, 8 ] [ 3, 9 ]
Nine comparisons. That's right!
And the scopes for each?
Those look right, too, thankfully.
Now for the overly complicated part, I think.
They are:
........... ........... ...X....... ........... .....Y..... <---1N from top X, 2N from bottom X ........... .......Y... <---2N from top X, 1N from bottom X ........... .........X. ...........
Let's handle this.
It's a lot, but the subtleties are important within each clause:
............ ........0... .....0...... .......0.... ....0....... ......A..... ............ ............ ........A... .........A.. ............ ............
Thankfully, all identified antinodes seem correctly placed.
Next, excluding ones that are out-of-bounds
Enter...more conditions!
1,8 vs. 2,5 1 row apart 3 col apart 2 possible antinodes: 0,11: 0 = min(1,2) - 1 3,2 For 0,11 0 = min(1,2) - 1 11 = ....
I am checking for whether each coordinate is between 0 and the length of the rows or the columns.
Then, at the bottom of each clause in my antinode-finder, I call the function on both possible nodes:
(y2 - y1) / (x2 - x1)
And my answer will be the size of my valid set.
Running it generates 12. Not 14.
Why not?
...
After some debugging, I found my error:
1,8 and 2,5 (5 - 8) / (2 - 1) = -3 / 1 = -3
I'm off by one in my assignment of the row. I need a value that is one less:
0 ............ 1 ........0... 2 .....0...... 3 .......0.... 4 ....0....... 5 ......A..... 6 ............ 7 ............ 8 ........A... 9 .........A.. ............ ............ 0123456789
That fixes things.
I see 14 now.
Time to run it on my puzzle input.
...
Correct answer!!!
That took a lot longer than I expected, but I did it!
I can only imagine what Part 2 will require.
Gulp.
This feels harder, though it may be a relatively simple adjustment.
Time to think on it.
...
Mostly because of this gotcha:
exactly in line with at least two antennas of the same frequency
I think I understand this criteria.
My hunch is that at long as there are three of any given frequency, all three antennas are also antinodes.
If I'm wrong, then that's likely why my answer will be off: mistaking an antenna for an antinode.
But I think I have a strategy for identifying all the new antinodes.
My current algorithm finds the antinodes on either end of two antennas.
I instead want to walk along the line in both directions until I am about to step out of bounds.
This will require some refactoring.
I'm ready.
Here's my updated condition for positive slope lines:
............ ........0... 9 .....0...... 8 .......0.... 7 ....0....... 6 ......A..... 5 ............ 4 ............ 3 ........A... 2 .........A.. 1 ............ 0 ............ 0123456789
What changed:
I had to do this for each clause.
I messed one up slightly, which caused me to get an off-by-1 answer using the example input, and to see a really weird grid, which helped me diagnose which clause was malfunctioning.
Eventually, I got it to work on the example input.
Then I ran it on my puzzle input.
And...
I generated the correct answer!!!
I'm so proud of myself!
And I'm so grateful that there was no sneaky edge case in my puzzle input!
Wow, that took several days of passive thinking to work through.
On to another day with two hard earned gold stars.
The above is the detailed content of Resonant Collinearity. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
