2022 day24

1 files changed, 52 insertions, 36 deletions

diff --git a/src/2022/day24/aoc.cpp b/src/2022/day24/aoc.cpp
index 52f90e0..1e55468 100644
--- a/src/2022/day24/aoc.cpp
+++ b/src/2022/day24/aoc.cpp
@@ -1,59 +1,71 @@
 #include "aoc.h"
+#include <set>
+#include <deque>
 
 namespace aoc2022 {
 
 struct pos {
   int x;
   int y;
+  int t;
 
+  friend bool operator<(pos p1, pos p2) {
+    return p1.x < p2.x ? true : p1.x > p2.x ? false : p1.y < p2.y ? true : p1.y > p2.y ? false : p1.t < p2.t;
+  }
   bool operator==(pos p) const noexcept {
     return x == p.x && y == p.y;
   }
 };
 
-bool is_valid(pos p, const std::map<blizzard, int>&m, valley& v) {
+bool is_valid(pos p, valley& v, std::set<pos>& visited) {
+  pos px{p.x, p.y, p.t % (v.height * v.width)};
+
+  auto pr = visited.insert(px);
+  if (!pr.second) {
+    return false;
+  }
+
+  auto blz = v.at(px.t);
+  auto find = [&blz](blizzard b) -> bool {
+    for(auto& bx : blz) {
+      if (bx == b) return true;
+    }
+    return false;
+  };
+
   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) == '.';
+  return b && !find(blizzard{p.x, p.y, '.'}) && v.get(p.y, p.x) == '.';
 }
 
-void expedition(int m, pos p, pos target, valley& v, int* min, bool pass) {
-  if (*min < INT32_MAX && m > *min) return;
-  if (p == target) {
-    printf("arrived by %d !!!\n", m);
-    if (*min > m) *min = m;
-  }
-  else {
-    auto& t = v.get_time(p.y, p.x);
-    if (m < t || pass) {
-      // printf("(%d, %d) in %d, was %d\n", p.x, p.y, m, t);
+// bfs
+int expedition(pos p, pos target, valley& v, std::set<pos>& visited) {
+  std::deque<pos> q;
+  q.push_back(p);
 
-      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;
-        }
+  while(!q.empty()) {
+    auto size = q.size();
+    while (size-- > 0) {
+      pos px = q.front();
+      // printf("(%d,%d) at %d\n", px.x, px.y, px.t);
+      q.pop_front();
+      if (px == target) {
+        return px.t;
       }
-
-      pos mv0[5] = {
-        {p.x, p.y+1},
-        {p.x+1, p.y},
-        {p.x, p.y-1},
-        {p.x-1, p.y},
-        p,
+      pos ps[5] = {
+        {px.x, px.y+1, px.t + 1},
+        {px.x+1, px.y, px.t + 1},
+        {px.x, px.y-1, px.t + 1},
+        {px.x-1, px.y, px.t + 1},
+        {px.x, px.y, px.t + 1},
       };
       for (int i = 0; i < 5; i++) {
-        auto mv = mv0[i];
-        if (is_valid(mv, mp, v)) {
-          auto blz = v.blz;
-          t = m;
-          expedition(m + 1, mv, target, v, min, i > 1);
-          v.blz = blz;
+        if (is_valid(ps[i], v, visited)) {
+          q.push_back(ps[i]);
         }
       }
     }
   }
+  return INT32_MAX;
 }
 
 std::pair<int, int> day24(line_view file) {
@@ -65,12 +77,16 @@ std::pair<int, int> day24(line_view file) {
     v.load(height++, lv);
     return true;
   });
+  std::set<pos> visited;
 
-  int min{INT32_MAX};
-  // v.print();
-  expedition(0, {1, 0}, {150, 21}, v, &min, false);
+  int m1 = expedition({1, 0, 0}, {150, 21, INT32_MAX}, v, visited);
+  visited.clear();
+  int m2 = expedition({150, 21, m1}, {1, 0, INT32_MAX}, v, visited);
+  visited.clear();
+  int m3 = expedition({1, 0, m2}, {150, 21, INT32_MAX}, v, visited);
 
-  return {min, 0};
+  // printf("%d %d %d\n", m1, m2, m3);
+  return {m1, m3};
 }
 }