daily pastebin goal
86%
SHARE
TWEET

Untitled

a guest Dec 7th, 2017 15 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <fstream>
  4. #include <sstream>
  5. #include <cctype>
  6.  
  7. struct program{
  8.     std::string name;
  9.     int weight;
  10.     std::vector<std::string> link_names;
  11.     std::vector<program*> links;
  12. };
  13.  
  14. program get_program(std::string);
  15. program* find_root(std::vector<program>&);
  16. void link_programs(program*, std::vector<program>&);
  17. int chain_weight(program*);
  18. program* find_bad(program*);
  19. int fix_weight(program*, std::vector<program>&);
  20.  
  21. int main()
  22. {
  23.     std::vector<program> prog_v;
  24.     std::string root_name;
  25.     std::ifstream txt("day07.txt");
  26.     /*fill program vector*/
  27.     for (std::string line; getline(txt, line);){
  28.         prog_v.push_back(get_program(line));
  29.     }
  30.     txt.close();
  31.  
  32.     program *root;
  33.     try{
  34.         root = find_root(prog_v);
  35.     }catch (const char *s){
  36.         std::cout << s << '\n';
  37.         return -1;
  38.     }
  39.  
  40.     link_programs(root, prog_v);
  41.  
  42.     program *bad = find_bad(root);
  43.  
  44.     std::cout << "root name: " + root->name + '\n';
  45.     std::cout << "change: " + bad->name + "\n(" << bad->weight  << ") -> ";
  46.     std::cout << "(" << fix_weight(bad, prog_v) << ")\n";
  47. }
  48. /*
  49.  * returns what the bad programs weight should be
  50.  */
  51. int fix_weight(program *p_ptr, std::vector<program> &progs_v)
  52. {
  53.     /*weight of the programs children*/
  54.     int links_weight = chain_weight(p_ptr->links[0]) * p_ptr->links.size();
  55.     int weight_proper = 0;
  56.     /*
  57.      * looks for a neighbor of the bad branch
  58.      * returns the difference of the neighbor
  59.      * and branches children
  60.      */
  61.     for (auto &x : progs_v){
  62.         for (auto &link : x.links){
  63.             if (link == p_ptr){
  64.                 weight_proper = (x.links[0] != p_ptr) ?
  65.                     chain_weight(x.links[0]):
  66.                     chain_weight(x.links[1]);
  67.                 return weight_proper - links_weight;
  68.             }
  69.         }
  70.     }
  71.     return -1;/*failure*/
  72. }
  73. /*
  74.  * searches for unbalanced program (part 2)
  75.  */
  76. program *find_bad(program *p_ptr)
  77. {
  78.     /*
  79.      * looks at weight of branches and subbrances untill
  80.      * there is no longer anything unbalanced then
  81.      * returns last unbalanced program
  82.      */
  83.     for (auto &x : p_ptr->links){
  84.         bool found = true;
  85.         for (auto &y : p_ptr->links){
  86.             if (x != y && chain_weight(y) == chain_weight(x))
  87.                 found = false;
  88.         }
  89.         if (found)
  90.             return find_bad(x);
  91.     }
  92.     return p_ptr;
  93. }
  94. /*
  95.  * returns weight of program and everything its linked to
  96.  */
  97. int chain_weight(program* p_ptr)
  98. {
  99.     /*if found the end return weight*/
  100.     if (p_ptr->links.size() == 0)
  101.         return p_ptr->weight;
  102.     /*otherwise add everything connected recursivly*/
  103.     int weight = p_ptr->weight;
  104.     for (auto &x : p_ptr->links)
  105.         weight += chain_weight(x);
  106.  
  107.     return weight;
  108. }
  109. /*
  110.  * adds pointers based on programs list of names
  111.  */
  112. void link_programs(program* p_ptr, std::vector<program> &progs_v)
  113. {
  114.     /*
  115.      * looks at the list of progs for every prog
  116.      * and adds a pointer to everything on the list
  117.      */
  118.     if (p_ptr->link_names.size() != 0){
  119.         for (auto &names : p_ptr->link_names){
  120.             for (auto &x : progs_v){
  121.                 if (x.name == names){
  122.                     link_programs(&x, progs_v);
  123.                     p_ptr->links.push_back(&x);
  124.                 }
  125.             }
  126.         }
  127.     }
  128. }
  129. /*
  130.  * searches for program that nothing is linked to (part 1)
  131.  */
  132. program *find_root(std::vector<program>& progs_v)
  133. {
  134.     /*
  135.      * compares the name of every program to
  136.      * the list of linked programs of every program
  137.      * the one not in a list is the root
  138.      */
  139.     for (auto &x : progs_v){
  140.         bool found = true;
  141.         for (auto &y :progs_v)
  142.             for (auto &s : y.link_names){
  143.                 if (s == x.name){
  144.                     found = false;
  145.                     break;
  146.                 }
  147.             }
  148.         if (found){
  149.             return &x;
  150.         }
  151.     }
  152.     throw "failed to find root";/*failure*/
  153. }
  154. /*
  155.  * parses the text and returns a program struct
  156.  */
  157. program get_program(std::string line)
  158. {
  159.     program p;
  160.  
  161.     /*chopping line*/
  162.     std::stringstream line_ss(line);
  163.     std::string chunk;
  164.  
  165.     /*first string is name*/
  166.     line_ss >> chunk;
  167.     p.name = chunk;
  168.  
  169.     /*followed by weight*/
  170.     line_ss >> chunk;
  171.     int weight = 0;
  172.  
  173.     for (auto i = chunk.begin(); *i; i++)
  174.         /*ignore whatever isn't a number*/
  175.         if (isdigit(*i))
  176.             weight = weight * 10 + *i - '0';
  177.     p.weight = weight;
  178.     /*
  179.      * if there is an arrow add the programs its linked to
  180.      * ignore whatever isn't a letter (",")
  181.      */
  182.     if (line_ss >> chunk){
  183.         while (line_ss >> chunk){
  184.             std::string tmp;
  185.             for (auto i = chunk.begin(); *i; i++){
  186.                 if (isalpha(*i))
  187.                     tmp += *i;
  188.             }
  189.             p.link_names.push_back(tmp);
  190.         }
  191.     }
  192.     return p;
  193. }
RAW Paste Data
Top