view 2017/day24/app.d @ 35:1d99d733cf13 default tip @

day08: replace static foreach with workaround
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Tue, 16 Jan 2018 11:28:55 -0500
parents bc652fa0a645
children
line wrap: on
line source

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