2015 day24 dfs

1 files changed, 52 insertions, 5 deletions

diff --git a/src/2015/day24/aoc.cpp b/src/2015/day24/aoc.cpp
index 344660f..b92f8ee 100644
--- a/src/2015/day24/aoc.cpp
+++ b/src/2015/day24/aoc.cpp
@@ -1,24 +1,71 @@
 #include "aoc.h"
+#include <algorithm>
+#include <set>
 #include <vector>
 
 namespace aoc2015 {
 
 static int get_number(const char* p) {
   int d{0};
-  while(*p >= '0' && *p <= '9') {
+  while (*p >= '0' && *p <= '9') {
     d = d * 10 + *p - '0';
     p++;
   }
   return d;
 }
 
+int64_t quantum_entanglement(const std::set<int>& si) {
+  int64_t qe{1};
+  for (auto i : si) {
+    qe *= i;
+  }
+  return qe;
+}
+
+void find(int x, std::set<int> selected, const std::vector<int>& ns, int target, size_t* min, std::set<int64_t>& qes) {
+  if (x == target && *min >= selected.size()) {
+    if (*min > selected.size()) {
+      *min = selected.size();
+      qes.clear();
+      qes.insert(quantum_entanglement(selected));
+    } else {
+      qes.insert(quantum_entanglement(selected));
+    }
+  } else {
+    if (*min != INT32_MAX && selected.size() > *min)
+      return;
+
+    for (size_t i = 0; i < ns.size(); i++) {
+      auto n = ns[i];
+      if (n + x <= target && selected.find(n) == selected.end()) {
+        selected.insert(n);
+        find(n + x, selected, ns, target, min, qes);
+        selected.erase(n);
+      }
+    }
+  }
+}
+
 std::pair<int, int> day24(line_view file) {
   int total{0};
-  per_line(file,[&total](line_view lv){
-      total += get_number(lv.line);
-      return true;
+  std::vector<int> ns;
+  per_line(file, [&total, &ns](line_view lv) {
+    auto i = get_number(lv.line);
+    total += i;
+    ns.push_back(i);
+    return true;
   });
+  std::sort(ns.begin(), ns.end(), [](int i1, int i2) { return i1 > i2; });
+  std::set<int> selected;
+  std::set<int64_t> qes;
+  size_t min{INT32_MAX};
+  printf("total is %d\n", total);
+  find(0, selected, ns, total / 3, &min, qes);
+
+  for (auto& qe : qes) {
+    printf("%ld\n", qe);
+  }
   return {0, 0};
 }
 
-}
+} // namespace aoc2015