day15.rb

require 'set'

if ARGV.empty?
  data = DATA.readlines(chomp: true)
  y = 10
  MAX = 20
else
  data = File.readlines(ARGV[0], chomp: true)
  y = 2000000
  MAX = 4000000
end

def distance(a, b)
  (a[0] - b[0]).abs + (a[1] - b[1]).abs
end

sensors = Set.new
beacons = Set.new
data.map do
  match = /Sensor at x=(?<x>-?\d+), y=(?<y>-?\d+): closest beacon is at x=(?<bx>-?\d+), y=(?<by>-?\d+)/.match(_1)
  sensor = match[:x].to_i, match[:y].to_i
  beacon = match[:bx].to_i, match[:by].to_i
  d = distance(sensor, beacon)
  sensors << [sensor, d]
  beacons << beacon
end

# gets all the points around a point that are
# exactly d + 1 away
def get_points(ep, point, d)
  x, y = point
  (-d..d).each do |dx|
    dy = d - dx.abs
    next if x + dx < 0 || x + dx > MAX
    next if y + dy < 0 || y + dy > MAX
    ep << [x + dx, y + dy]

    next if y - dy < 0 || y - dy > MAX
    ep << [x + dx, y - dy]
  end
end

puts "Finding edge points..."
edge_points = Set.new
sensors.each do |sensor, d|
  get_points(edge_points, sensor, d + 1)
end
puts "Found #{edge_points.size} edge points"

excluded = Set.new
edge_points.each do |ep|
  sensors.each do |sensor, d|
    if distance(ep, sensor) <= d
      excluded << ep
      break
    end
  end
end
p edge_points - excluded
x, y = (edge_points - excluded).first
puts "Part 1: #{x *4000000 + y}"

# part 1
# excluded = Set.new
#
# (-10_000_000..10_000_000).each do |x|
#   pt = [x, y]
#   sensors.each do |sensor, d|
#     if distance(pt, sensor) <= d
#       if !beacons.include?(pt)
#         excluded << pt
#       end
#     end
#   end
# end
#
# p excluded.size


__END__
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

https://youtu.be/7p9RsY9-dp4

https://youtu.be/ij9WmVQfLgc