changeset 31:6761b3bbaa70

day 24
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Tue, 02 Jan 2018 20:16:44 -0500
parents c64fab7ed515
children 763c88851b91
files 2017/day24.d
diffstat 1 files changed, 52 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
new file mode 100644
--- /dev/null
+++ b/2017/day24.d
@@ -0,0 +1,52 @@
+import std.stdio;
+import std.string: split;
+import std.conv: to;
+import std.algorithm: map, filter, any, all, sum, maxElement;
+import std.array: array;
+
+struct Halfedge {
+  int node;
+  int id;
+}
+
+auto buildGraph(string[] lines) {
+  Halfedge[][int] graph;
+  foreach(int id, line; lines) {
+    auto nodes = line.split("/").map!(to!int).array;
+    auto input = nodes[0], output = nodes[1];
+    graph[input] = graph.get(input, []) ~ Halfedge(output, id);
+    graph[output] = graph.get(output, []) ~ Halfedge(input, id);
+  }
+  return graph;
+}
+
+Halfedge[][]  paths;
+
+void buildPaths(
+  Halfedge[][int] graph,
+  int node=0,
+  Halfedge[] path=[])
+{
+  auto unexplored_edges = graph[node].filter!(
+    x => path.map!(y => x.id != y.id).all
+  );
+  if (unexplored_edges.empty) {
+    paths ~= path;
+  }
+  else {
+    foreach(edge; unexplored_edges) {
+      auto newpath = path.dup ~ edge;
+      buildPaths(graph, edge.node, newpath);
+    }
+  }
+}
+
+int pathWeight(Halfedge[] path) {
+  return path[0..$-1].map!(x => x.node).sum*2 + path[$-1].node;
+}
+
+void main(string[] args){
+  File(args[1]).byLineCopy.array.buildGraph.buildPaths;
+  writeln(paths.map!(pathWeight).maxElement);
+  writeln(paths.maxElement!(p => [p.length, p.pathWeight]).pathWeight);
+}