Beacon Exclusion Zone

Advent of Code 2022 Day 15

Part 1

1. Great, more sensors and beacons
2. Drawing each example sensor's circle
3. Looking for patterns in the circles
4. Turning the pattern into an algorithm
5. Storing each position, not the number of positions
6. My algorithm in JavaScript

Great, more sensors and beacons

• I have an o.k. track record with this puzzle type
• I'm happy it's currently a 2D space and not a 3D space
• But the challenge has me a bit confused

I'm gonna need to fill in more gaps of the example diagram in order to fully understand how to approach solving this puzzle.

Drawing each example sensor's circle

• One sensor's circle is depicted in the diagram
• It's very helpful in visualizing the circumference of the area surrounding a sensor where there cannot be any beacons
• But I am confused when I see the slice depicted in the second diagram
• So I need to visualize a few more sensors' circles

After some fun in my design tool, I made this map:

Doing that removed my confusion as to how the third diagram showing the 3-row slice was derived.

Now I'm confused as to how I would programmatically identify all 26 of those positions.

Looking for patterns in the circles

For this sensor:

Sensor at x=8, y=7: closest beacon is at x=2, y=10

The Manhattan Distance from sensor to beacon is:

Math.abs(8 - 2) + Math.abs(7 - 10) // 6 + 3 = 9

As depicted in the diagram, that gives the circle spanning all positions where a beacon cannot exist a radius of 9.

Drawing a horizontal line through the middle of this circle would result in a line of length of 18, the diameter.

And a number of positions equal to the diameter plus 1.

A line drawn through the circle one row lower: 17
One row lower: 15
One row lower: 13

Interesting. There's a formula here relating Manhattan Distance with decrements of 2 depending on the number of rows away from the sensor.

I hope this becomes of use in solving Part 1.

Turning the pattern into an algorithm

Back to the example sensor:

Sensor at x=8, y=7: closest beacon is at x=2, y=10

The Manhattan Distance from sensor to beacon is 9.

The target row is y=10.

First mystery: does the sensor's deadzone circumference intersect with that row?

To find out, I'll check whether the target row minus the sensor row is less than or equal to the Manhattan Distance:

Math.abs(10 - 7) // 3 <= 9? Yes! Intersection!

Second mystery: how many positions on the target row cannot contain a beacon closest to this sensor?

Well, we just learned the row is 3 away from the sensor.

The Manhattan Distance is 9.

Sensor's middle row:
(MD - 0) * 2 + 1
(9  - 0) * 2 + 1
 9       * 2 + 1
 18          + 1
 19

Sensor's 1st non-middle row in either direction:
(MD - 1) * 2 + 1
 ...
 17

Sensor's 2nd non-middle row in either direction:
(MD - 2) * 2 + 1
 15

Sensor's 3rd non-middle row in either direction:
(MD - 3) * 2 + 1
 13

Sensor's Nth non-middle row in either direction:
(MD - N) * 2 + 1

Is that the formula?

I need to try it on another sensor that intersects with the target row!

Thanks to the full picture I drew earlier, I know this one does:

Sensor at x=20, y=14: closest beacon is at x=25, y=17

Manhattan Distance:

Math.abs(20 - 25) + Math.abs(14 - 17) // 5 + 3 = 8

Rows away from target row:

Math.abs(14 - 10) // 4 <= 8 ? Yes! Intersection!

Positions in target row that cannot be a beacon:

(MD - 4) * 2 + 1
(8  - 4) * 2 + 1
 4       * 2 + 1
 8           + 1
 9

Using my drawing to confirm: Yes, there are 9 positions!

I think I'm on to something!

Storing each position, not the number of positions

I'm glad I have a formula for determining the length of the slice of the circle that may intersect with my target y.

But now I need to use that formula in a loop that walks left-to-right along that line and records each point.

In pseudocode:

If the target row is less than or equal to the largest Manhattan Distance away from the sensor's `y` coordinate
  For i from the left-most point to the right-most point
    Add the point to a collection of all unique points encountered thus far

In JavaScript:

if (rowsAway <= MD) {
  let slots = (MD - rowsAway) * 2 + 1
  for (let i = -((slots - 1) / 2); i <= ((slots - 1) / 2); i++) {
    all.add(String([sx + i, target]))
  }
}

The math is a bit yucky, but it essentially moves i from a negative number to its equivalent positive number using the y coordinate of the sensor as a 0 midpoint.

After testing this in my broader algorithm, I noticed an issue:

• I was returning a number one higher than the expected amount

How come?

• I wasn't accounting for the existence of a beacon at one of the points

Oh ya!

• Each of the sensors that intersected with the target y coordinate has a beacon at one of the points in their circle
• And it is entirely possible that the beacon's y coordinate is the same as the target

Thankfully, this is easy to account for.

In JavaScript:

// inside for loop
if (String([bx,by]) !== String([sx + i, target])) {
  all.add(String([sx + i, target]))
}

My algorithm in JavaScript

(target) => {
   return input
     .split('\n')
     .reduce((total, sensor) => {
       let [sx, sy, bx, by] = [
         ...sensor.matchAll(/-?\d+/g)
       ].map(el => +el[0])
       let MD = (
         Math.abs(sx - bx) +
         Math.abs(sy - by)
       )
       let rowsAway = Math.abs(sy - target)
       if (rowsAway <= MD) {
         let slots = (MD - rowsAway) * 2 + 1
         for (let i = -((slots - 1) / 2); i <= ((slots - 1) / 2); i++) {
           if (String([bx, by]) !== String([sx + i, target])) {
             total.add(String([sx + i, target]))
           }
         }
       }
       return total
     }, new Set()).size
}

I had to refactor it a bit to overcome a heap error related to large array sizes.

The resulting algorithm uses only a single Set() filled with unique stringified coordinates.

It still takes several seconds to run.

But when finished, it generates the correct answer for my puzzle input!

Part 2

1. Needle in a trillion-straw hay stack
2. Seeing the signal in the example input

Needle in a trillion-straw hay stack

• I need to search a 4M square area for a distress signal's coordinates
• That is as many as 16 trillion positions!
• Thus, this is clearly a performance test
• I don't do well with those

Seeing the signal in the example input

Remember the image above showing each sensor's diamond-shaped circles?

Here it is again with the only open dot between 0 and 20 x and y highlighted in yellow (at 11,14):

How would I find it algorithmically?

For each point from 0-20 y
  For each point from 0-20 x
    If the point is outside of every sensor's circle
      Distress signal found!
    Else, if the point is inside of even a single sensor's circle
      Skip to the next point

That of course would finish quickly on the example.

And probably never finish on a 16 trillion tile square area.

So I'm not inclined to write and run it.

I did it!

• I solved Part 1!
• Using Math() and Set() and regex and reduce()!
• And drawing, of course!

I wish my puzzle input's area were smaller, as it would have been fun to render the sensors and their circles to ultimately spot the distress signal.

I'm glad my track record with these beacon-position puzzles remains 50/50 (1/2 stars average).