Mercurial > hg > aoc

comparison 2017/day07.d @ 7:52fdca7ea9be

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
day 7
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Fri, 08 Dec 2017 11:58:41 -0500
parents
children
comparison
equal deleted inserted replaced
6:94a2bb2aad6a 7:52fdca7ea9be
1 import std.array: array, assocArray, byPair;
2 import std.stdio;
3 import std.algorithm: map, filter, uniq, group;
4 import std.regex;
5 import std.string: split;
6 import std.conv: to;
7
8 struct Node(numType) {
9 numType weight;
10 string[] childNames;
11 numType[string] subweights;
12 bool balanced;
13 string parent;
14 }
15
16 Node!int[string] index;
17
18 void parseLine(string line) {
19 static nodeRegex = regex(
20 r"(?P<name>\w+) \((?P<weight>\d+)\)( -> (?P<children>[\w, ]+))?"
21 );
22 auto row = matchFirst(line, nodeRegex);
23 Node!int n = {
24 weight: to!int(row["weight"]),
25 childNames: row["children"].split(", "),
26 balanced: true,
27 };
28 index[row["name"]] = n;
29 }
30
31 void connectNodes() {
32 foreach(parent, node; index) {
33 foreach(child; node.childNames) {
34 index[child].parent = parent;
35 }
36 }
37 }
38
39 auto findRoot() {
40 foreach(name, node; index) {
41 if(!node.parent) {
42 return name;
43 }
44 }
45 return "";
46 }
47
48 void computeSubWeights(string name) {
49 auto node = index[name];
50 foreach(subname; node.childNames) {
51 computeSubWeights(subname);
52 auto subnode = index[subname];
53 auto subsum = 0;
54 foreach(subweight; subnode.subweights) {
55 subsum += subweight;
56 }
57 node.subweights[subname] = subnode.weight + subsum;
58 }
59 node.balanced = node.subweights.values.uniq.array.length <= 1;
60 index[name] = node;
61 }
62
63 string findUnbalanced(string name) {
64 auto node = index[name];
65 foreach(subname; node.childNames) {
66 auto subnode = index[subname];
67 if(!subnode.balanced) {
68 return findUnbalanced(subname);
69 }
70 }
71 return name;
72 }
73
74 auto balanceTilty(string tilty) {
75 auto node = index[tilty];
76 auto weightCounts = node.subweights.values.group.assocArray;
77 auto badweight = weightCounts.byPair.filter!(x => x[1] == 1).array[0][0];
78 auto goodweight = weightCounts.byPair.filter!(x => x[1] > 1).array[0][0];
79 auto badname =
80 node
81 .subweights
82 .byPair
83 .filter!(x => x[1] == badweight)
84 .array[0][0];
85
86 return index[badname].weight + (goodweight-badweight);
87 }
88
89 void main(string[] args) {
90 foreach(line; File(args[1]).byLineCopy) {
91 parseLine(line);
92 }
93 connectNodes();
94 auto root = findRoot();
95 writeln(root);
96 computeSubWeights(root);
97 auto tilty = findUnbalanced(root);
98 auto balancedValue = balanceTilty(tilty);
99 writeln(balancedValue);
100 }