2022 day15 part2

2 files changed, 41 insertions, 34 deletions

diff --git a/src/2022/day15/aoc.cpp b/src/2022/day15/aoc.cpp
index 0196a11..52237dd 100644
--- a/src/2022/day15/aoc.cpp
+++ b/src/2022/day15/aoc.cpp
@@ -2,12 +2,13 @@
 #include <algorithm>
 
 namespace aoc2022 {
-int sensor::minx;
-int sensor::maxx;
-
 typedef sensor::pos pos;
 typedef sensor::line line;
 
+int sensor::minx;
+int sensor::maxx;
+std::set<pos> sensor::beacons;
+
 static std::vector<line> merge(const std::vector<line>& ls) {
   std::vector<line> merged;
   if (ls.empty())
@@ -16,7 +17,7 @@ static std::vector<line> merge(const std::vector<line>& ls) {
   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) {
+    if (last.p1.x + 1 >= ls[i].p0.x) {
       last.p1.x = ls[i].p1.x;
     } else {
       merged.push_back(ls[i]);
@@ -38,13 +39,17 @@ int no_beacon(int y, std::vector<sensor>& ss) {
   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));
+    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}});
         }
@@ -61,16 +66,28 @@ int no_beacon(int y, std::vector<sensor>& ss) {
 
 size_t one_beacon(int range, std::vector<sensor>& ss) {
   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 (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));
+      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;
         }
       }
@@ -79,7 +96,11 @@ size_t one_beacon(int range, std::vector<sensor>& ss) {
     std::sort(ls.begin(), ls.end());
     auto m = merge(ls);
     if (m.size() > 1) {
-      printf("%d, %d\n", m[0].p1.x + 1, y);
+      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;
+      }
     }
   }
   return 0;
@@ -93,8 +114,7 @@ std::pair<int, int> day15(line_view file) {
   });
   std::sort(ss.begin(), ss.end());
   auto n1 = no_beacon(2000000, ss);
-  // auto n2 = one_beacon(4000000, ss);
-  auto n2 = one_beacon(20, ss);
+  auto n2 = one_beacon(4000000, ss);
   return {n1, n2};
 }
 
diff --git a/src/2022/day15/aoc.h b/src/2022/day15/aoc.h
index b35c85b..87c3208 100644
--- a/src/2022/day15/aoc.h
+++ b/src/2022/day15/aoc.h
@@ -1,5 +1,6 @@
 #include "common.h"
 #include <vector>
+#include <set>
 
 namespace aoc2022 {
 
@@ -30,6 +31,7 @@ struct sensor {
 
   static int minx;
   static int maxx;
+  static std::set<pos> beacons;
 
   pos ps[2] = {{0,0},{0,0}};
 
@@ -56,22 +58,6 @@ struct sensor {
     printf("S(%d, %d) B(%d, %d)\n", ps[0].x, ps[0].y, ps[1].x, ps[1].y);
   }
 
-  bool inscope(pos p) {
-    auto d1 = mdistance(ps[0], ps[1]);
-    auto d2 = mdistance(ps[0], p);
-    return d2 <= d1;
-  }
-
-  line line_by_dy(int dy) {
-    int d = mdistance(ps[0], ps[1]);
-    int y = ps[0].y + dy; 
-    int dx = d - std::abs(dy);
-    int x = ps[0].x - dx;
-    pos p0 = {x, y};
-    pos p1 = {x + 2 * dx, y};
-    return {p0 , p1};
-  }
-
   sensor(line_view lv) {
     const char* p = lv.line;
     int *is[] = {&ps[0].x, &ps[0].y, &ps[1].x, &ps[1].y};
@@ -85,6 +71,7 @@ struct sensor {
       }
       p++;
     }
+    beacons.insert(ps[1]);
     auto x1 = ps[0].x - mdistance(ps[0], ps[1]);
     auto x2 = ps[0].x + mdistance(ps[0], ps[1]);
     if (minx > x1) minx = x1;