day15 part1

6 files changed, 155 insertions, 3 deletions

diff --git a/src/2015/day14/aoc.h b/src/2015/day14/aoc.h
index 5772e99..7e773ff 100644
--- a/src/2015/day14/aoc.h
+++ b/src/2015/day14/aoc.h
@@ -81,9 +81,9 @@ struct olympics {
     for (int i = 1; i <= s; i++) {
       score(i);
     }
-    for (size_t i = 0; i < reindeers.size(); i++) {
-      std::cout << reindeers[i].name << ": " << points[i] << std::endl;
-    }
+    // for (size_t i = 0; i < reindeers.size(); i++) {
+    //   std::cout << reindeers[i].name << ": " << points[i] << std::endl;
+    // }
     int x = 0;
     for (size_t i = 1; i < points.size(); i++) {
       if (points[i] > points[x]) {
diff --git a/src/2015/day15/README.md b/src/2015/day15/README.md
new file mode 100644
index 0000000..86d6fa6
--- /dev/null
+++ b/src/2015/day15/README.md
@@ -0,0 +1,31 @@
+--- Day 15: Science for Hungry People ---
+
+Today, you set out on the task of perfecting your milk-dunking cookie recipe. All you have to do is find the right balance of ingredients.
+
+Your recipe leaves room for exactly 100 teaspoons of ingredients. You make a list of the remaining ingredients you could use to finish the recipe (your puzzle input) and their properties per teaspoon:
+
+    capacity (how well it helps the cookie absorb milk)
+    durability (how well it keeps the cookie intact when full of milk)
+    flavor (how tasty it makes the cookie)
+    texture (how it improves the feel of the cookie)
+    calories (how many calories it adds to the cookie)
+
+You can only measure ingredients in whole-teaspoon amounts accurately, and you have to be accurate so you can reproduce your results in the future. The total score of a cookie can be found by adding up each of the properties (negative totals become 0) and then multiplying together everything except calories.
+
+For instance, suppose you have these two ingredients:
+
+Butterscotch: capacity -1, durability -2, flavor 6, texture 3, calories 8
+Cinnamon: capacity 2, durability 3, flavor -2, texture -1, calories 3
+
+Then, choosing to use 44 teaspoons of butterscotch and 56 teaspoons of cinnamon (because the amounts of each ingredient must add up to 100) would result in a cookie with the following properties:
+
+    A capacity of 44*-1 + 56*2 = 68
+    A durability of 44*-2 + 56*3 = 80
+    A flavor of 44*6 + 56*-2 = 152
+    A texture of 44*3 + 56*-1 = 76
+
+Multiplying these together (68 * 80 * 152 * 76, ignoring calories for now) results in a total score of 62842880, which happens to be the best score possible given these ingredients. If any properties had produced a negative total, it would have instead become zero, causing the whole score to multiply to zero.
+
+Given the ingredients in your kitchen and their properties, what is the total score of the highest-scoring cookie you can make?
+
+
diff --git a/src/2015/day15/aoc.cpp b/src/2015/day15/aoc.cpp
new file mode 100644
index 0000000..ee6f864
--- /dev/null
+++ b/src/2015/day15/aoc.cpp
@@ -0,0 +1,17 @@
+#include "aoc.h"
+
+namespace aoc2015 {
+
+int day15(line_view file) {
+  recipe r;
+  per_line(file, [&r](line_view lv) {
+    r.parse(lv);
+    return true;
+  });
+
+  std::vector<int> combos;
+  int best{0};
+  r.measure(100, 0, combos, &best);
+  return best;
+}
+} // namespace aoc2015
diff --git a/src/2015/day15/aoc.h b/src/2015/day15/aoc.h
new file mode 100644
index 0000000..56a083e
--- /dev/null
+++ b/src/2015/day15/aoc.h
@@ -0,0 +1,99 @@
+#pragma once
+
+#include "common.h"
+#include <vector>
+
+namespace aoc2015 {
+
+struct ingredient {
+  line_view name;
+  int capacity;
+  int durability;
+  int flavor;
+  int texture;
+  int calories;
+
+  friend std::ostream& operator<<(std::ostream& o, const ingredient& i) {
+    o << i.name << " " << i.capacity << " " << i.durability << " " << i.flavor << " " << i.texture << " " << i.calories;
+    return o;
+  }
+};
+
+struct recipe {
+  std::vector<ingredient> ingredients;
+
+  int score(const std::vector<int>& is) {
+    int capacity = 0;
+    int durability = 0;
+    int flavor = 0;
+    int texture = 0;
+    for (size_t i = 0; i < ingredients.size(); i++) {
+      capacity += is[i] * ingredients[i].capacity;
+      durability += is[i] * ingredients[i].durability;
+      flavor += is[i] * ingredients[i].flavor;
+      texture += is[i] * ingredients[i].texture;
+    }
+    if (capacity < 0 || durability < 0 || flavor < 0 || texture < 0) {
+      return 0;
+    }
+    return capacity * durability * flavor * texture;
+  }
+
+  // backtrace
+  void measure(int total, size_t index, std::vector<int>& combos, int* best) {
+    if (index == ingredients.size() - 1) { // last ingredient
+      combos.push_back(total);
+      int s = score(combos);
+
+      // std::cout << "{" << s << " -> ";
+      // for (auto i : {0, 1, 2, 3}) {
+      //   std::cout << ingredients[i].name << ": " << combos[i] << " ";
+      // }
+      // std::cout << "}" << std::endl;
+
+      if (s > 0 && s > *best) {
+        *best = s;
+      }
+      combos.pop_back();
+      return;
+    }
+
+    for (int x = 1; x < total; x++) {
+      combos.push_back(x);
+      measure(total - x, index + 1, combos, best);
+      combos.pop_back();
+    }
+  }
+
+  int get_number(const char* p) {
+    int d{0};
+    int sign{1};
+    if (*p == '-') {
+      sign = -1;
+      p++;
+    }
+    while ((*p) >= '0' && (*p) <= '9') {
+      d = d * 10 + *p - '0';
+      p++;
+    }
+    return sign * d;
+  }
+
+  void parse(line_view line) {
+    static const char* cs[] = {"capacity", "durability", "flavor", "texture", "calories"};
+    const char* p0 = line.contains(":");
+    ingredient x{{line.line, p0}, 0, 0, 0, 0, 0};
+    int* xs[] = {&x.capacity, &x.durability, &x.flavor, &x.texture, &x.calories};
+
+    for (size_t i = 0; i < ARRAY_SIZE(cs); i++) {
+      const char* p = line.contains(cs[i]);
+      *xs[i] = get_number(p + strlen(cs[i]) + 1);
+    }
+    // std::cout << x << std::endl;
+    ingredients.push_back(x);
+  }
+};
+
+int day15(line_view);
+
+} // namespace aoc2015
diff --git a/src/2015/day15/input b/src/2015/day15/input
new file mode 100644
index 0000000..6f33d01
--- /dev/null
+++ b/src/2015/day15/input
@@ -0,0 +1,4 @@
+Sprinkles: capacity 2, durability 0, flavor -2, texture 0, calories 3
+Butterscotch: capacity 0, durability 5, flavor -3, texture 0, calories 3
+Chocolate: capacity 0, durability 0, flavor 5, texture -1, calories 8
+Candy: capacity 0, durability -1, flavor 0, texture 5, calories 8
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 8bb132f..96da997 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -14,6 +14,7 @@ set(SOLUTION_FILES
   "2015/day12/aoc.cpp"
   "2015/day13/aoc.cpp"
   "2015/day14/aoc.cpp"
+  "2015/day15/aoc.cpp"
 )
 
 add_library(solution SHARED ${SOLUTION_FILES})