diff options
author | Leah Neukirchen <leah@vuxu.org> | 2017-12-08 13:58:59 +0100 |
---|---|---|
committer | Leah Neukirchen <leah@vuxu.org> | 2017-12-08 13:58:59 +0100 |
commit | 1d15071800b621c219e71858978d4f320cc1b89f (patch) | |
tree | 50ea57f5b7cfd5806ed128a9a6c12d3e15cd2207 /day07.cc | |
parent | 2e09dc131e1c8fad8aac0e51fe4162ecdcf5194e (diff) | |
download | adventofcode2017-1d15071800b621c219e71858978d4f320cc1b89f.tar.gz adventofcode2017-1d15071800b621c219e71858978d4f320cc1b89f.tar.xz adventofcode2017-1d15071800b621c219e71858978d4f320cc1b89f.zip |
day07
Diffstat (limited to 'day07.cc')
-rw-r--r-- | day07.cc | 70 |
1 files changed, 70 insertions, 0 deletions
diff --git a/day07.cc b/day07.cc new file mode 100644 index 0000000..e82162e --- /dev/null +++ b/day07.cc @@ -0,0 +1,70 @@ +#include <algorithm> +#include <iostream> +#include <iterator> +#include <numeric> +#include <set> +#include <sstream> +#include <string> +#include <map> +#include <vector> + +using namespace std; + +map<string,int> weights; +map<string,bool> onbottom; +map<string,vector<string>> ontop; + +int weighing(string s) { + const auto &children = ontop[s]; + vector<int> sw; + + transform(begin(children), end(children), back_inserter(sw), weighing); + + auto [min, max] = minmax_element(begin(sw), end(sw)); + if (min != end(sw) && *min != *max) { + auto another = begin(sw); + while (another != end(sw) && (another == max || another == min)) + another++; + + auto wrong = *min == *another ? max : min; + auto wrongid = ontop[s][distance(sw.begin(), wrong)]; + + cout << weights[wrongid] + (*another - *wrong) << endl; + exit(0); // lame + } + + return accumulate(begin(sw), end(sw), weights[s]); +} + +int +main() +{ + string line; + + while (getline(cin, line)) { + istringstream is1{line}; + string name; + int weight; + + is1 >> name; is1.ignore(5, '('); + is1 >> weight; is1.ignore(5, '>'); + + vector<string> v; + string item; + + while (getline(is1, item, ',')) { + item.erase(0, 1); + v.push_back(item); + onbottom[item] = 1; + } + + weights[name] = weight; + ontop[name] = v; + } + + auto top = find_if_not(begin(weights), end(weights), + [](auto v) { return onbottom.count(v.first); })->first; + + cout << top << "\n"; + weighing(top); +} |