2022 day15 part1

1 files changed, 68 insertions, 55 deletions

diff --git a/src/2022/day15/aoc.cpp b/src/2022/day15/aoc.cpp
index 1314b8d..0196a11 100644
--- a/src/2022/day15/aoc.cpp
+++ b/src/2022/day15/aoc.cpp
@@ -1,5 +1,5 @@
 #include "aoc.h"
-#include <set>
+#include <algorithm>
 
 namespace aoc2022 {
 int sensor::minx;
@@ -8,61 +8,81 @@ int sensor::maxx;
 typedef sensor::pos pos;
 typedef sensor::line line;
 
-int no_beacon(int y, std::vector<sensor>& ss) {
-  int total = sensor::maxx - sensor::minx + 1;
-  char * p = (char *) malloc(total);
-  memset(p, 0, total);
-  std::vector<line> ls;
-  for (auto& s : ss) {
-    int dy = y - s.ps[0].y;
-    if (sensor::mdistance(s.ps[0], s.ps[1]) >= std::abs(dy)) {
-      ls.push_back(s.line_by_dy(dy));
+static std::vector<line> merge(const std::vector<line>& ls) {
+  std::vector<line> merged;
+  if (ls.empty())
+    return merged;
+
+  merged.push_back(ls[0]);
+  for (size_t i = 1; i < ls.size(); i++) {
+    line& last = merged[merged.size() - 1];
+    if (last.p1.x >= ls[i].p0.x) {
+      last.p1.x = ls[i].p1.x;
+    } else {
+      merged.push_back(ls[i]);
     }
   }
+  return merged;
+}
 
+static int count(const std::vector<line>& ls) {
+  int total{0};
   for (auto& l : ls) {
-    int x0 = l.p0.x - sensor::minx;
-    int x1 = l.p1.x - sensor::minx;
-    memset(p + x0, 1, x1 - x0);
+    total += l.p1.x - l.p0.x + 1;
   }
-
-  int ones{0};
-  for (int i = 0; i < total; i++) {
-      ones += (int) *(p + i) == 1;
-  }
-
-  free(p);
-  return ones;
+  return total;
 }
 
-int one_beacon(int y, int range, std::vector<sensor>& ss) {
-  int total = sensor::maxx - sensor::minx + 1;
-  char * p = (char *) malloc(total);
-  memset(p, 0, total);
-
+int no_beacon(int y, std::vector<sensor>& ss) {
   std::vector<line> ls;
-  for (auto& s : ss) {
-    int dy = y - s.ps[0].y;
-    if (sensor::mdistance(s.ps[0], s.ps[1]) >= std::abs(dy)) {
-      ls.push_back(s.line_by_dy(dy));
+  int x = sensor::minx;
+  while (x <= sensor::maxx) {
+    pos p{x, y};
+    for (auto& s : ss) {
+      if (s.inscope(p)) {
+        int d = sensor::mdistance(s.ps[0], s.ps[1]);
+        int dy = y - s.ps[0].y;
+        auto x0 = x + 2 * (d - std::abs(dy));
+        if (p == s.ps[1]) {
+          ls.push_back({{x + 1, y}, {x0, y}});
+        } else {
+          ls.push_back({{x, y}, {x0, y}});
+        }
+        x = x0;
+        break;
+      }
     }
+    x++;
   }
 
-  for (auto& l : ls) {
-    int x0 = l.p0.x - sensor::minx;
-    int x1 = l.p1.x - sensor::minx;
-    memset(p + x0, 1, x1 - x0);
-  }
+  std::sort(ls.begin(), ls.end());
+  return count(merge(ls));
+}
 
-  for (int i = 0 - sensor::minx; i <= range - sensor::minx; i++) {
-     if (*(p + i) == 0) {
-       free(p);
-       return sensor::minx + i + 1;
-     }
+size_t one_beacon(int range, std::vector<sensor>& ss) {
+  for (int y = 0; y <= range; y++) {
+    std::vector<line> ls;
+    int x = 0;
+    while (x <= range) {
+      pos p{x, y};
+      for (auto& s : ss) {
+        if (s.inscope(p)) {
+          int d = sensor::mdistance(s.ps[0], s.ps[1]);
+          int dy = y - s.ps[0].y;
+          ls.push_back(s.line_by_dy(dy));
+          x += 2 * (d - std::abs(dy));
+          break;
+        }
+      }
+      x++;
+    }
+    std::sort(ls.begin(), ls.end());
+    auto m = merge(ls);
+    if (m.size() > 1) {
+      printf("%d, %d\n", m[0].p1.x + 1, y);
+    }
   }
-
-  free(p);
-  return range;
+  return 0;
 }
 
 std::pair<int, int> day15(line_view file) {
@@ -71,18 +91,11 @@ std::pair<int, int> day15(line_view file) {
     ss.emplace_back(lv);
     return true;
   });
-  auto n = no_beacon(2000000, ss);
-
-  // int total = 4000000;
-  // for (int y = 0; y <= total; y++) {
-  //   int x = one_beacon(y, total, ss);
-  //   if (x != total) {
-  //     printf("%d %d\n", x, y);
-  //     break;
-  //   }
-  // }
-
-  return {n, 0};
+  std::sort(ss.begin(), ss.end());
+  auto n1 = no_beacon(2000000, ss);
+  // auto n2 = one_beacon(4000000, ss);
+  auto n2 = one_beacon(20, ss);
+  return {n1, n2};
 }
 
 } // namespace aoc2022