view 2017/day07.d @ 7:52fdca7ea9be

day 7
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Fri, 08 Dec 2017 11:58:41 -0500
parents
children
line wrap: on
line source

import std.array: array, assocArray, byPair;
import std.stdio;
import std.algorithm: map, filter, uniq, group;
import std.regex;
import std.string: split;
import std.conv: to;

struct Node(numType) {
  numType weight;
  string[] childNames;
  numType[string] subweights;
  bool balanced;
  string parent;
}

Node!int[string] index;

void parseLine(string line) {
  static nodeRegex = regex(
    r"(?P<name>\w+) \((?P<weight>\d+)\)( -> (?P<children>[\w, ]+))?"
  );
  auto row = matchFirst(line, nodeRegex);
  Node!int n = {
    weight: to!int(row["weight"]),
    childNames: row["children"].split(", "),
    balanced: true,
  };
  index[row["name"]] = n;
}

void connectNodes() {
  foreach(parent, node; index) {
    foreach(child; node.childNames) {
      index[child].parent = parent;
    }
  }
}

auto findRoot() {
  foreach(name, node; index) {
    if(!node.parent) {
      return name;
    }
  }
  return "";
}

void computeSubWeights(string name) {
  auto node = index[name];
  foreach(subname; node.childNames) {
    computeSubWeights(subname);
    auto subnode = index[subname];
    auto subsum = 0;
    foreach(subweight; subnode.subweights) {
      subsum += subweight;
    }
    node.subweights[subname] = subnode.weight + subsum;
  }
  node.balanced = node.subweights.values.uniq.array.length <= 1;
  index[name] = node;
}

string findUnbalanced(string name) {
  auto node = index[name];
  foreach(subname; node.childNames) {
    auto subnode = index[subname];
    if(!subnode.balanced) {
      return findUnbalanced(subname);
    }
  }
  return name;
}

auto balanceTilty(string tilty) {
  auto node = index[tilty];
  auto weightCounts = node.subweights.values.group.assocArray;
  auto badweight = weightCounts.byPair.filter!(x => x[1] == 1).array[0][0];
  auto goodweight = weightCounts.byPair.filter!(x => x[1] > 1).array[0][0];
  auto badname =
    node
    .subweights
    .byPair
    .filter!(x => x[1] == badweight)
    .array[0][0];

  return index[badname].weight + (goodweight-badweight);
}

void main(string[] args) {
  foreach(line; File(args[1]).byLineCopy) {
    parseLine(line);
  }
  connectNodes();
  auto root = findRoot();
  writeln(root);
  computeSubWeights(root);
  auto tilty = findUnbalanced(root);
  auto balancedValue = balanceTilty(tilty);
  writeln(balancedValue);
}