Resonant Collinearity

Advent of Code 2024 Day 8

Part 1

I think I get it. Can I do it?

As I understand it:

• For each pair of identical ligatures
• Find the point X where one ligature is 1N and the other is 2N - where N is some distance from X
• As long as it is within the bounds of the grid, count it toward the answer

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?

Calculating 1N and 2N algorithmically

Here's the example grid:

............
........0...
.....0......
.......0....
....0.......
......A.....
............
............
........A...
.........A..
............
............

I'll focus on the 0s:

• There are four
• Coordinates are: 1,8, 2,5, 3,7, 4,4

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.

Refreshing my memory about slope

The formula is:

(y2 - y1) / (x2 - x1)

The outcome will be one of these four:

• > 0 means positive slope: up and to the right
• < 0 means negative slope: down and to the right
• 0 means horizontal line
• Infinity means vertical line

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!

Starting to code

Building the list of antenna coordinates

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])
    }
  }
}

Creates this object for the example input:

{
  '0': [ [ 11, 8 ], [ 10, 5 ], [ 9, 7 ], [ 8, 4 ] ],
  A: [ [ 7, 6 ], [ 4, 8 ], [ 3, 9 ] ]
}

Looks great!

Next, calculating slope.

Writing an overly complex antinode-finder

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.

Handling all four slope types

They are:

- 0
\ -1
| Infinity
/ +1

Let's handle this.

It's a lot, but the subtleties are important within each clause:

let slope = getScope(f[i], f[j])
if (slope == Infinity) { 
  let Ydiff = Math.abs(f[i][0] - f[j][0])
  let node1 = [Math.max(f[i][0],f[j][0]) + Ydiff, f[i][1]]
  let node2 = [Math.min(f[i][0],f[j][0]) - Ydiff, f[i][1]]
} else if (slope < 0) {
  let Ydiff = Math.abs(f[i][0] - f[j][0])
  let Xdiff = Math.abs(f[i][1] - f[j][1])
  let node1 = [Math.min(f[i][0],f[j][0]) - Ydiff, Math.max(f[i][1],f[j][1]) + Xdiff]
  let node2 = [Math.max(f[i][0],f[j][0]) + Ydiff, Math.min(f[i][1],f[j][1]) - Xdiff]
} else if (slope == 0) {
  let Xdiff = Math.abs(f[i][1] - f[j][1])
  let node1 = [f[i][0], Math.max(f[i][1],f[j][1]) + Xdiff]
  let node2 = [f[i][0], Math.min(f[i][1],f[j][1]) - Xdiff]
} else if (slope > 0) {
  let Ydiff = Math.abs(f[i][0] - f[j][0])
  let Xdiff = Math.abs(f[i][1] - f[j][1])
  let node1 = [Math.max(f[i][0],f[j][0]) + Ydiff, Math.max(f[i][1],f[j][1]) + Xdiff]
  let node2 = [Math.min(f[i][0],f[j][0]) - Ydiff, Math.min(f[i][1],f[j][1]) - Xdiff]
}

Thankfully, all identified antinodes seem correctly placed.

Next, excluding ones that are out-of-bounds

Excluding the out-of-bounds antinodes

Enter...more conditions!

function addNode(p1) {
  if (
    p1[0] >= 0 && p1[0] < graph.length &&
    p1[1] >= 0 && p1[1] < graph[0].length
  ) {
    valid.add(p1.join(','))
  }
}

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:

addNode(node1)
addNode(node2)

And my answer will be the size of my valid set.

Does this actually work?

Running it generates 12. Not 14.

Why not?

...

After some debugging, I found my error:

antennas[graph[y][x]].push([graph.length - y,x])

I'm off by one in my assignment of the row. I need a value that is one less:

antennas[graph[y][x]].push([graph.length - 1 - y,x])

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.

Part 2

Yup. Lots more antinodes to identify.

This feels harder, though it may be a relatively simple adjustment.

Time to think on it.

...

Going in with low confidence of generating the correct answer

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.

Enter: more while loops to walk the lines

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:

if (slope > 0) {
  let Ydiff = Math.abs(f[i][0] - f[j][0])
  let Xdiff = Math.abs(f[i][1] - f[j][1])
  let next1 = [Math.max(f[i][0],f[j][0]) + Ydiff, Math.max(f[i][1],f[j][1]) + Xdiff]
  while (isInBounds(next1)) {
    valid.add(next1.join(','))
    next1 = [next1[0] + Ydiff, next1[1] + Xdiff]
  }
  let next2 = [Math.min(f[i][0],f[j][0]) - Ydiff, Math.min(f[i][1],f[j][1]) - Xdiff]
  while (isInBounds(next2)) {
    valid.add(next2.join(','))
    next2 = [next2[0] - Ydiff, next2[1] - Xdiff]
  }
}

What changed:

• I perform Math once up front
• Inside the while loop I add the coordinate, then I just increment or decrement each coordinate by the corresponding diff
• The condition uses my updated function which returns a boolean instead of adding the coordinate automatically

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.