day17 done

3 files changed, 89 insertions, 1 deletions

diff --git a/src/2015/day17/README.md b/src/2015/day17/README.md
index 4f6e878..9c61787 100644
--- a/src/2015/day17/README.md
+++ b/src/2015/day17/README.md
@@ -11,3 +11,10 @@ For example, suppose you have containers of size 20, 15, 10, 5, and 5 liters. If
 
 Filling all containers entirely, how many different combinations of containers can exactly fit all 150 liters of eggnog?
 
+--- Part Two ---
+
+While playing with all the containers in the kitchen, another load of eggnog arrives! The shipping and receiving department is requesting as many containers as you can spare.
+
+Find the minimum number of containers that can exactly fit all 150 liters of eggnog. How many different ways can you fill that number of containers and still hold exactly 150 litres?
+
+In the example above, the minimum number of containers was two. There were three ways to use that many containers, and so the answer there would be 3.
diff --git a/src/2015/day17/aoc.cpp b/src/2015/day17/aoc.cpp
index 1c33c66..c7a514b 100644
--- a/src/2015/day17/aoc.cpp
+++ b/src/2015/day17/aoc.cpp
@@ -2,4 +2,17 @@
 
 namespace aoc2015 {
 
+std::pair<size_t,size_t> day17(line_view file, int t) {
+  kichen ki;
+  per_line(file, [&ki](line_view lv) {
+    ki.parse(lv);
+    return true;
+  });
+  std::vector<int> c(ki.containers.size(),0);
+  std::vector<std::vector<int>> combo;
+  // std::for_each(ki.containers.begin(), ki.containers.end(), [](int i) { printf("%d\n", i); });
+  ki.fill(t, 0, c, combo);
+  return {combo.size(), ki.min(combo)};
 }
+
+} // namespace aoc2015
diff --git a/src/2015/day17/aoc.h b/src/2015/day17/aoc.h
index 7eb843c..a0dd1da 100644
--- a/src/2015/day17/aoc.h
+++ b/src/2015/day17/aoc.h
@@ -1,7 +1,75 @@
 #pragma once
 
 #include "common.h"
+#include <algorithm>
+#include <stack>
+#include <vector>
 
 namespace aoc2015 {
 
-}
+struct kichen {
+  std::vector<int> containers;
+
+  int get_number(const char* p) {
+    int d{0};
+    while ((*p) >= '0' && (*p) <= '9') {
+      d = d * 10 + *p - '0';
+      p++;
+    }
+    return d;
+  }
+
+  int count(const std::vector<int>& is) {
+    int d{0};
+    for (auto i : is) {
+      if (i > 0) {
+        d++;
+      }
+    }
+    return d;
+  }
+
+  void fill(int total, size_t index, std::vector<int>& c, std::vector<std::vector<int>>& combos) {
+    if (0 == total) {
+      // std::for_each(c.begin(), c.end(), [](int i) { printf("%02d ", i); });
+      // printf("\n");
+      combos.push_back(c);
+      return;
+    }
+    if (index < containers.size()) {
+      // printf("--> %d [%zu]%d?\n", total, index, containers[index]);
+      if (containers[index] > total) {
+        c[index] = 0;
+        fill(total, index + 1, c, combos);
+      } else {
+        for (int i = 0; i < 2; i++) {
+          int x = i == 0 ? containers[index] : 0;
+          c[index] = x;
+          fill(total - x, index + 1, c, combos);
+        }
+      }
+    }
+  }
+
+  size_t min(const std::vector<std::vector<int>>& combos) {
+    std::stack<int> is;
+    for (auto& c : combos) {
+      int x = count(c);
+      if (is.empty() || x == is.top()) {
+        is.push(x);
+      } else if (x < is.top()) {
+        while (!is.empty()) {
+          is.pop();
+        }
+        is.push(x);
+      }
+    }
+    return is.size();
+  }
+
+  void parse(line_view lv) { containers.push_back(get_number(lv.line)); }
+};
+
+std::pair<size_t, size_t> day17(line_view, int);
+
+} // namespace aoc2015