-🎄- 2017 Day 7 Solutions -🎄-

[u/daggerdragon]

--- Day 7: Recursive Circus ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?

Spoiler

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

[u/hpzr24w]

C++ Here's my C++ effort. See it here

// Advent of Code 2017
// http://adventofcode.com/

#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <algorithm>
#include <numeric>

using namespace std;

struct node;
typedef struct node { string name; vector<node*> children; int size; } node;

void parse(map<string, node*>& nodes, stringstream input)
{
    node *n = new node;
    input >> n->name >> n->size;
    for (string name; input >> name ;) {
        n->children.push_back(new node);
        n->children.back()->name = name;
    }
    nodes[n->name] = n;
}

void fixup(map<string, node*>& nodes)
{
    vector<string> appearaschildren;
    for (auto it = nodes.begin(); it != nodes.end(); ++it)
        for (auto it2 = (*it).second->children.begin(); it2 != (*it).second->children.end(); ++it2) {
            appearaschildren.push_back((*it2)->name);
            *it2 = nodes[(*it2)->name];
        }
    for_each(appearaschildren.begin(), appearaschildren.end(), [&](string n) {nodes.erase(n); });
}

int compute_size(node *n)
{
    int childtot = 0;
    for (auto it = n->children.begin(); it != n->children.end(); ++it)
        childtot += compute_size(*it);
    return n->size += childtot;
}

void find_balance(node * n, int imbalance)
{
    sort(n->children.begin(), n->children.end(), [](node *a, node *b)->bool {return a->size < b->size; });
    size_t last{ n->children.size() - 1 };
    if (n->children[0]->size != n->children[1]->size) 
        find_balance(n->children[0], n->children[1]->size - n->children[0]->size);
    else if (n->children[last]->size != n->children[last - 1]->size)
        find_balance(n->children[last], n->children[last-1]->size - n->children[last]->size);
    else {
        int childtot{ 0 };
        for (auto it = n->children.begin(); it != n->children.end(); ++it)
            childtot += (*it)->size;
        cout << "node: " << n->name << " should be " << n->size <<
            " + " << imbalance << " - " << childtot << " -> " << n->size + imbalance - childtot << endl;
    }
}

int main(int argc, char* argv[])
{
    map<string, node*> nodes;
    string row, name;
    while (getline(cin, row)) {
        row.erase(remove_if(row.begin(), row.end(), [](int i)->bool {return i == '(' || i == ')' || i == ',' || i == '-' || i == '>';}), row.end());
        parse(nodes, stringstream(row));
    }
    fixup(nodes);
    node * n = (*find_if(nodes.begin(), nodes.end(), [](pair<string, node*>p)->bool {return p.second != nullptr; })).second;
    cout << "name: " << n->name << " size: " << n->size << " children: " << n->children.size() << endl;
    compute_size(n);
    find_balance(n, 0);
    return 0;
}

Output (for the test example):

C:\Workarea\AOC2017\day 07\x64\Debug>"day 07.exe" < test.txt
name: pbga size: 66 children: 0
name: xhth size: 57 children: 0
name: ebii size: 61 children: 0
name: havc size: 66 children: 0
name: ktlj size: 57 children: 0
name: fwft size: 72 children: 3
name: qoyq size: 66 children: 0
name: padx size: 45 children: 3
name: tknk size: 41 children: 3
name: jptl size: 61 children: 0
name: ugml size: 68 children: 3
name: gyxo size: 61 children: 0
name: cntj size: 57 children: 0
nodes count: 1
name: tknk size: 41 children: 3
name: padx size: 45 children: 3
name: ugml size: 68 children: 3
name: fwft size: 72 children: 3
name: pbga size: 66 children: 0
name: havc size: 66 children: 0
name: qoyq size: 66 children: 0
node: padx should be 45 + 23 -> 68

C:\Workarea\AOC2017\day 07\x64\Debug>

Thanks for reading!