Advent of Code 2022, Day 15: Beacon Exclusion Zone

#ruby #advent of code 2022

Part A

On Day 15 we are looking for a beacon. We have a bunch of sensors that are scanning nearby areas and report back with positions of beacons. This is our input:

Sensor at x=2, y=18: closest beacon is at x=-2, y=15
Sensor at x=9, y=16: closest beacon is at x=10, y=16
Sensor at x=13, y=2: closest beacon is at x=15, y=3
Sensor at x=12, y=14: closest beacon is at x=10, y=16
Sensor at x=10, y=20: closest beacon is at x=10, y=16
Sensor at x=14, y=17: closest beacon is at x=10, y=16
Sensor at x=8, y=7: closest beacon is at x=2, y=10
Sensor at x=2, y=0: closest beacon is at x=2, y=10
Sensor at x=0, y=11: closest beacon is at x=2, y=10
Sensor at x=20, y=14: closest beacon is at x=25, y=17
Sensor at x=17, y=20: closest beacon is at x=21, y=22
Sensor at x=16, y=7: closest beacon is at x=15, y=3
Sensor at x=14, y=3: closest beacon is at x=15, y=3
Sensor at x=20, y=1: closest beacon is at x=15, y=3

All distances are measure by the Manhattan distance. Each sensor can detect only one, closest beacon. Our input file can be represented by the following map:

               1    1    2    2
     0    5    0    5    0    5
 0 ....S.......................
 1 ......................S.....
 2 ...............S............
 3 ................SB..........
 4 ............................
 5 ............................
 6 ............................
 7 ..........S.......S.........
 8 ............................
 9 ............................
10 ....B.......................
11 ..S.........................
12 ............................
13 ............................
14 ..............S.......S.....
15 B...........................
16 ...........SB...............
17 ................S..........B
18 ....S.......................
19 ............................
20 ............S......S........
21 ............................
22 .......................B....

None of the reported beacons is producing distress signal, which means not all area is covered by our sensors. In Part A we need to output how many positions are covered in the row 2000000.

Here is the full code:

target_y = 2000000
data = File.readlines("15.txt", chomp: true)

sensors = data.map do |line|
  line.match(/Sensor at x=(\-?\d+), y=(\-?\d+): closest beacon is at x=(\-?\d+), y=(\-?\d+)/).captures.map(&:to_i)
end

beacons = sensors.map { |sensor| sensor[3] == target_y ? sensor[2] : nil }.compact.uniq

def manhattan(p1_x, p1_y, p2_x, p2_y)
  (p1_x - p2_x).abs + (p1_y - p2_y).abs
end

def sensor_cross_y?(sx, sy, bx, by, y)
  (sy - y).abs <= manhattan(sx, sy, bx, by)
end

def coverage(sx, sy, bx, by, y)
  distance = manhattan(sx, sy, bx, by)
  results = []

  (sx - distance).upto(sx + distance).each do |x|
    if manhattan(sx, sy, x, y) <= distance
      results.push(x)
    end
  end

  results
end

points = []
sensors.each do |sensor|
  if sensor_cross_y?(*sensor, target_y)
    coverage(*sensor, target_y).each do |x|
      next if beacons.include?(x)

      points.push(x)
    end
  end
end

puts points.uniq.size

It is pretty simple. We parse the input, then iterate over each sensor and calculate which points they cover. First we check if given sensor is actually touching our target row 2000000. If yes we scan all x positions this sensor can possibly cover and add them to the array.

Please note that this code is not optimal. If given sensor touches target row in just one single point we will still check all possible points in this row within given sensor range.

But it is enough to find a solution in couple of seconds.

Part B

Things get more difficult in Part B and naive solution won’t cut it. Now we need to find the single point that is not covered by any beacon in the area of 4000000 x 4000000.

This was the first puzzle that took me long time to solve. I did Part A pretty quickly and then was struggling with Part B. Maybe it is because I don’t have much experience with geometry algorithms.

My first idea was to maintain a polygon covering the whole area where this point can be. In the beginning this polygon will be just plain rectangle with four corners. Then we will pick a sensor from the list that is close to one of the corners and we will cut out the sensor coverage area from this polygon.

With each sensor processed our polygon will become smaller and smaller and eventually should contain just one point.

I still think it is not a bad idea, but I was hoping I can quickly look up the code for representing polygons and producing intersections of polygons.

Well I couldn’t find anything quickly, but then I thought about another solution. Since we are looking for just one pixel it must be located somewhere on the intersection of those polygons representing sensors coverage area.

So what we can do is to take all sensors, generate all four segments representing their coverage area. We are dealing with Taxicab geometry, so their coverage areas are not circles, but rhombuses. Given sensor position we can easily calculate their top, right, bottom and right corners and then generate segments for each side of rhombus:

def circle_points(x, y, r)
  [
    [x - r, y],
    [x, y + r],
    [x + r, y],
    [x, y - r]
  ]
end

def circle_segments(x, y, r)
  [
    [x - r, y, x, y + r],
    [x, y + r, x + r, y],
    [x + r, y, x, y - r],
    [x, y - r, x - r, y]
  ].map do |(x1, y1, x2, y2)|
    if x1 <= x2
      [x1, y1, x2, y2]
    else
      [x2, y2, x1, y1]
    end
  end
end

In my solution I named my methods confusingly circle_points and circle_segments. First one generate rhombus corner points and second one generates segments for each rhombus side.

Next we need a method to calculate intersection point of two segments. Here is my (probably) overcomplicated version:

def segments_intersection(s1, s2)
  x11, y11, x12, y12 = s1
  x21, y21, x22, y22 = s2

  if (x11 - x12) == 0
    a2 = (y21 - y22) / (x21 - x22)
    b2 = y21 - a2 * x21  

    x = x11
    y = a2 * x + b2

    return [x, y]
  elsif (x21 - x22) == 0
    a1 = (y11 - y12) / (x11 - x12)
    b1 = y11 - a1 * x11

    x = x21
    y = a1 * x + b1

    return [x, y]
  end

  a1 = (y11 - y12) / (x11 - x12)
  b1 = y11 - a1 * x11

  a2 = (y21 - y22) / (x21 - x22)
  b2 = y21 - a2 * x21

  x = nil
  y = nil

  if a1 == 0
    x = (b1 - b2) / a2.to_f
    y = b1
  elsif a2 == 0
    x = (b2 - b1) / a1.to_f
    y = b2
  elsif a1 == a2
    return []
  else
    x = (b2 - b1) / 2.to_f * a1
    y = (b2 - b1) / 2.to_f + b1
  end

  xs = [x.floor, x.ceil]
  ys = [y.floor, y.ceil]

  xs.product(ys).uniq
end

First condition if (x11 - x12) == 0 handles case where first segment is vertical line and second one elsif (x21 - x22) == 0 handles case where second segment is vertical line. We can have vertical lines if want to get intersection point with left or right border lines.

In general to calculate intersection point, we need to write line equation for both segments and then solve those equations. Again, I am not good at math, but I guess line equation can be written as y = a * x + b. The a component can be written as a = (y1 - y2) / (x1 - x2), where we substitute points on both ends of the segment. The b component can be written as b2 = y21 - a2 * x21.

Line equation for vertical line is just x = x21. We can now substitute all those values in y = a1 * x + b1.

Later on we have conditions for horizontal lines:

a1 = (y11 - y12) / (x11 - x12)
b1 = y11 - a1 * x11

a2 = (y21 - y22) / (x21 - x22)
b2 = y21 - a2 * x21

x = nil
y = nil

if a1 == 0
  x = (b1 - b2) / a2.to_f
  y = b1
elsif a2 == 0
  x = (b2 - b1) / a1.to_f
  y = b2

We first calculate a and b components for both segments. If a equals 0 it means that line is horizontal, so the solution to their equations is simpler.

Then if a1 == a2 it means segments are parallel and they don’t have any intersection points.

And finally we have the solution for most common case, where both segments are diagonal:

else
  x = (b2 - b1) / 2.to_f * a1
  y = (b2 - b1) / 2.to_f + b1
end

There is one more catch. We are dealing with integer numbers only. All are positions are integer numbers, but in the above equations you can get float numbers as well. In that case we need to return multiple intersection points. If you get intersection at (1.5, 1.5) we need to return 4 points (1, 1), (1, 2), (2, 1) and (2, 2). That’s why at the end of this method I am doing this:

xs = [x.floor, x.ceil]
ys = [y.floor, y.ceil]

xs.product(ys).uniq

Having all those methods we can start calculating all those intersection points possible:

points = []
segments = []

@sensors.each do |sensor|
  points.concat(circle_points(*sensor))
  segments.concat(circle_segments(*sensor))
end

n = segments.size

n.times do |i|
  n.times do |j|
    next if i == j

    intersections = segments_intersection(segments[i], segments[j])

    if intersections.any?
      points.concat(intersections)
    end
  end
end

points.uniq!

First we add all corner points from coverage rhombuses. Then we generate list of all segments and then we try to find intersections between all segments. We are just using O(n^2) algorithm here and we add all intersection points to our array. Finally we remove duplicates.

But the beacon can’t be located on the intersection point. It must be located next to some intersection point. Either above, right, left of below it. So we need to remap our list of points. For each point we need to generate it’s four neighbors:

points = points.flat_map do |(x, y)|
  [
    [x - 1, y],
    [x, y - 1],
    [x + 1, y],
    [x, y + 1]
  ]
end

points.uniq!

Then we can remove all points that are outside of our 4000000 x 4000000 boundaries:

points.reject! do |(x, y)|
  x < 0 || y < 0 || x > 4_000_000 || y > 4_000_000
end

For puzzle input I’ve got around 13k points meeting above requirements.

Now the final step is to check each point and find the one that is not covered by any sensor:

points.each do |(x, y)|
  covered = @sensors.any? { |(sx, sy, d)| manhattan(x, y, sx, sy) <= d }

  if !covered
    puts 4000000 * x + y
  end
end

Here is the full code:

require "debug"
require "io/console"
data = File.readlines("15.txt", chomp: true)

def manhattan(p1_x, p1_y, p2_x, p2_y)
  (p1_x - p2_x).abs + (p1_y - p2_y).abs
end

@sensors = data.map do |line|
  values = line.match(/Sensor at x=(\-?\d+), y=(\-?\d+): closest beacon is at x=(\-?\d+), y=(\-?\d+)/).captures.map(&:to_i)
  [values[0], values[1], manhattan(*values)]
end.sort do |a, b|
  a[1] <=> b[1]
end

def circle_points(x, y, r)
  [
    [x - r, y],
    [x, y + r],
    [x + r, y],
    [x, y - r]
  ]
end

def circle_segments(x, y, r)
  [
    [x - r, y, x, y + r],
    [x, y + r, x + r, y],
    [x + r, y, x, y - r],
    [x, y - r, x - r, y]
  ].map do |(x1, y1, x2, y2)|
    if x1 <= x2
      [x1, y1, x2, y2]
    else
      [x2, y2, x1, y1]
    end
  end
end

def segments_intersection(s1, s2)
  x11, y11, x12, y12 = s1
  x21, y21, x22, y22 = s2

  if (x11 - x12) == 0
    a2 = (y21 - y22) / (x21 - x22)
    b2 = y21 - a2 * x21  

    x = x11
    y = a2 * x + b2

    return [x, y]
  elsif (x21 - x22) == 0
    a1 = (y11 - y12) / (x11 - x12)
    b1 = y11 - a1 * x11

    x = x21
    y = a1 * x + b1

    return [x, y]
  end

  a1 = (y11 - y12) / (x11 - x12)
  b1 = y11 - a1 * x11

  a2 = (y21 - y22) / (x21 - x22)
  b2 = y21 - a2 * x21

  x = nil
  y = nil

  if a1 == 0
    x = (b1 - b2) / a2.to_f
    y = b1
  elsif a2 == 0
    x = (b2 - b1) / a1.to_f
    y = b2
  elsif a1 == a2
    return []
  else
    x = (b2 - b1) / 2.to_f * a1
    y = (b2 - b1) / 2.to_f + b1
  end

  xs = [x.floor, x.ceil]
  ys = [y.floor, y.ceil]

  xs.product(ys).uniq
end

points = []
segments = []

@sensors.each do |sensor|
  points.concat(circle_points(*sensor))
  segments.concat(circle_segments(*sensor))
end

n = segments.size

n.times do |i|
  n.times do |j|
    next if i == j

    intersections = segments_intersection(segments[i], segments[j])

    if intersections.any?
      points.concat(intersections)
    end
  end
end

points.uniq!

points = points.flat_map do |(x, y)|
  [
    [x - 1, y],
    [x, y - 1],
    [x + 1, y],
    [x, y + 1]
  ]
end

points.uniq!

points.reject! do |(x, y)|
  x < 0 || y < 0 || x > 4_000_000 || y > 4_000_000
end

puts points.size

points.each do |(x, y)|
  covered = @sensors.any? { |(sx, sy, d)| manhattan(x, y, sx, sy) <= d }

  if !covered
    puts 4000000 * x + y
  end
end