Mercurial > hg > aoc
changeset 7:52fdca7ea9be
day 7
author | Jordi Gutiérrez Hermoso <jordigh@octave.org> |
---|---|
date | Fri, 08 Dec 2017 11:58:41 -0500 |
parents | 94a2bb2aad6a |
children | 7d06d033b0ee |
files | 2017/day07.d |
diffstat | 1 files changed, 100 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
new file mode 100644 --- /dev/null +++ b/2017/day07.d @@ -0,0 +1,100 @@ +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); +}