Branch data     Line data    Source code

       1                 :             : #include <algorithm>
       2                 :             : #include <fstream>
       3                 :             : #include <iostream>
       4                 :             : #include <ranges>
       5                 :             : #include <string>
       6                 :             : #include <tuple>
       7                 :             : #include <unordered_map>
       8                 :             : #include <vector>
       9                 :             : using namespace std;
      10                 :             : 
      11                 :           2 : int main() {
      12                 :           2 :   ifstream inf{"input.txt"};
      13         [ +  + ]:           2 :   if (!inf) {
      14                 :           1 :     cerr << "Could not open file: input.txt" << endl;
      15                 :           1 :     return 1;
      16                 :             :   }
      17                 :             : 
      18   [ +  -  +  +  :          91 :   for (string line; getline(inf, line) && !line.empty(););
                   +  + ]
      19                 :             : 
      20                 :           1 :   vector<string> as, bs, cs, ds, wrong;
      21                 :           1 :   unordered_map<string, tuple<string, string, string>> gates;
      22         [ +  + ]:         223 :   for (string input1, input2, op, out, _; inf >> input1 >> op >> input2 >> _ >> out; gates[out] = {op, input1, input2}) {
      23   [ +  +  -  +  :         222 :     if ((input1[0] == 'x' && input2[0] == 'y') || (input1[0] == 'y' && input2[0] == 'x')) {
          +  +  +  -  +  
                      + ]
      24                 :          90 :       int n1{stoi(input1.substr(1))}, n2{stoi(input2.substr(1))};
      25                 :             : 
      26         [ +  - ]:          90 :       if (n1 == n2) {
      27         [ +  + ]:          90 :         if (n1 + 1 > as.size()) {
      28                 :           6 :           as.resize(n1 + 1);
      29                 :           6 :           bs.resize(n1 + 1);
      30                 :             :         }
      31                 :             : 
      32         [ +  + ]:          90 :         as[n1] = (op == "XOR") ? out : as[n1];
      33         [ +  + ]:          90 :         bs[n1] = (op == "AND") ? out : bs[n1];
      34                 :             :       }
      35                 :             :     }
      36                 :           1 :   }
      37                 :           1 :   cs.resize(as.size());
      38                 :           1 :   ds.resize(as.size());
      39                 :           1 :   cs[1] = bs[0]; // Initialize first carry signal
      40                 :             : 
      41                 :           4 :   auto gateSwap = [&gates, &as, &bs, &cs, &ds](const string in1, const string in2) {
      42                 :           4 :     swap(gates[in2], gates[in1]);
      43         [ +  + ]:          20 :     for (auto* vec : {&as, &bs, &cs, &ds}) {
      44         [ +  + ]:         736 :       for (auto& output : *vec) {
      45   [ +  +  +  +  :         720 :         if (output == in2 || output == in1) {
                   +  + ]
      46         [ +  + ]:           3 :           output = (output == in2) ? in1 : in2;
      47                 :             :         }
      48                 :             :       }
      49                 :             :     }
      50                 :           5 :   };
      51                 :             : 
      52                 :          89 :   auto findGateOutputs = [&gates, &ds, &as, &cs, &bs](int i) {
      53         [ +  - ]:        9822 :     for (const auto &[out_gate, gate_gate] : gates) {
      54   [ +  +  +  +  :        9822 :       if (ds[i].empty() && get<0>(gate_gate) == "AND" && ((as[i - 1] == get<1>(gate_gate) && cs[i - 1] == get<2>(gate_gate)) || (as[i - 1] == get<2>(gate_gate) && cs[i - 1] == get<1>(gate_gate)))) {
          +  +  -  +  +  
             +  +  -  +  
                      + ]
      55                 :          43 :         ds[i] = out_gate; break;
      56   [ +  +  +  +  :        9779 :       } else if (!ds[i].empty() && cs[i].empty() && get<0>(gate_gate) == "OR" && ((bs[i - 1] == get<1>(gate_gate) && ds[i] == get<2>(gate_gate)) || (bs[i - 1] == get<2>(gate_gate) && ds[i] == get<1>(gate_gate)))) {
          +  +  +  +  -  
          +  +  +  +  -  
                   +  + ]
      57                 :          43 :         cs[i] = out_gate; break;
      58   [ +  +  +  +  :        9736 :       } else if (!cs[i].empty() && get<0>(gate_gate) == "XOR" && ((as[i] == get<1>(gate_gate) && cs[i] == get<2>(gate_gate)) || (as[i] == get<2>(gate_gate) && cs[i] == get<1>(gate_gate)))) {
          +  +  -  +  +  
             +  +  -  +  
                      + ]
      59                 :           3 :         return out_gate;
      60                 :             :       }
      61                 :             :     }
      62                 :          86 :     return string{};
      63                 :           1 :   };
      64                 :             : 
      65                 :           1 :   auto gate = gates.at("z00");
      66                 :           1 :   string& in1 = get<1>(gate), &in2 = get<2>(gate);
      67   [ +  -  -  +  :           1 :   if (get<0>(gate) != "XOR" || !((in1 == "x00" && in2 == "y00") || (in1 == "y00" && in2 == "x00"))) {
          -  -  +  -  -  
                +  -  + ]
      68                 :           0 :     wrong.emplace_back("z00");
      69                 :             :   }
      70                 :             : 
      71         [ +  + ]:          45 :   for (int i = 1; i < as.size(); ++i) {
      72         [ +  + ]:         132 :     string label = string("z") + (i < 10 ? "0" : "") + to_string(i);
      73                 :          44 :     gate = gates.at(label);
      74                 :          44 :     in1 = get<1>(gate), in2 = get<2>(gate);
      75                 :             : 
      76         [ +  + ]:          44 :     if (get<0>(gate) != "XOR") { // wrong operation
      77                 :           3 :       ds[i] = cs[i] = "";
      78                 :           3 :       string labelSwap;
      79         [ +  + ]:          12 :       while(labelSwap.empty()) {
      80                 :           9 :         labelSwap = findGateOutputs(i);
      81                 :             :       }
      82         [ +  + ]:           9 :       wrong.insert(wrong.end(), {labelSwap, label});
      83                 :           3 :       gateSwap(label, labelSwap);
      84   [ +  +  +  +  :          44 :     } else if (in1 != as[i] && in2 != as[i]) { // XOR gate with wrong inputs
                   +  + ]
      85                 :           1 :       wrong.push_back(as[i]);
      86   [ +  -  -  + ]:           1 :       gateSwap(as[i], (get<1>(gates.at(in1)) == bs[i - 1] || get<2>(gates.at(in1)) == bs[i - 1]) ? in2 : in1);
      87                 :           1 :       wrong.push_back(as[i]);
      88                 :             :     }
      89                 :             : 
      90         [ +  + ]:         124 :     while(cs[i].empty()) {
      91                 :          80 :       findGateOutputs(i);
      92                 :             :     }
      93                 :          44 :   }
      94                 :             : 
      95                 :           1 :   ranges::sort(wrong);
      96                 :             : 
      97                 :           1 :   std::cout << std::ranges::to<std::string>(wrong | std::views::join_with(',')) << std::endl;
      98         [ +  + ]:           3 : }