2019 day10 part2

1 files changed, 95 insertions, 11 deletions

diff --git a/src/2019/day10/aoc.cpp b/src/2019/day10/aoc.cpp
index fbcb049..60de3ea 100644
--- a/src/2019/day10/aoc.cpp
+++ b/src/2019/day10/aoc.cpp
@@ -1,8 +1,72 @@
 #include "aoc.h"
 #include <algorithm>
+#include <vector>
 
 namespace aoc2019 {
 
+struct posd {
+  belt::pos p;
+  belt::distance d;
+  int count = 0;
+};
+
+enum dim {
+  xe0yl0,
+  xg0yl0,
+  xg0ye0,
+  xg0yg0,
+  xe0yg0,
+  xl0yg0,
+  xl0ye0,
+  xl0yl0
+};
+
+dim dimention(belt::distance d) {
+  if (d.dx == 0 && d.dy < 0) return xe0yl0;
+  if (d.dx > 0 && d.dy < 0) return xg0yl0;
+  if (d.dx > 0 && d.dy == 0) return xg0ye0;
+  if (d.dx > 0 && d.dy > 0) return xg0yg0;
+  if (d.dx == 0 && d.dy > 0) return xe0yg0;
+  if (d.dx < 0 && d.dy > 0) return xl0yg0;
+  if (d.dx < 0 && d.dy == 0) return xl0ye0;
+  return xl0yl0;
+}
+
+bool dimcmp(dim m, belt::distance d1, belt::distance d2) {
+  int x1 = std::abs(d1.dx);
+  int y1 = std::abs(d1.dy);
+  int x2 = std::abs(d2.dx);
+  int y2 = std::abs(d2.dy);
+
+  switch (m) {
+    case xe0yl0: return y1 < y2;
+    case xg0yl0: return y1 > y2 ? true : y1 < y2 ? false : x1 < x2;
+    case xg0ye0: return x1 < x2;
+    case xg0yg0: return y1 < y2 ? true : y1 > y2 ? false : x1 < x2;
+    case xe0yg0: return y1 < y2;
+    case xl0yg0: return y1 > y2 ? true : y1 < y2 ? false : x1 < x2;
+    case xl0ye0: return x1 < x2;
+    case xl0yl0: return y1 < y2 ? true : y1 > y2 ? false : x1 < x2;
+  }
+  return false;
+}
+
+belt::pos vaporize(belt b, belt::pos& m, std::vector<posd>& ps, int* count) {
+  belt bx = b;
+  for (auto& dp : ps) {
+    if (dp.count == 0 && !bx.blocked(dp.p, m)) {
+      dp.count = 1;
+      b.get(dp.p) = '.';
+      *count += 1;
+      printf("%d asteroid to be vaporized is at (%d, %d)\n", *count, dp.p.x, dp.p.y);
+      if (*count == 200) {
+        return dp.p;
+      }
+    }
+  }
+  return vaporize(b, m, ps, count);
+}
+
 std::pair<int, int> day10(line_view file) {
   belt b;
   int r{0};
@@ -11,22 +75,42 @@ std::pair<int, int> day10(line_view file) {
     return true;
   });
 
-  // b.print();
+  std::vector<posd> ps;
+  b.iterate([&ps, &b](belt::pos p){
+    if (b.get(p) == '#') {
+      posd d;
+      d.p = p;
+      b.count(p, &d.count);
+      ps.push_back(d);
+    }
+  });
+
+  std::sort(ps.begin(), ps.end(), [](const posd& d1, const posd& d2){
+      return d1.count > d2.count;
+  });
 
-  int observe{0};
-  int max{0};
+  int max = ps[0].count;
+  belt::pos monitor = ps[0].p;
 
-  b.iterate([&observe, &max, &b](belt::pos p){
-    if (b.get(p) == '#') {
-      observe = 0;
-      b.count(p, &observe);
-      if (observe > max) {
-        max = observe;
+  for (auto& a : ps) {
+    a.d = b.dist(a.p, monitor);
+    a.count = a.p == monitor ? 1 : 0; // mark as not lazered
+  }
+
+  std::sort(ps.begin(), ps.end(), [](const posd& d1, const posd& d2) {
+      dim m1 = dimention(d1.d);
+      dim m2 = dimention(d2.d);
+      if (m1 == m2) {
+        return dimcmp(m1, d1.d, d2.d);
+      }
+      else {
+        return (int) m1 < (int) m2;
       }
-    }
   });
 
-  return {max, 0};
+  int count{0};
+  belt::pos xp = vaporize(b, monitor, ps, &count);
+  return {max, xp.x * 100 + xp.y};
 }
 
 } // namespace aoc2019