Day 15

3 files changed, 163 insertions, 0 deletions

diff --git a/day15/example.txt b/day15/example.txt
new file mode 100644
index 0000000..a612424
--- /dev/null
+++ b/day15/example.txt
@@ -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
diff --git a/day15/input.txt b/day15/input.txt
new file mode 100644
index 0000000..ec728e8
--- /dev/null
+++ b/day15/input.txt
@@ -0,0 +1,32 @@
+Sensor at x=3428425, y=2345067: closest beacon is at x=3431988, y=2379841
+Sensor at x=928237, y=25774: closest beacon is at x=1212315, y=-161555
+Sensor at x=2061220, y=2396791: closest beacon is at x=2038311, y=2495160
+Sensor at x=1830400, y=2994568: closest beacon is at x=1910058, y=3117415
+Sensor at x=2485733, y=2625804: closest beacon is at x=2038311, y=2495160
+Sensor at x=1855873, y=3971916: closest beacon is at x=1910058, y=3117415
+Sensor at x=119582, y=3929652: closest beacon is at x=311197, y=4221202
+Sensor at x=1069031, y=3509672: closest beacon is at x=1910058, y=3117415
+Sensor at x=3368023, y=2213635: closest beacon is at x=3431988, y=2379841
+Sensor at x=3713877, y=2460862: closest beacon is at x=3431988, y=2379841
+Sensor at x=3593503, y=2174008: closest beacon is at x=3507689, y=2000000
+Sensor at x=501760, y=93436: closest beacon is at x=1212315, y=-161555
+Sensor at x=3712703, y=214999: closest beacon is at x=3507689, y=2000000
+Sensor at x=1594824, y=2790273: closest beacon is at x=1910058, y=3117415
+Sensor at x=2539549, y=3190814: closest beacon is at x=1910058, y=3117415
+Sensor at x=3522790, y=2671548: closest beacon is at x=3431988, y=2379841
+Sensor at x=1001452, y=1327490: closest beacon is at x=1212315, y=-161555
+Sensor at x=629209, y=2451628: closest beacon is at x=-416149, y=2226089
+Sensor at x=2636827, y=1146266: closest beacon is at x=3507689, y=2000000
+Sensor at x=3909, y=625124: closest beacon is at x=1212315, y=-161555
+Sensor at x=3950231, y=3688780: closest beacon is at x=3888160, y=3226725
+Sensor at x=3449978, y=2328058: closest beacon is at x=3431988, y=2379841
+Sensor at x=3974214, y=2582925: closest beacon is at x=3888160, y=3226725
+Sensor at x=82663, y=3225533: closest beacon is at x=311197, y=4221202
+Sensor at x=1958305, y=2292045: closest beacon is at x=2038311, y=2495160
+Sensor at x=3465738, y=2123353: closest beacon is at x=3507689, y=2000000
+Sensor at x=2940758, y=3884337: closest beacon is at x=2746166, y=4800483
+Sensor at x=3429173, y=2275591: closest beacon is at x=3431988, y=2379841
+Sensor at x=1527349, y=38565: closest beacon is at x=1212315, y=-161555
+Sensor at x=3049925, y=2498038: closest beacon is at x=3431988, y=2379841
+Sensor at x=1593202, y=3335178: closest beacon is at x=1910058, y=3117415
+Sensor at x=3175520, y=3230234: closest beacon is at x=3888160, y=3226725
diff --git a/day15/solution.nim b/day15/solution.nim
new file mode 100644
index 0000000..58e2aab
--- /dev/null
+++ b/day15/solution.nim
@@ -0,0 +1,117 @@
+import strutils
+import sequtils
+import re
+import sugar
+import algorithm
+import sets
+
+type
+  Point = tuple
+    x: int
+    y: int
+  
+  Range = tuple
+    b: int
+    l: int
+
+  Entry = tuple
+    sensor: Point
+    beacon: Point
+    distance: int
+
+proc distance(A, B: Point): int =
+  result = abs(A.x - B.x) + abs(A.y - B.y)
+
+proc disjoinWith(A, B: Range): bool =
+  return A.b + A.l < B.b
+
+proc rangeContains(r: Range, y: int, p: Point): bool =
+  p.y == y and r.b <= p.x and p.x <= r.b + r.l - 1
+
+proc unite(A, B: Range): Range =
+  assert(A.b <= B.b)
+  assert(not A.disjoinWith(B))
+  result = (A.b, max(A.l, B.b - A.b + B.l))
+
+proc rangeComparator(A, B: Range): int =
+  if A.b < B.b or (A.b == B.b and A.l <= B.l):
+    return -1
+  else:
+    return 1
+
+proc parsePoint(strPoint: string): Point = 
+  let tokens = strPoint.split(",")
+  Point((tokens[0].parseInt(), tokens[1].parseInt()))
+
+proc parseEntry(strEntry: string): Entry =
+  let tokens = strEntry.split(":")
+  let points = @[tokens[0].parsePoint(), tokens[1].parsePoint()]
+  Entry((points[0], points[1], distance(points[0], points[1])))
+
+proc parseFile(content: string): seq[Entry] =
+  let lines = content.strip().splitLines()
+
+  let strEntries = map(
+    lines,
+    (line) => line.replace(re"[^0-9\-,:]")
+  )
+
+  result = map(
+    strEntries,
+    parseEntry
+  )
+
+proc emptyRanges(entries: seq[Entry], criticalLine: int): seq[Range] =
+  var emptyRanges: seq[Range]
+  for entry in entries:
+    let
+      distFromLine = abs(entry.sensor.y - criticalLine)
+      rangeFromMid = entry.distance - distFromLine
+      b = entry.sensor.x - rangeFromMid
+      e = entry.sensor.x + rangeFromMid
+      l = e - b + 1
+    if l > 0:
+      emptyRanges.add((b, l))
+
+  emptyRanges.sort(rangeComparator)
+  var
+    curr = emptyRanges[0]
+    lastPushed = true
+
+  for other in emptyRanges[1..^1]:
+    lastPushed = false
+    if curr.disjoinWith(other):
+      result.add(curr)
+      lastPushed = true
+      curr = other
+    else:
+      curr = curr.unite(other)
+
+  if not lastPushed:
+    result.add(curr)
+
+proc part1(entries: seq[Entry], criticalLine = 2_000_000): int =
+  # List of all beacons
+  var beacons: HashSet[Point]
+  for entry in entries:
+    beacons.incl(entry.beacon)
+
+  let empty = emptyRanges(entries, criticalLine)
+  for r in empty:
+    result += r.l
+    for b in beacons:
+      if r.rangeContains(criticalLine, b):
+        result -= 1
+
+proc part2(entries: seq[Entry], criticalLength = 4_000_000): int =
+  for y in 0 .. criticalLength:
+    let empty = emptyRanges(entries, y)
+    if empty.len() == 2:
+      let x = empty[0].b + empty[0].l
+      return x * 4_000_000 + y
+
+let content = readFile("./input.txt")
+let entries = parseFile(content)
+
+echo part1(entries)
+echo part2(entries)