view 2017/day12.d @ 13:13f69301183f

day 12
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Tue, 12 Dec 2017 17:21:08 -0500
parents
children
line wrap: on
line source

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);
}