2019 day3

2 files changed, 67 insertions, 21 deletions

diff --git a/src/2019/day3/aoc.cpp b/src/2019/day3/aoc.cpp
index 967863a..b711991 100644
--- a/src/2019/day3/aoc.cpp
+++ b/src/2019/day3/aoc.cpp
@@ -35,22 +35,71 @@ int match_closest(wire ws[]) {
   match(ws[0].psh, ws[1].psv, &p1);
   match(ws[1].psh, ws[0].psv, &p2);
   day3point p = std::min(p1, p2);
-  return p.distance() ;
+  return p.distance();
+}
+
+int distance(const wire::line& l, day3point p) { return l.a.x == p.x ? std::abs(p.y - l.a.y) : std::abs(p.x - l.a.x); }
+int distance(const wire::line& l, wire::line* ls) {
+  int total{0};
+  int i{0};
+  while (ls[i].id != l.id) {
+    total += ls[i++].length;
+  }
+  return total;
+}
+
+void match(int i, wire::line* ls1, wire::line* ls2, int* shorest, int max) {
+  if (i < max) {
+    for (int j = 1; j < max; j += 2) {
+      day3point p;
+      if (cross(ls1[i], ls2[j], &p)) {
+        int s1 = distance(ls1[i], p) + distance(ls1[i], ls1);
+        int s2 = distance(ls2[j], p) + distance(ls2[j], ls2);
+        if (s1 + s2 < *shorest) {
+          *shorest = s1 + s2;
+        }
+      }
+    }
+    match(i + 2, ls1, ls2, shorest, max);
+  }
+}
+
+bool match(wire::line* ls1, wire::line* ls2, size_t n) {
+  day3point p1;
+  day3point p2;
+  if (cross(ls1[n - 1], ls2[n], &p1)) {
+    return true;
+  }
+  if (cross(ls2[n - 1], ls1[n], &p2)) {
+    return true;
+  }
+  return false;
 }
 
 int match_earliest(wire ws[]) {
-  return 0;
+  size_t n = 1;
+  while (n < ws[0].ps.size() && n < ws[1].ps.size()) {
+    if (match(ws[0].ps.data(), ws[1].ps.data(), n)) {
+      break;
+    }
+    n += 1;
+  }
+  int shorest{INT32_MAX};
+  match(0, ws[0].ps.data(), ws[1].ps.data(), &shorest, n + 1);
+  match(0, ws[1].ps.data(), ws[0].ps.data(), &shorest, n + 1);
+  // printf("%d\n", shorest);
+  return shorest;
 }
 
 std::pair<int, int> day3(line_view file) {
   wire ws[2];
-  day3point mp{0, 0};
   int i{0};
-  per_line(file, [&ws, &mp, &i](line_view lv) {
+  per_line(file, [&ws, &i](line_view lv) {
     day3point cp{0, 0};
-    ws[i++].parse(lv, &cp, &mp);
+    ws[i++].parse(lv, &cp);
     return true;
   });
+  // printf("%zu %zu\n", ws[0].ps.size(), ws[1].ps.size());
   return {match_earliest(ws), match_closest(ws)};
 }
 
diff --git a/src/2019/day3/aoc.h b/src/2019/day3/aoc.h
index 41be5ed..abd0c54 100644
--- a/src/2019/day3/aoc.h
+++ b/src/2019/day3/aoc.h
@@ -35,12 +35,16 @@ struct wire {
   }
 
   struct line {
+    int id;
+    line_view label;
     day3point a;
     day3point b;
+    int length;
   };
 
   std::vector<line> psh;
   std::vector<line> psv;
+  std::vector<line> ps;
 
   void sort() {
     std::sort(psh.begin(), psh.end(),
@@ -59,30 +63,23 @@ struct wire {
     *pp = p;
   }
 
-  void largest(day3point* cp, day3point* mp) {
-    if (std::abs(cp->x) > std::abs(mp->x)) {
-      mp->x = cp->x;
-    }
-    if (std::abs(cp->y) > std::abs(mp->y)) {
-      mp->y = cp->y;
-    }
-  }
-
-  void parse(line_view lv, day3point* cp, day3point* mp) {
+  void parse(line_view lv, day3point* cp) {
     part p;
     const char* p1 = lv.line;
-    auto make_part = [&p, &p1, cp, mp, this](part::dir_t d) {
+    int i{0};
+    auto make_part = [&i, &p, &p1, cp, this](part::dir_t d) {
       p.dir = d;
+      const char* p0 = p1;
       get_part(&p1, &p.distance);
       day3point a = *cp;
       *cp = mov(*cp, p);
-      // printf("%d, %d\n", cp->x, cp->y);
-      largest(cp, mp);
+      line l{i++, {p0, p1}, a, *cp, p.distance};
+      ps.push_back(l);
       if (d == part::right || d == part::left) {
-        psh.push_back({a, *cp});
+        psh.push_back(l);
       }
       if (d == part::up || d == part::down) {
-        psv.push_back({a, *cp});
+        psv.push_back(l);
       }
     };
     while (p1 < lv.line + lv.length) {
@@ -107,6 +104,6 @@ struct wire {
   }
 };
 
-std::pair<int,int> day3(line_view);
+std::pair<int, int> day3(line_view);
 
 } // namespace aoc2019