day21 done

4 files changed, 57 insertions, 34 deletions

diff --git a/src/2015/day21/README.md b/src/2015/day21/README.md
index 1dcddcb..46ffddc 100644
--- a/src/2015/day21/README.md
+++ b/src/2015/day21/README.md
@@ -45,4 +45,7 @@ In this scenario, the player wins! (Barely.)
 
 You have 100 hit points. The boss's actual stats are in your puzzle input. What is the least amount of gold you can spend and still win the fight?
 
+--- Part Two ---
+Turns out the shopkeeper is working with the boss, and can persuade you to buy whatever items he wants. The other rules still apply, and he still only has one of each item.
 
+What is the most amount of gold you can spend and still lose the fight?
diff --git a/src/2015/day21/aoc.cpp b/src/2015/day21/aoc.cpp
index 8c7e259..e9b303a 100644
--- a/src/2015/day21/aoc.cpp
+++ b/src/2015/day21/aoc.cpp
@@ -2,22 +2,26 @@
 
 namespace aoc2015 {
 
-int day21() {
+std::pair<int, int> day21() {
   Role me{100, 0, 0, 0};
   Role boss{100, 8, 2, 0};
   RPG game;
 
-  int money{INT32_MAX};
+  int m1{INT32_MAX};
+  int m2{INT32_MIN};
   std::vector<Role> rs = game.shop(me);
-  std::for_each(rs.begin(), rs.end(), [&game, &boss, &money](Role& r) {
+  std::for_each(rs.begin(), rs.end(), [&game, &boss, &m1, &m2](Role& r) {
     Role b = boss;
     if (game.battle(r, b)) {
-      if (r.cost < money) {
-        money = r.cost;
+      if (r.cost < m1) {
+        m1 = r.cost;
+      }
+    } else {
+      if (r.cost > m2) {
+        m2 = r.cost;
       }
     }
   });
-  return money;
+  return {m1, m2};
 }
-
 } // namespace aoc2015
diff --git a/src/2015/day21/aoc.h b/src/2015/day21/aoc.h
index 126613e..ad6a68c 100644
--- a/src/2015/day21/aoc.h
+++ b/src/2015/day21/aoc.h
@@ -14,7 +14,7 @@ struct Role {
 
 struct RPG {
   struct item {
-    line_view name;
+    const char* name;
     int cost;
     int damage;
     int armor;
@@ -27,43 +27,57 @@ struct RPG {
   };
 
   // 0, 1 in 5
-  item armors[5] = {
+  item armors[6] = {
       {"leather", 13, 0, 1},    {"chainmail", 31, 0, 2},  {"splintmail", 53, 0, 3},
-      {"bandedmail", 75, 0, 4}, {"platemail", 102, 0, 5},
+      {"bandedmail", 75, 0, 4}, {"platemail", 102, 0, 5}, {"none", 0, 0, 0},
   };
 
   // 0, 1, 2 in 6
-  item rings[6] = {
-      {"ring1", 25, 1, 0}, {"ring2", 50, 2, 0}, {"ring3", 100, 3, 0},
-      {"ring4", 20, 0, 1}, {"ring5", 40, 0, 2}, {"ring6", 80, 0, 3},
+  item rings[7] = {
+      {"ring1", 25, 1, 0}, {"ring2", 50, 2, 0}, {"ring3", 100, 3, 0}, {"ring4", 20, 0, 1},
+      {"ring5", 40, 0, 2}, {"ring6", 80, 0, 3}, {"none", 0, 0, 0},
   };
 
-  struct three {
-    int i1;
-    int i2;
-    int i3;
-  };
+  bool has_same_ring(std::vector<item*> is) {
+    int x[ARRAY_SIZE(rings)] = {0};
+    for (item* i : is) {
+      line_view lv{i->name};
+      const char* p = lv.contains("ring");
+      if (p != nullptr && ++(x[*(p + 4) - '1']) > 1) {
+        return true;
+      }
+    }
+    return false;
+  }
 
   // backtrace
-  void shop(int i, three& t1, three& t2, std::vector<item>& is) {
-    if (i == 3) {
-
+  void shop(size_t i, std::vector<item*>& v, std::vector<Role>& rs, const Role& r) {
+    static item* items[] = {weapons, armors, rings, rings};
+    static size_t sizes[] = {ARRAY_SIZE(weapons), ARRAY_SIZE(armors), ARRAY_SIZE(rings), ARRAY_SIZE(rings)};
+    if (i < ARRAY_SIZE(items)) {
+      item* is = items[i];
+      for (size_t x = 0; x < sizes[i]; x++) {
+        v.push_back(&is[x]);
+        shop(i + 1, v, rs, r);
+        v.pop_back();
+      }
+    } else {
+      if (!has_same_ring(v)) {
+        Role x = r;
+        std::for_each(v.begin(), v.end(), [&x](item* i) {
+          x.cost += i->cost;
+          x.armor += i->armor;
+          x.damage += i->damage;
+        });
+        rs.push_back(x);
+      }
     }
   }
 
   std::vector<Role> shop(Role r) {
-    std::vector<item> is;
+    std::vector<item*> is;
     std::vector<Role> rs;
-    three t1;
-    three t2;
-    shop(0, t1, t2, is);
-    std::transform(is.begin(), is.end(), rs.begin(), [&r](const item& i) -> Role {
-      Role x = r;
-      x.cost += i.cost;
-      x.armor += i.armor;
-      x.damage += i.damage;
-      return x;
-    });
+    shop(0, is, rs, r);
     return rs;
   }
 
@@ -76,6 +90,6 @@ struct RPG {
   }
 };
 
-int day21();
+std::pair<int,int> day21();
 
 } // namespace aoc2015
diff --git a/test/test_2015.cpp b/test/test_2015.cpp
index 4fa831a..1abda71 100644
--- a/test/test_2015.cpp
+++ b/test/test_2015.cpp
@@ -217,5 +217,7 @@ TEST_CASE("Infinite Elves and Infinite Houses", "[day20]") {
 }
 
 TEST_CASE("RPG Simulator 20XX", "[day21]") {
-  // line_view lv = load_file("../src/2015/day21/input");
+  auto p = aoc2015::day21();
+  REQUIRE(91 == p.first);
+  REQUIRE(158 == p.second);
 }