2017 day7 part1

3 files changed, 96 insertions, 1 deletions

diff --git a/src/2017/day7/README.md b/src/2017/day7/README.md
index 2784eb6..9ed70f8 100644
--- a/src/2017/day7/README.md
+++ b/src/2017/day7/README.md
@@ -43,4 +43,18 @@ In this example, tknk is at the bottom of the tower (the bottom program), and is
 
 Before you're ready to help them, you need to make sure your information is correct. What is the name of the bottom program?
 
+--- Part Two ---
+The programs explain the situation: they can't get down. Rather, they could get down, if they weren't expending all of their energy trying to keep the tower balanced. Apparently, one program has the wrong weight, and until it's fixed, they're stuck here.
 
+For any program holding a disc, each program standing on that disc forms a sub-tower. Each of those sub-towers are supposed to be the same weight, or the disc itself isn't balanced. The weight of a tower is the sum of the weights of the programs in that tower.
+
+In the example above, this means that for ugml's disc to be balanced, gyxo, ebii, and jptl must all have the same weight, and they do: 61.
+
+However, for tknk to be balanced, each of the programs standing on its disc and all programs above it must each match. This means that the following sums must all be the same:
+
+ugml + (gyxo + ebii + jptl) = 68 + (61 + 61 + 61) = 251
+padx + (pbga + havc + qoyq) = 45 + (66 + 66 + 66) = 243
+fwft + (ktlj + cntj + xhth) = 72 + (57 + 57 + 57) = 243
+As you can see, tknk's disc is unbalanced: ugml's stack is heavier than the other two. Even though the nodes above ugml are balanced, ugml itself is too heavy: it needs to be 8 units lighter for its stack to weigh 243 and keep the towers balanced. If this change were made, its weight would be 60.
+
+Given that exactly one program is the wrong weight, what would its weight need to be to balance the entire tower?
diff --git a/src/2017/day7/aoc.cpp b/src/2017/day7/aoc.cpp
index fe3ee2f..86e2e45 100644
--- a/src/2017/day7/aoc.cpp
+++ b/src/2017/day7/aoc.cpp
@@ -1,4 +1,57 @@
 #include "aoc.h"
+#include <unordered_map>
 
 namespace aoc2017 {
+
+void fix_subs(std::unordered_map<line_view, disc*>& ds) {
+  for (auto& kv : ds) {
+    if (kv.second->xp != nullptr) {
+      const char* p1 = kv.second->xp;
+      const char* p = p1;
+      while (*p != '\n') {
+        if (*p == ',') {
+          kv.second->subs.push_back(ds[{p1, p}]);
+          p1 = p + 2;
+        }
+        p++;
+      }
+      kv.second->subs.push_back(ds[{p1, p}]);
+    }
+  }
+}
+
+void depth(disc* d, int* dh) {
+  if (d->subs.size() > 0) {
+    *dh += 1;
+    depth(d->subs[0], dh);
+  }
 }
+
+void day7(line_view file, char name[]) {
+  std::unordered_map<line_view, disc*> ds;
+  per_line(file, [&ds](line_view lv) {
+    const char* p = lv.contains("(");
+    line_view name{lv.line, p - 1};
+    ds.insert({name, new disc{lv, p}});
+    return true;
+  });
+  fix_subs(ds);
+
+  line_view x;
+  int max{INT32_MIN};
+  for (auto& kv : ds) {
+    int d{1};
+    depth(kv.second, &d);
+    if (d > max) {
+      max = d;
+      x = kv.first;
+    }
+  }
+  int i{0};
+  per_char(x, [&name, &i](char c) {
+    name[i++] = c;
+    return true;
+  });
+}
+
+} // namespace aoc2017
diff --git a/src/2017/day7/aoc.h b/src/2017/day7/aoc.h
index 1f1d643..f3b9104 100644
--- a/src/2017/day7/aoc.h
+++ b/src/2017/day7/aoc.h
@@ -1,5 +1,33 @@
 #pragma once
 #include "common.h"
+#include <vector>
 
 namespace aoc2017 {
-}
+
+struct disc {
+  line_view name;
+  int weight;
+  std::vector<disc*> subs;
+  const char* xp = nullptr;
+
+  const char* get_number(const char* p, int* d) {
+    *d = 0;
+    while (*p >= '0' && *p <= '9') {
+      *d = *d * 10 + *p - '0';
+      p++;
+    }
+    return p;
+  }
+
+  disc(line_view lv, const char* p) {
+    name = {lv.line, p - 1};
+    p = get_number(p + 1, &weight) + 5;
+    if (p < lv.line + lv.length) {
+      xp = p;
+    }
+  }
+};
+
+void day7(line_view, char[]);
+
+} // namespace aoc2017