2022 day12 part1

2 files changed, 41 insertions, 6 deletions

diff --git a/src/2022/day12/aoc.cpp b/src/2022/day12/aoc.cpp
index c0d1db5..7b79e94 100644
--- a/src/2022/day12/aoc.cpp
+++ b/src/2022/day12/aoc.cpp
@@ -11,13 +11,14 @@ std::pair<int, int> day12(line_view file) {
       return true;
   });
 
-  hm.print();
-  std::vector<int> paths;
-  hm.was(hm.start) += 1;
-  hm.find(0, hm.start, paths);
+  // hm.print();
+  std::vector<heightmap::pos> ps;
+  hm.find_prev(0, hm.end, ps);
 
-  std::sort(paths.begin(), paths.end());
-  return {paths[0], 0};
+  for (auto &p : ps) {
+    printf("%d %d\n", p.x, p.y);
+  }
+  return {0, 0};
 }
 
 }
diff --git a/src/2022/day12/aoc.h b/src/2022/day12/aoc.h
index a771bfc..3ac0c76 100644
--- a/src/2022/day12/aoc.h
+++ b/src/2022/day12/aoc.h
@@ -56,6 +56,25 @@ struct heightmap {
     }
   }
 
+  void get_prev(pos p, pos prev[], int* n) {
+    pos ps[] = {
+      {p.x, p.y - 1}, // UP
+      {p.x, p.y + 1}, // DOWN
+      {p.x - 1, p.y}, // LEFT
+      {p.x + 1, p.y}, // RIGHT
+    };
+    for (int i = 0; i < 4; i++) {
+      if (valid(ps[i])) {
+        bool b1 = get(ps[i]) == get(p) - 1;
+        bool b2 = get(ps[i]) == get(p);
+        if (b1 || b2) {
+          prev[*n] = ps[i];
+          *n += 1;
+        }
+      }
+    }
+  }
+
   char * indent (int s) {
      static char space[100] = {0};
      memset(space, 0 ,100);
@@ -65,6 +84,21 @@ struct heightmap {
      return space;
   };
 
+  void find_prev(int steps, pos p, std::vector<pos>& as) {
+    // printf("%s (%d,%d) %c\n", indent(steps), p.x, p.y, get(p));
+    if (get(p) == 'a') {
+      as.push_back(p);
+    }
+    else {
+      pos prev[4];
+      int n = 0;
+      get_prev(p, prev, &n);
+      for (int i = 0; i < n; i++) {
+        find_prev(steps + 1, prev[i], as);
+      }
+    }
+  }
+
   void find(int steps, pos p, std::vector<int>& paths) {
     // printf("%s (%d,%d) %c\n", indent(steps), p.x, p.y, get(p));
     if (p == end) {