changeset 13:13f69301183f tip @

day 12
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Tue, 12 Dec 2017 17:21:08 -0500
parents a991288f3d55
children
files 2017/day12.d
diffstat 1 files changed, 42 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
new file mode 100644
--- /dev/null
+++ b/2017/day12.d
@@ -0,0 +1,42 @@
+import std.stdio;
+import std.regex: regex, matchFirst;
+import std.conv: to;
+import std.string: split;
+import std.algorithm: sort, map, setDifference;
+import std.array: array;
+
+static nodeRegex = regex(r"(?P<src>\d+) <-> (?P<dests>.*)");
+
+auto buildGraph(T)(T lines) {
+  int[][int] graph;
+  foreach(line; lines) {
+    auto row = matchFirst(line, nodeRegex);
+    graph[to!int(row["src"])] = row["dests"].split(", ").map!(to!int).array;
+  }
+  return graph;
+}
+
+bool[int] dfsFindNodes(int[][int] graph, int start, bool[int] seen = null) {
+  seen[start] = true;
+  foreach(node; graph[start]) {
+    if (node !in seen) {
+      seen[node] = true;
+      seen = dfsFindNodes(graph, node, seen);
+    }
+  }
+  return seen;
+}
+
+void main(string[] args) {
+  auto graph = buildGraph(File(args[1]).byLine);
+  auto seen = dfsFindNodes(graph, 0);
+  writeln(seen.keys.length);
+  auto unseen = setDifference(sort(graph.keys), sort(seen.keys)).array;
+  auto numcomponents = 1;
+  while (unseen) {
+    numcomponents++;
+    seen = dfsFindNodes(graph, unseen[0], seen);
+    unseen = setDifference(unseen, sort(seen.keys)).array;
+  }
+  writeln(numcomponents);
+}