2 files changed, 80 insertions, 27 deletions

diff --git a/src/2022/day15/aoc.cpp b/src/2022/day15/aoc.cpp
index 09a923f..1314b8d 100644
--- a/src/2022/day15/aoc.cpp
+++ b/src/2022/day15/aoc.cpp
@@ -5,42 +5,84 @@ namespace aoc2022 {
 int sensor::minx;
 int sensor::maxx;
 
+typedef sensor::pos pos;
+typedef sensor::line line;
 
 int no_beacon(int y, std::vector<sensor>& ss) {
-  int count{0};
-  for (int x = sensor::minx; x <= sensor::maxx; x++) {
-    sensor::pos p;
-    p.x = x;
-    p.y = y;
-    size_t n{0};
-    for (auto&s : ss) {
-      if(s.inscope(p)) {
-        n++;
-      }
+  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));
     }
-    // printf("(%d, %d) has %zu\n", x, y, n);
-    count += (bool) n > 0;
   }
-  return count;
-}
 
-bool valid(sensor::pos p, int dx) {
-  return p.x >= 0 && p.x <= dx && p.y >= 0 && p.y <= dx;
+  for (auto& l : ls) {
+    int x0 = l.p0.x - sensor::minx;
+    int x1 = l.p1.x - sensor::minx;
+    memset(p + x0, 1, x1 - x0);
+  }
+
+  int ones{0};
+  for (int i = 0; i < total; i++) {
+      ones += (int) *(p + i) == 1;
+  }
+
+  free(p);
+  return ones;
 }
 
-int only_beacon(int dx, std::vector<sensor>& ss) {
-  return 0;
+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);
+
+  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));
+    }
+  }
+
+  for (auto& l : ls) {
+    int x0 = l.p0.x - sensor::minx;
+    int x1 = l.p1.x - sensor::minx;
+    memset(p + x0, 1, x1 - x0);
+  }
+
+  for (int i = 0 - sensor::minx; i <= range - sensor::minx; i++) {
+     if (*(p + i) == 0) {
+       free(p);
+       return sensor::minx + i + 1;
+     }
+  }
+
+  free(p);
+  return range;
 }
 
 std::pair<int, int> day15(line_view file) {
   std::vector<sensor> ss;
-  per_line(file, [&ss](line_view lv){
-      ss.emplace_back(lv);
-      return true;
+  per_line(file, [&ss](line_view lv) {
+    ss.emplace_back(lv);
+    return true;
   });
-  int n1 = no_beacon(2000000, ss);
-  int n2 = only_beacon(4000000, ss);
-  return {n1, n2};
-}
+  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};
 }
 
+} // namespace aoc2022
diff --git a/src/2022/day15/aoc.h b/src/2022/day15/aoc.h
index ffb4183..eaed197 100644
--- a/src/2022/day15/aoc.h
+++ b/src/2022/day15/aoc.h
@@ -19,8 +19,9 @@ struct sensor {
     }
   };
 
-  struct triangle {
-    pos as[3];
+  struct line {
+    pos p0;
+    pos p1;
   };
 
   static int minx;
@@ -57,6 +58,16 @@ struct sensor {
     return d2 <= d1 && !(p == ps[1]);
   }
 
+  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};