changeset 7:52fdca7ea9be

day 7
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Fri, 08 Dec 2017 11:58:41 -0500
parents 94a2bb2aad6a
children 7d06d033b0ee
files 2017/day07.d
diffstat 1 files changed, 100 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
new file mode 100644
--- /dev/null
+++ b/2017/day07.d
@@ -0,0 +1,100 @@
+import std.array: array, assocArray, byPair;
+import std.stdio;
+import std.algorithm: map, filter, uniq, group;
+import std.regex;
+import std.string: split;
+import std.conv: to;
+
+struct Node(numType) {
+  numType weight;
+  string[] childNames;
+  numType[string] subweights;
+  bool balanced;
+  string parent;
+}
+
+Node!int[string] index;
+
+void parseLine(string line) {
+  static nodeRegex = regex(
+    r"(?P<name>\w+) \((?P<weight>\d+)\)( -> (?P<children>[\w, ]+))?"
+  );
+  auto row = matchFirst(line, nodeRegex);
+  Node!int n = {
+    weight: to!int(row["weight"]),
+    childNames: row["children"].split(", "),
+    balanced: true,
+  };
+  index[row["name"]] = n;
+}
+
+void connectNodes() {
+  foreach(parent, node; index) {
+    foreach(child; node.childNames) {
+      index[child].parent = parent;
+    }
+  }
+}
+
+auto findRoot() {
+  foreach(name, node; index) {
+    if(!node.parent) {
+      return name;
+    }
+  }
+  return "";
+}
+
+void computeSubWeights(string name) {
+  auto node = index[name];
+  foreach(subname; node.childNames) {
+    computeSubWeights(subname);
+    auto subnode = index[subname];
+    auto subsum = 0;
+    foreach(subweight; subnode.subweights) {
+      subsum += subweight;
+    }
+    node.subweights[subname] = subnode.weight + subsum;
+  }
+  node.balanced = node.subweights.values.uniq.array.length <= 1;
+  index[name] = node;
+}
+
+string findUnbalanced(string name) {
+  auto node = index[name];
+  foreach(subname; node.childNames) {
+    auto subnode = index[subname];
+    if(!subnode.balanced) {
+      return findUnbalanced(subname);
+    }
+  }
+  return name;
+}
+
+auto balanceTilty(string tilty) {
+  auto node = index[tilty];
+  auto weightCounts = node.subweights.values.group.assocArray;
+  auto badweight = weightCounts.byPair.filter!(x => x[1] == 1).array[0][0];
+  auto goodweight = weightCounts.byPair.filter!(x => x[1] > 1).array[0][0];
+  auto badname =
+    node
+    .subweights
+    .byPair
+    .filter!(x => x[1] == badweight)
+    .array[0][0];
+
+  return index[badname].weight + (goodweight-badweight);
+}
+
+void main(string[] args) {
+  foreach(line; File(args[1]).byLineCopy) {
+    parseLine(line);
+  }
+  connectNodes();
+  auto root = findRoot();
+  writeln(root);
+  computeSubWeights(root);
+  auto tilty = findUnbalanced(root);
+  auto balancedValue = balanceTilty(tilty);
+  writeln(balancedValue);
+}