2022 day24 part1

1 files changed, 62 insertions, 3 deletions

diff --git a/src/2022/day24/aoc.cpp b/src/2022/day24/aoc.cpp
index 80b233c..21e9d3e 100644
--- a/src/2022/day24/aoc.cpp
+++ b/src/2022/day24/aoc.cpp
@@ -5,14 +5,72 @@ namespace aoc2022 {
 struct pos {
   int x;
   int y;
+
+  bool operator==(pos p) const noexcept {
+    return x == p.x && y == p.y;
+  }
 };
 
-void expedition(int m, pos p, pos target, valley& v, int* max) {
+bool is_valid(pos p, const std::map<blizzard, int>&m, valley& v) {
+  auto b = p.x >= 0 && p.x < v.width && p.y >= 0 && p.y < v.height;
+  return b && m.find(blizzard{p.x, p.y, '.'}) == m.end() && v.get(p.y, p.x) == '.';
+}
+
+void expedition(int m, pos p, pos target, valley& v, int* min) {
+  if (*min < INT32_MAX && m >= *min) return;
+  if (p == target) {
+    printf("arrived by %d !!!\n", m);
+    if (*min > m) *min = m;
+  }
+  else {
+    v.next();
+    std::map<blizzard, int> mp; 
+    for (auto& b: v.blz) {
+      auto p = mp.insert({b, 1});
+      if (!p.second) {
+        p.first->second += 1;
+      }
+    }
+
+    pos mv0[2] = {
+      {p.x, p.y+1},
+      {p.x+1, p.y},
+    };
+    bool p0{false}, p1{false};
+    for (int i = 0; i < 2; i++) {
+      auto mv = mv0[i];
+      if (is_valid(mv, mp, v)) {
+        p0 = true;
+        auto blz = v.blz;
+        expedition(m + 1, mv, target, v, min);
+        v.blz = blz;
+      }
+    }
+
+    if (!p0) {
+      pos mv1[2] = {
+        {p.x, p.y-1},
+        {p.x-1, p.y},
+      };
+      for (int i = 0; i < 2; i++) {
+        auto mv = mv1[i];
+        if (is_valid(mv, mp, v)) {
+          p1 = true;
+          expedition(m + 1, mv, target, v, min);
+          break;
+        }
+      }
+    }
 
+    if (!p0 && !p1) {
+      expedition(m + 1, p, target, v, min);
+    }
+  }
 }
 
 std::pair<int, int> day24(line_view file) {
-  valley v{8,6}; //sample
+  // valley v{8,6}; //sample
+  valley v{152,22};
 
   int height{0};
   per_line(file, [&v, &height](line_view lv) {
@@ -21,7 +79,8 @@ std::pair<int, int> day24(line_view file) {
   });
 
   int min{INT32_MAX};
-  expedition(0, {1, 0}, {6, 5}, v, &min); // sample
+  // v.print();
+  expedition(0, {1, 0}, {150, 21}, v, &min);
 
   return {min, 0};
 }