2022 day24

3 files changed, 78 insertions, 53 deletions

diff --git a/src/2022/day24/README.md b/src/2022/day24/README.md
index 0945b97..2eb0716 100644
--- a/src/2022/day24/README.md
+++ b/src/2022/day24/README.md
@@ -229,3 +229,14 @@ Minute 18, move down:
 #<....>#
 ######E#
 What is the fewest number of minutes required to avoid the blizzards and reach the goal?
+
+--- Part Two ---
+As the expedition reaches the far side of the valley, one of the Elves looks especially dismayed:
+
+He forgot his snacks at the entrance to the valley!
+
+Since you're so good at dodging blizzards, the Elves humbly request that you go back for his snacks. From the same initial conditions, how quickly can you make it from the start to the goal, then back to the start, then back to the goal?
+
+In the above example, the first trip to the goal takes 18 minutes, the trip back to the start takes 23 minutes, and the trip back to the goal again takes 13 minutes, for a total time of 54 minutes.
+
+What is the fewest number of minutes required to reach the goal, go back to the start, then reach the goal again?
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};
 }
 }
 
diff --git a/src/2022/day24/aoc.h b/src/2022/day24/aoc.h
index 5102256..9724324 100644
--- a/src/2022/day24/aoc.h
+++ b/src/2022/day24/aoc.h
@@ -33,46 +33,44 @@ struct valley {
   int height;
 
   char* pixel;
-  int* dp;
-  std::vector<blizzard> blz;
+  std::vector<std::vector<blizzard>> blzs;
 
   valley(int w, int h): width(w), height(h) {
     pixel = (char*) malloc(width * height);
-    dp = (int*) malloc(width * height * sizeof(int));
-    for(int i = 0; i < width * height; i++) {
-      *(dp + i) = INT32_MAX;
-    }
+    blzs.resize(1);
   }
 
   char& get(int h, int w) {
     return *(pixel + h*width + w);
   }
 
-  int& get_time(int h, int w) {
-    return *(dp + h*width + w);
-  }
-
   void load(int h, line_view lv) {
     for(size_t i = 0; i < lv.length - 1; i++) {
       char c = *(lv.line + i);
       get(h, i) = c;
       if (c == '<' || c == '>' || c == '^' || c == 'v') {
         get(h, i) = '.';
-        blz.emplace_back(blizzard{(int) i, h, c});
+        blzs[0].emplace_back(blizzard{(int) i, h, c});
       }
     }
   }
 
-  void next() {
-    std::vector<blizzard> n{blz.size()};
-    for(size_t i = 0; i < blz.size(); i++) {
-      n[i] = blz[i].next(height, width);
+  std::vector<blizzard> at(int t) {
+    t %= width * height;
+    while (blzs.size() < (size_t) t + 1) {
+      auto l = blzs.size() - 1;
+      std::vector<blizzard> n = blzs[l];
+      for (size_t i = 0; i < n.size(); i++) {
+        n[i] = n[i].next(height, width);
+      }
+      blzs.push_back(n);
     }
-    blz = n;
+    return blzs[t];
   }
 
-  void print() {
+  void print(int t) {
     std::map<blizzard, int> m; 
+    auto& blz = blzs[t];
     for (auto& b: blz) {
       auto p = m.insert({b, 1});
       if (!p.second) {