#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <cctype>

struct program{
    std::string name;
    int weight;
    std::vector<std::string> link_names;
    std::vector<program*> links;
};

program get_program(std::string);
program* find_root(std::vector<program>&);
void link_programs(program*, std::vector<program>&);
int chain_weight(program*);
program* find_bad(program*);
int fix_weight(program*, std::vector<program>&);

int main()
{
    std::vector<program> prog_v;
    std::string root_name;
    std::ifstream txt("day07.txt");
    /*fill program vector*/
    for (std::string line; getline(txt, line);){
        prog_v.push_back(get_program(line));
    }
    txt.close();

    program *root;
    try{
        root = find_root(prog_v);
    }catch (const char *s){
        std::cout << s << '\n';
        return -1;
    }

    link_programs(root, prog_v);

    program *bad = find_bad(root);

    std::cout << "root name: " + root->name + '\n';
    std::cout << "change: " + bad->name + "\n(" << bad->weight  << ") -> ";
    std::cout << "(" << fix_weight(bad, prog_v) << ")\n";
}
/*
 * returns what the bad programs weight should be
 */
int fix_weight(program *p_ptr, std::vector<program> &progs_v)
{
    /*weight of the programs children*/
    int links_weight = chain_weight(p_ptr->links[0]) * p_ptr->links.size();
    int weight_proper = 0;
    /*
     * looks for a neighbor of the bad branch
     * returns the difference of the neighbor
     * and branches children
     */
    for (auto &x : progs_v){
        for (auto &link : x.links){
            if (link == p_ptr){
                weight_proper = (x.links[0] != p_ptr) ?
                    chain_weight(x.links[0]):
                    chain_weight(x.links[1]);
                return weight_proper - links_weight;
            }
        }
    }
    return -1;/*failure*/
}
/*
 * searches for unbalanced program (part 2)
 */
program *find_bad(program *p_ptr)
{
    /*
     * looks at weight of branches and subbrances untill
     * there is no longer anything unbalanced then
     * returns last unbalanced program
     */
    for (auto &x : p_ptr->links){
        bool found = true;
        for (auto &y : p_ptr->links){
            if (x != y && chain_weight(y) == chain_weight(x))
                found = false;
        }
        if (found)
            return find_bad(x);
    }
    return p_ptr;
}
/*
 * returns weight of program and everything its linked to
 */
int chain_weight(program* p_ptr)
{
    /*if found the end return weight*/
    if (p_ptr->links.size() == 0)
        return p_ptr->weight;
    /*otherwise add everything connected recursivly*/
    int weight = p_ptr->weight;
    for (auto &x : p_ptr->links)
        weight += chain_weight(x);

    return weight;
}
/*
 * adds pointers based on programs list of names
 */
void link_programs(program* p_ptr, std::vector<program> &progs_v)
{
    /*
     * looks at the list of progs for every prog
     * and adds a pointer to everything on the list
     */
    if (p_ptr->link_names.size() != 0){
        for (auto &names : p_ptr->link_names){
            for (auto &x : progs_v){
                if (x.name == names){
                    link_programs(&x, progs_v);
                    p_ptr->links.push_back(&x);
                }
            }
        }
    }
}
/*
 * searches for program that nothing is linked to (part 1)
 */
program *find_root(std::vector<program>& progs_v)
{
    /*
     * compares the name of every program to
     * the list of linked programs of every program
     * the one not in a list is the root
     */
    for (auto &x : progs_v){
        bool found = true;
        for (auto &y :progs_v)
            for (auto &s : y.link_names){
                if (s == x.name){
                    found = false;
                    break;
                }
            }
        if (found){
            return &x;
        }
    }
    throw "failed to find root";/*failure*/
}
/*
 * parses the text and returns a program struct
 */
program get_program(std::string line)
{
    program p;

    /*chopping line*/
    std::stringstream line_ss(line);
    std::string chunk;

    /*first string is name*/
    line_ss >> chunk;
    p.name = chunk;

    /*followed by weight*/
    line_ss >> chunk;
    int weight = 0;

    for (auto i = chunk.begin(); *i; i++)
        /*ignore whatever isn't a number*/
        if (isdigit(*i))
            weight = weight * 10 + *i - '0';
    p.weight = weight;
    /*
     * if there is an arrow add the programs its linked to
     * ignore whatever isn't a letter (",")
     */
    if (line_ss >> chunk){
        while (line_ss >> chunk){
            std::string tmp;
            for (auto i = chunk.begin(); *i; i++){
                if (isalpha(*i))
                    tmp += *i;
            }
            p.link_names.push_back(tmp);
        }
    }
    return p;
}