Day 15, part 2 broken.

4 files changed, 140 insertions, 0 deletions

diff --git a/day15/input b/day15/input
new file mode 100644
index 0000000..f651b7f
--- /dev/null
+++ b/day15/input
@@ -0,0 +1,29 @@
+Sensor at x=2557568, y=3759110: closest beacon is at x=2594124, y=3746832
+Sensor at x=2684200, y=1861612: closest beacon is at x=2816974, y=2000000
+Sensor at x=1003362, y=1946094: closest beacon is at x=1972523, y=2563441
+Sensor at x=2142655, y=1481541: closest beacon is at x=1932524, y=967542
+Sensor at x=2796219, y=1955744: closest beacon is at x=2816974, y=2000000
+Sensor at x=3890832, y=1818644: closest beacon is at x=3454717, y=2547103
+Sensor at x=2828842, y=1921726: closest beacon is at x=2816974, y=2000000
+Sensor at x=2065227, y=583957: closest beacon is at x=1932524, y=967542
+Sensor at x=2725784, y=2088998: closest beacon is at x=2816974, y=2000000
+Sensor at x=3574347, y=927734: closest beacon is at x=1932524, y=967542
+Sensor at x=2939312, y=2652370: closest beacon is at x=3454717, y=2547103
+Sensor at x=2495187, y=3681541: closest beacon is at x=2431306, y=3703654
+Sensor at x=2878002, y=2054681: closest beacon is at x=2816974, y=2000000
+Sensor at x=1539310, y=3235516: closest beacon is at x=1972523, y=2563441
+Sensor at x=545413, y=533006: closest beacon is at x=-538654, y=69689
+Sensor at x=1828899, y=3980292: closest beacon is at x=2431306, y=3703654
+Sensor at x=3275729, y=2937931: closest beacon is at x=3454717, y=2547103
+Sensor at x=600131, y=3861189: closest beacon is at x=2431306, y=3703654
+Sensor at x=2089895, y=28975: closest beacon is at x=1932524, y=967542
+Sensor at x=2960402, y=3942666: closest beacon is at x=2594124, y=3746832
+Sensor at x=3785083, y=3905392: closest beacon is at x=2594124, y=3746832
+Sensor at x=1721938, y=1077173: closest beacon is at x=1932524, y=967542
+Sensor at x=2515156, y=3751221: closest beacon is at x=2594124, y=3746832
+Sensor at x=2469423, y=2109095: closest beacon is at x=2816974, y=2000000
+Sensor at x=1776986, y=904092: closest beacon is at x=1932524, y=967542
+Sensor at x=2789294, y=3316115: closest beacon is at x=2594124, y=3746832
+Sensor at x=3538757, y=2695066: closest beacon is at x=3454717, y=2547103
+Sensor at x=2299738, y=2708004: closest beacon is at x=1972523, y=2563441
+Sensor at x=2388366, y=3234346: closest beacon is at x=2431306, y=3703654
diff --git a/day15/part1.rb b/day15/part1.rb
new file mode 100644
index 0000000..7dd3531
--- /dev/null
+++ b/day15/part1.rb
@@ -0,0 +1,36 @@
+class Sensor
+  def initialize(sx, sy, bx, by)
+    @x = sx
+    @y = sy
+    @range = (sx - bx).abs + (sy - by).abs
+  end
+
+  attr_reader :x, :y, :range
+end
+
+sensors = []
+beacons = []
+$stdin.readlines.each do |line|
+  c = line.scan(/x=(-?\d+), y=(-?\d+)/).flatten.map(&:to_i)
+  sensors << Sensor.new(*c)
+  beacons << c[2..3]
+end
+
+row = 2_000_000
+
+xranges = []
+sensors.each do |s|
+  dx = s.range - (s.y - row).abs
+  xranges << ((s.x - dx)..(s.x + dx)) if dx > 0
+end
+
+from = xranges.map(&:begin).min 
+to = xranges.map(&:end).max
+xs = to - from + 1
+
+(from..to).each do |x|
+  xs += 1 unless xranges.any? { |xrange| xrange.include?(x) }
+end
+xs -= beacons.select { |_, y| y == row }.map { |x, _| x }.uniq.count
+
+pp xs
diff --git a/day15/part2.rb b/day15/part2.rb
new file mode 100644
index 0000000..cb3219d
--- /dev/null
+++ b/day15/part2.rb
@@ -0,0 +1,61 @@
+class Sensor
+  def initialize(sx, sy, bx, by)
+    @x = sx
+    @y = sy
+    @range = dist(bx, by)
+  end
+
+  attr_reader :x, :y, :range
+
+  def dist(x, y)
+    (@x - x).abs + (@y - y).abs
+  end
+
+  def cover?(x, y)
+    dist(x, y) <= @range
+  end
+
+  def edge
+    edges = []
+    at = [@x, @y - (@range + 1)]
+    until at[1] == @y
+      edges << at
+      at[0] += 1
+      at[1] += 1
+    end
+    until at[0] == @x
+      edges << at
+      at[0] -= 1
+      at[1] += 1
+    end
+    until at[1] == @y
+      edges << at
+      at[0] -= 1
+      at[1] -= 1
+    end
+    until at[0] == @x
+      edges << at
+      at[0] += 1
+      at[1] -= 1
+    end
+    edges
+  end
+end
+
+sensors = []
+$stdin.readlines.each do |line|
+  c = line.scan(/x=(-?\d+), y=(-?\d+)/).flatten.map(&:to_i)
+  sensors << Sensor.new(*c)
+end
+
+max = 4_000_000
+
+coord = sensors.map { |s|
+  s.edge.reject { |e|
+    e[0] < 0 || e[0] > max ||
+    e[1] < 0 || e[1] > max ||
+    sensors.any? { |s2| s2.cover?(*e) }
+  }
+}.flatten(1).uniq[0]
+
+puts coord[0] * 4_000_000 + coord[1]
diff --git a/day15/test b/day15/test
new file mode 100644
index 0000000..a612424
--- /dev/null
+++ b/day15/test
@@ -0,0 +1,14 @@
+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