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.
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