day 15 part 1

1 files changed, 41 insertions, 0 deletions

diff --git a/22.15/main.py b/22.15/main.py
new file mode 100644
index 0000000..c366999
--- /dev/null
+++ b/22.15/main.py
@@ -0,0 +1,41 @@
+import sys, re
+# ranges are inclusive from both ends
+
+def range_intersect(a, b):
+	return a[0] <= b[0] <= a[1] or a[0] <= b[1] <= a[1] or b[0] <= a[0] <= b[1] or b[0] <= a[1] <= b[1]
+
+class RangeSet:
+	def __init__(self):
+		self.rs = []
+	def add(self, a, b):
+		for i in range(len(self.rs)):
+			r = self.rs[i]
+			if range_intersect(r, (a, b)):
+				a = min(a, r[0])
+				b = max(b, r[1])
+				self.rs[i] = None
+		self.rs = [r for r in self.rs if r]
+		self.rs.append((a, b))
+	def size(self):
+		s = 0
+		for r in self.rs:
+			s += r[1] - r[0] + 1
+		return s
+
+data = []
+for line in sys.stdin:
+	data.append([int(n) for n in re.findall('\d+', line)])
+
+manhattan = [abs(a[0] - a[2]) + abs(a[1] - a[3]) for a in data]
+
+def partOne(y):
+	r = RangeSet()
+	for l, m in zip(data, manhattan):
+		w = m - abs(l[1] - y)
+		if w < 0: continue
+		#print(l, w, l[0] - w, l[0] + w)
+		r.add(l[0] - w, l[0] + w)
+	beacons = set([(a[2], a[3]) for a in data if a[3] == y])
+	return r.size() - len(beacons)
+
+print(partOne(2000000))