2016 day11 bfs ??

1 files changed, 23 insertions, 9 deletions

diff --git a/src/2016/day11/aoc.cpp b/src/2016/day11/aoc.cpp
index 9a45063..ffd2fbe 100644
--- a/src/2016/day11/aoc.cpp
+++ b/src/2016/day11/aoc.cpp
@@ -1,4 +1,5 @@
 #include "aoc.h"
+#include <deque>
 
 // F4 . .  .  .  .  .  .  .  .  .  .
 // F3 . .  .  .  .  .  .  HG HM RG RM
@@ -76,6 +77,7 @@ bool any_at(const std::vector<ritem>& rs, int f) {
 
 bool empty(const std::vector<ritem>& rs, int f) { return !any_at(rs, f); }
 
+// bfs ???
 // goal is to get every ritem in rs with value (4,4)
 // 1. in every step, modify fs[0] or fs[1] in each ritem
 // 2. at minimal 1 must be modified, at most, 2 can be modified
@@ -88,22 +90,34 @@ bool empty(const std::vector<ritem>& rs, int f) { return !any_at(rs, f); }
 //    5.2 or empty == next_floor(fs[0])
 // 6. either modify fs[0] and fs[1] of the same ritem
 //    or modify two fs[0] or two fs[1]
-void move_ritem(int step, int floor, std::vector<ritem>& rs, int* min) {
-  if (all_at(rs, 4)) {
-    if (*min > step) {
-      *min = step;
+// 7. GGM is ok, GMM is not
+int move_ritem(int floor, const std::vector<ritem>& r) {
+  int step = 0;
+  std::deque<std::vector<ritem>> q;
+  q.push_back(r);
+
+  while (!q.empty()) {
+    auto s = q.size();
+    while (s-- > 0) {
+      auto r0 = q.front();
+      q.pop_front();
+
+      if (all_at(r0, 4)) {
+        return step;
+      } else {
+        // push to q every other next possible state of r0
+      }
     }
-  } else {
-    // int nf = next_floor(floor);
+    step++;
   }
+  return INT32_MAX;
 }
 
 std::pair<int64_t, int64_t> day11(line_view) {
   std::vector<ritem> rs;
   setup_demo(rs);
 
-  int min{INT32_MAX};
-  move_ritem(0, 1, rs, &min);
-  return {0, 0};
+  int min = move_ritem(1, rs);
+  return {min, 0};
 }
 } // namespace aoc2016