2022 day19 part1 dfs

1 files changed, 47 insertions, 61 deletions

diff --git a/src/2022/day19/aoc.cpp b/src/2022/day19/aoc.cpp
index 7ccac05..4260374 100644
--- a/src/2022/day19/aoc.cpp
+++ b/src/2022/day19/aoc.cpp
@@ -1,4 +1,5 @@
 #include "aoc.h"
+#include <map>
 #include <set>
 
 namespace aoc2022 {
@@ -10,50 +11,17 @@ struct build_result {
 };
 
 void print_result(int i, int m, const build_result& r) {
-  printf("%d %02d| ore[%d] clay[%d] obsi[%d] geod[%d]\n", i, m, r.products[0], r.products[1], r.products[2],
-         r.products[3]);
-  printf("%d %02d| robots: %d %d %d %d\n", i, m, r.robots[0], r.robots[1], r.robots[2], r.robots[3]);
-}
-
-bool can_build(int i, const build_result& r, const blueprint& b) {
-  switch (i) {
-  case 0:
-    return r.products[0] >= b.c_ore_r[0];
-  case 1:
-    return r.products[0] >= b.c_clay_r[0];
-  case 2:
-    return r.products[0] >= b.c_obsi_r[0] && r.products[1] >= b.c_obsi_r[1];
-  case 3:
-    return r.products[0] >= b.c_geod_r[0] && r.products[2] >= b.c_geod_r[1];
-  default:
-    break;
-  }
-  return false;
+  printf("%d %02d| ms: %d %d %d %d | rs: %d %d %d %d\n", i, m, r.products[0], r.products[1], r.products[2],
+         r.products[3], r.robots[0], r.robots[1], r.robots[2], r.robots[3]);
 }
 
 build_result build_robot(int i, build_result r, const blueprint& b) {
-  switch (i) {
-  case 0:
-    r.products[0] -= b.c_ore_r[0];
-    r.robots[0] += 1;
-    break;
-  case 1:
-    r.products[0] -= b.c_clay_r[0];
-    r.robots[1] += 1;
-    break;
-  case 2:
-    r.products[0] -= b.c_obsi_r[0];
-    r.products[1] -= b.c_obsi_r[1];
-    r.robots[2] += 1;
-    break;
-  case 3:
-    r.products[0] -= b.c_geod_r[0];
-    r.products[2] -= b.c_geod_r[1];
-    r.robots[3] += 1;
-    break;
-  default:
-    break;
+  const int* bs[4] = {b.c_ore_r, b.c_clay_r, b.c_obsi_r, b.c_geod_r};
+  r.products[0] -= bs[i][0];
+  if (i > 0) {
+    r.products[i - 1] -= bs[i][1];
   }
+  r.robots[i] += 1;
   return r;
 }
 
@@ -63,38 +31,56 @@ void build_product(build_result& r, int x) {
   }
 }
 
-int required(const blueprint& b, int i) {
-  switch (i) {
-  case 0:
-    return 0;
-  case 1:
-    return 0;
-  case 2:
-    return b.c_obsi_r[1];
-  case 3:
-    return b.c_geod_r[1];
-  default:
-    break;
+struct diff {
+  int d0 = 0;
+  int d1 = 0;
+
+  diff(int i0, int i1) : d0(i0), d1(i1) {}
+};
+
+diff required(const blueprint& b, const build_result& r, int i) {
+  const int* bs[4] = {b.c_ore_r, b.c_clay_r, b.c_obsi_r, b.c_geod_r};
+  diff d = {r.products[0] - bs[i][0], 0};
+  if (i > 0) {
+    d.d1 = r.products[i - 1] - bs[i][1];
   }
-  return 0;
+  return d;
+}
+
+bool can_build(const blueprint& b, const build_result& r, int i) {
+  diff d = required(b, r, i);
+  return d.d0 >= 0 && d.d1 >= 0;
 }
 
 std::set<int> to_build(const blueprint& b, const build_result& r) {
-  int need{3}; // 0, 1, 2, 3
-  while (need > 0) {
-    auto c = can_build(need, r, b);
-    if (c || (r.products[need - 1] >= required(b, need))) {
+  std::set<int> is;
+  for (int i = 3; i >= 0; i--) {
+    if (can_build(b, r, i)) {
+      is.insert(i);
       break;
+    } else {
+      is.insert(INT32_MAX);
     }
-    need--;
   }
-  // printf("need %d\n", need);
-  return can_build(need, r, b) ? std::set<int>{need} : std::set<int>{INT32_MAX};
+  return is;
 }
 
+struct p4 {
+  int products[4] = {-1, -1, -1, -1};
+
+  p4(int ps[4]) {
+    for (int i = 0; i < 4; i++) {
+      products[i] = ps[i];
+    }
+  }
+  p4() {}
+
+  int at(int i) const noexcept { return products[i]; }
+};
+
 void build(int m, const blueprint& b, build_result r, build_result& max) {
+  print_result(b.idx, 24 - m, r);
   if (m > 0) {
-    // print_result(b.idx, 24 - m, r);
     auto is = to_build(b, r);
     for (auto i : is) {
       if (i != INT32_MAX) {