2022 day15 stay calm no panic

3 files changed, 65 insertions, 35 deletions

diff --git a/src/2022/day15/aoc.cpp b/src/2022/day15/aoc.cpp
index 52237dd..a86c92f 100644
--- a/src/2022/day15/aoc.cpp
+++ b/src/2022/day15/aoc.cpp
@@ -18,7 +18,7 @@ static std::vector<line> merge(const std::vector<line>& ls) {
   for (size_t i = 1; i < ls.size(); i++) {
     line& last = merged[merged.size() - 1];
     if (last.p1.x + 1 >= ls[i].p0.x) {
-      last.p1.x = ls[i].p1.x;
+      last.p1.x = std::max(last.p1.x, ls[i].p1.x);
     } else {
       merged.push_back(ls[i]);
     }
@@ -64,49 +64,65 @@ int no_beacon(int y, std::vector<sensor>& ss) {
   return count(merge(ls));
 }
 
+bool get_line(std::pair<int, std::vector<line>>& ls, int y, line* l) {
+  auto y0 = ls.first;
+  if (y >= y0 && y < y0 + (int)ls.second.size()) {
+    *l = ls.second[y - y0];
+    // printf("get %d: (%d-%d)\n", y, l->p0.x, l->p1.x);
+    return true;
+  }
+  return false;
+}
+
+bool check_range(int y, const std::vector<line>& ls, int range, size_t* d) {
+  line l{{0, y}, {range, y}};
+  for (size_t i = 0; i < ls.size() - 1; i++) {
+    auto l0 = ls[i];
+    auto l1 = ls[i + 1];
+    auto b1 = l.p0.x >= l0.p0.x && l.p0.x <= l0.p1.x;
+    auto b2 = l.p1.x >= l1.p0.x && l.p1.x <= l1.p1.x;
+    // printf("%d: checking (%d,%d) with (%d,%d) and (%d,%d)\n", y, 0, range, l0.p0.x, l0.p1.x, l1.p0.x, l1.p1.x);
+    if (b1 && b2) {
+      // printf("%d, %d\n", l0.p1.x + 1, y);
+      *d = ((size_t)l0.p1.x + 1) * range + y;
+      return true;
+    }
+  }
+  return false;
+}
+
+// static void print(const char* s, int y, const std::vector<line>& ls) {
+//   for (auto& l : ls) {
+//     printf("%s %d: (%d-%d)\n", s, y, l.p0.x, l.p1.x);
+//   }
+// }
+
 size_t one_beacon(int range, std::vector<sensor>& ss) {
+  std::vector<std::pair<int, std::vector<line>>> ps;
+  for (auto& s : ss) {
+    ps.emplace_back(s.lines());
+  }
+  size_t d{0};
   for (int y = 0; y <= range; y++) {
-    if (y % 10000 == 0) {
-      printf("%d\n", y);
-    }
     std::vector<line> ls;
-    int x = 0;
-    while (x <= range) {
-      pos p{x, y};
-      for (size_t i = 0; i < ss.size(); i++) {
-        auto& s = ss[i];
-        auto d1 = sensor::mdistance(s.ps[0], s.ps[1]);
-        auto d2 = sensor::mdistance(s.ps[0], p);
-        if (d2 <= d1) {
-          auto dy = s.ps[0].y - y;
-          auto x0 = s.ps[0].x + d2 - std::abs(dy);
-          if (p == s.ps[1]) {
-            ls.push_back({{x + 1, y}, {x0, y}});
-          } else if (pos{x0, y} == s.ps[1]) {
-            ls.push_back({{x, y}, {x0 - 1, y}});
-          } else {
-            ls.push_back({{x, y}, {x0, y}});
-          }
-          x = x0;
-          break;
-        }
+    for (auto& p : ps) {
+      line l;
+      if (get_line(p, y, &l)) {
+        ls.push_back(l);
       }
-      x++;
     }
     std::sort(ls.begin(), ls.end());
+    // print("after sort", y, ls);
     auto m = merge(ls);
-    if (m.size() > 1) {
-      pos p{m[0].p1.x+1, y};
-      if (sensor::beacons.find(p) == sensor::beacons.end()) {
-          printf("%d %d\n", m[0].p1.x+1, y);
-          return ((size_t) m[0].p1.x+1) * range + y;
-      }
+    // print("after merge", y, m);
+    if (check_range(y, m, range, &d)) {
+      return d;
     }
   }
-  return 0;
+  return d;
 }
 
-std::pair<int, int> day15(line_view file) {
+std::pair<int, size_t> day15(line_view file) {
   std::vector<sensor> ss;
   per_line(file, [&ss](line_view lv) {
     ss.emplace_back(lv);
diff --git a/src/2022/day15/aoc.h b/src/2022/day15/aoc.h
index 87c3208..7540490 100644
--- a/src/2022/day15/aoc.h
+++ b/src/2022/day15/aoc.h
@@ -24,6 +24,8 @@ struct sensor {
     pos p0;
     pos p1;
 
+    line() {}
+    line(pos x, pos y): p0(x), p1(y) {}
     friend bool operator<(const line& l1, const line& l2) {
       return l1.p0.x < l2.p0.x;
     }
@@ -39,6 +41,18 @@ struct sensor {
     return std::abs(p1.x - p2.x) + std::abs(p1.y - p2.y);
   }
 
+  std::pair<int, std::vector<line>> lines() const noexcept {
+    auto d = mdistance(ps[0], ps[1]);
+    std::vector<line> ls;
+    for(int y = ps[0].y - d; y <= ps[0].y + d; y++) {
+      auto dx = d - std::abs(ps[0].y - y);
+      pos p0 = {ps[0].x - dx, y};
+      pos p1 = {ps[0].x + dx, y};
+      ls.emplace_back(p0, p1);
+    }
+    return {ps[0].y - d,ls};
+  }
+
   void get_number(const char** pp, int* d) {
     const char *p = *pp;
     int sign = 1;
@@ -83,6 +97,6 @@ struct sensor {
   }
 };
 
-std::pair<int, int> day15(line_view);
+std::pair<int, size_t> day15(line_view);
 }
 
diff --git a/test/test_2022.cpp b/test/test_2022.cpp
index ba5ebef..65a645f 100644
--- a/test/test_2022.cpp
+++ b/test/test_2022.cpp
@@ -123,7 +123,7 @@ TEST_CASE("Beacon Exclusion Zone", "[2022]") {
   line_view lv = load_file("../src/2022/day15/input");
   auto p = aoc2022::day15(lv);
   REQUIRE(6078701 == p.first);
-  REQUIRE(0 == p.second);
+  REQUIRE(12567351400528 == p.second);
 }
 
 //TEST_CASE("Proboscidea Volcanium", "[2022]") {