2022 day9 part2

1 files changed, 182 insertions, 1 deletions

diff --git a/src/2022/day9/aoc.cpp b/src/2022/day9/aoc.cpp
index 8122f1e..2748141 100644
--- a/src/2022/day9/aoc.cpp
+++ b/src/2022/day9/aoc.cpp
@@ -1,8 +1,189 @@
 #include "aoc.h"
+#include <memory.h>
+#include <vector>
 
 namespace aoc2022 {
+
+struct Co {
+  int x;
+  int y;
+};
+
+struct Move {
+  char direction;
+  int steps = 0;
+
+  Move(char d, int s): direction(d), steps(s) {}
+  Move(line_view lv) {
+    const char *p = lv.line;
+    direction = p[0];
+    p += 2;
+    while(*p != '\n') {
+      steps = steps * 10 + *p - '0';
+      p++;
+    }
+  }
+};
+
+// U D L R
+Co next(Co c, Move m, int d4[]) {
+  Co n = c;
+  switch(m.direction) {
+    case 'U' : {
+       n.y = c.y - m.steps;
+       d4[0] = d4[0] > n.y ? n.y : d4[0];
+       break;
+    }
+    case 'D' : {
+       n.y = c.y + m.steps; 
+       d4[1] = d4[1] < n.y ? n.y : d4[1];
+       break;
+    }
+    case 'L' : {
+       n.x = c.x - m.steps; 
+       d4[2] = d4[2] > n.x ? n.x : d4[2];
+       break;
+    }
+    case 'R' : {
+       n.x = c.x + m.steps; 
+       d4[3] = d4[3] < n.x ? n.x : d4[3];
+       break;
+    }
+    default: break;
+  }
+  return n;
+}
+
+bool too_far(Co c1, Co c2) {
+  int y = std::abs(c2.y - c1.y);
+  int x = std::abs(c2.x - c1.x);
+  return y > 1 || x > 1;
+}
+
+struct arena {
+  int len;
+  char *n;
+  Co head;
+  Co tail;
+
+  Co tails[10];
+
+  arena(int m) {
+    len = m * 2 + 1;
+    n = (char *) malloc(len * len);
+    memset(n, 0, len * len);
+    
+    head.x = len / 2;
+    head.y = len / 2;
+    tail = head;
+
+    for (int i = 0; i < 10; i++) {
+      tails[i] = head;
+    }
+  }
+
+  char& get(Co c) {
+    return *(n + c.y * len + c.x);
+  }
+
+  void reset() {
+    memset(n, 0, len * len);
+  }
+
+  int moves() {
+    int m{0};
+    for (int i = 0; i < len*len; i++) {
+      m += (int) *(n+i) > 0;
+    }
+    return m;
+  }
+
+  void follow(Co& t, Co& h) {
+    int dy = h.y - t.y;
+    int dx = h.x - t.x;
+    printf("(%d,%d) -> (%d,%d) %d %d\n", t.x, t.y, h.x, h.y, dx, dy);
+    if (dy == 2) {
+      t.y += 1;
+      t.x += dx;
+    }
+
+    if (dy == -2) {
+      t.y -= 1;
+      t.x += dx;
+    }
+
+    if (dx == 2) {
+      t.x += 1;
+      t.y += dy;
+    }
+
+    if (dx == -2) {
+      t.x -= 1;
+      t.y += dy;
+    }
+  }
+
+  void travel(std::vector<Move>& ms) {
+    int d4[4] = {0};
+    for(auto& m: ms) {
+      for (int i = 0; i < m.steps; i++) {
+        Move mx{m.direction, 1};
+        head = next(head, mx, d4);
+        if (too_far(tail, head)) {
+          follow(tail, head);
+          get(tail) += 1;
+        }
+      } 
+    }
+  }
+
+  void travel_tails(std::vector<Move>& ms) {
+    int d4[4] = {0};
+    for(auto& m: ms) {
+      for (int i = 0; i < m.steps; i++) {
+        Move mx{m.direction, 1};
+        tails[0] = next(tails[0], mx, d4);
+        for (int j = 1; j <= 9; j++) {
+          if (too_far(tails[j], tails[j-1])) {
+            follow(tails[j], tails[j - 1]);
+            if (j == 9) {
+              get(tails[j]) += 1;
+            }
+          }
+        }
+      } 
+    }
+  }
+};
+
 std::pair<int,int> day9(line_view file) {
-  return {0, 0};
+  Co p{0, 0};
+  int d4[] = {0, 0, 0, 0};
+
+  std::vector<Move> ms;
+  per_line(file, [&p, &d4, &ms](line_view lv){
+    Move m{lv};
+    ms.push_back(m);
+    p = next(p, m, d4);
+    return true;
+  });
+
+  int max{0};
+  for (auto d: d4) {
+    if (max < std::abs(d)) {
+      max = d;
+    }
+  }
+
+  // printf("%d %d %d %d -> %d\n", d4[0], d4[1], d4[2], d4[3], max);
+  arena an(max);
+  an.travel(ms);
+  int m1 = an.moves();
+
+  an.reset();
+  an.travel_tails(ms);
+  int m2 = an.moves();
+  return {m1, m2};
 }
 
 }