Mercurial > hg > aoc
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); }