3 files changed, 141 insertions, 1 deletions

diff --git a/src/2015/day13/README.md b/src/2015/day13/README.md
index 94262d6..6a8a36e 100644
--- a/src/2015/day13/README.md
+++ b/src/2015/day13/README.md
@@ -33,5 +33,10 @@ After trying every other seating arrangement in this hypothetical scenario, you
 
 What is the total change in happiness for the optimal seating arrangement of the actual guest list?
 
+--- Part Two ---
 
+In all the commotion, you realize that you forgot to seat yourself. At this point, you're pretty apathetic toward the whole thing, and your happiness wouldn't really go up or down regardless of who you sit next to. You assume everyone else would be just as ambivalent about sitting next to you, too.
 
+So, add yourself to the list, and give all happiness relationships that involve you a score of 0.
+
+What is the total change in happiness for the optimal seating arrangement that actually includes yourself?
diff --git a/src/2015/day13/aoc.cpp b/src/2015/day13/aoc.cpp
index 1c33c66..56ada11 100644
--- a/src/2015/day13/aoc.cpp
+++ b/src/2015/day13/aoc.cpp
@@ -2,4 +2,16 @@
 
 namespace aoc2015 {
 
+std::pair<int, int> day13(line_view file, const char* x) {
+  party p;
+  per_line(file, [&p](line_view lv) {
+    p.parse(lv);
+    return true;
+  });
+  if (x != nullptr) {
+    p.add(x, 0);
+  }
+  return p.arrange();
 }
+
+} // namespace aoc2015
diff --git a/src/2015/day13/aoc.h b/src/2015/day13/aoc.h
index 7eb843c..8cb22f7 100644
--- a/src/2015/day13/aoc.h
+++ b/src/2015/day13/aoc.h
@@ -1,7 +1,130 @@
 #pragma once
 
 #include "common.h"
+#include <map>
+#include <set>
+#include <vector>
 
 namespace aoc2015 {
 
-}
+struct guest {
+  line_view name;
+  std::map<guest*, int> points;
+
+  int point(guest* other) {
+    auto it = points.find(other);
+    return it != points.end() ? it->second : 0;
+  }
+};
+
+struct party {
+  std::vector<guest*> guests;
+
+  guest* the(line_view lv) {
+    for (auto g : guests) {
+      if (g->name == lv) {
+        return g;
+      }
+    }
+    guests.emplace_back(new guest{lv, {}});
+    return guests.back();
+  }
+
+  int happiness(std::vector<guest*> gs) const noexcept {
+    int h = 0;
+    int size = gs.size();
+    for (int i = 0; i < size; i++) {
+      guest* g1 = gs[i];
+      guest* g2 = i < size - 1 ? gs[i + 1] : gs[0];
+      h += g1->point(g2);
+      h += g2->point(g1);
+    }
+    return h;
+  }
+
+  int happiness(const char* p) {
+    int h{0};
+    while (*p != ' ') {
+      h = h * 10 + *p - '0';
+      p++;
+    }
+    return h;
+  }
+
+  // backtrace
+  typedef std::vector<guest*>* arrange_t;
+  typedef std::vector<std::vector<guest*>> combo_t;
+  void arrange(guest* g, std::set<guest*>& gs, arrange_t arrangement, combo_t& combos) const noexcept {
+    if (arrangement->size() == guests.size()) {
+      combos.push_back(*arrangement);
+      return;
+    }
+    for (auto& kv : g->points) {
+      if (gs.find(kv.first) != gs.end()) {
+        continue;
+      } else {
+        gs.insert(kv.first);
+        arrangement->push_back(kv.first);
+        arrange(kv.first, gs, arrangement, combos);
+        arrangement->pop_back();
+        gs.erase(kv.first);
+      }
+    }
+  }
+
+  std::pair<int, int> arrange() const noexcept {
+    combo_t combos;
+    for (auto g : guests) {
+      arrange_t arrangement = new std::vector<guest*>;
+      std::set<guest*> gs;
+      arrange(g, gs, arrangement, combos);
+    }
+
+    int hmax = INT32_MIN;
+    int hmin = INT32_MAX;
+    for (auto c : combos) {
+      int h = happiness(c);
+      /*
+      std::cout << "[" << h << ":";
+      for (auto x : c) {
+        std::cout << x->name << " -> ";
+      }
+      std::cout << "]" << std::endl;
+      */
+      if (hmax < h) {
+        hmax = h;
+      }
+      if (hmin > h) {
+        hmin = h;
+      }
+    }
+    return {hmin, hmax};
+  }
+
+  void parse(line_view lv) {
+    const char* p = lv.line;
+    const char* p1 = lv.contains("would");
+    const char* p2 = lv.contains("to");
+    guest* g1 = the({p, p1 - 1});
+    guest* g2 = the({p2 + 3, p + lv.length - 2});
+    int point = happiness(p1 + 11);
+    if (*(p1 + 6) == 'l') {
+      point = -point;
+    }
+    // std::cout << g1->name << " -> " << g2->name << ":" << point << std::endl;
+    g1->points.insert({g2, point});
+  }
+
+  void add(const char* x, int h) {
+    guest* ng = new guest{x, {}};
+    for (auto g : guests) {
+      g->points.insert({ng, h});
+      ng->points.insert({g, h});
+    }
+    guests.push_back(ng);
+  }
+};
+
+std::pair<int, int> day13(line_view file, const char* = nullptr);
+
+} // namespace aoc2015