API tools faq
paste
Guest User

Untitled

a guest
Dec 11th, 2025
179
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 17.43 KB | Source Code | 0 0
raw download clone embed print report
  1. #include "advent.hpp"
  2. #include <bit>
  3. #include <chrono>
  4. #include <cstdint>
  5. #include <format>
  6. #include <queue>
  7. #include <numeric>
  8. #include <utility>
  9.  
  10.  
  11. struct Machine {
  12.     i64 len = 0;
  13.     i64 target = 0;
  14.     vector<i64> buttons{};
  15.     vector<i64> joltage{};
  16. };
  17.  
  18. ostream& printBits(ostream& o, i64 v, i64 len) {
  19.     for (i64 i = len - 1; i >= 0; i--) {
  20.         o << ((v & (1LL << i)) ? '1' : '0');
  21.     }
  22.     return o;
  23. }
  24.  
  25. ostream& operator<<(ostream& os, const Machine& m) {
  26.     os << "(" << m.len << ", ";
  27.     printBits(os, m.target, m.len);
  28.     os << ", ";
  29.     bool first = true;
  30.     os << "[";
  31.     for (auto b : m.buttons) {
  32.         if (first) first = false; else os << ", ";
  33.         printBits(os, b, m.len);
  34.     }
  35.     os << "], ";
  36.     os << m.joltage;
  37.     os << ")";
  38.     return os;
  39. }
  40.  
  41. void iterateSets(int n, auto&& callback) {
  42.     uint64_t limit = 1ull << n;  // assumes n <= 63
  43.  
  44.     for (int k = 1; k <= n; ++k) {
  45.         uint64_t s = (1ull << k) - 1;
  46.         while (s < limit) {
  47.             if (!callback(s))
  48.                 return;
  49.             uint64_t c = s & -s;
  50.             uint64_t r = s + c;
  51.             s = (((r ^ s) >> 2) / c) | r;
  52.         }
  53.     }
  54. }
  55.  
  56. void iterateBits(uint64_t bits, auto&& callback) {
  57.     while (bits) {
  58.         uint64_t t = bits & -bits;
  59.         int r = std::countr_zero(t);
  60.         if (!callback(r))
  61.             return;
  62.         bits &= bits - 1;
  63.     }
  64. }
  65.  
  66. constexpr size_t LIMIT = 16;
  67. using Vec = array<int16_t, LIMIT>;
  68.  
  69. Vec operator+(const Vec& a, const Vec& b) {
  70.     Vec res;
  71.     for (size_t i = 0; i < LIMIT; i++)
  72.         res[i] = a[i] + b[i];
  73.     return res;
  74. }
  75. Vec operator-(const Vec& a, const Vec& b) {
  76.     Vec res;
  77.     for (size_t i = 0; i < LIMIT; i++)
  78.         res[i] = a[i] - b[i];
  79.     return res;
  80. }
  81. Vec operator*(const Vec& a, int16_t b) {
  82.     Vec res;
  83.     for (size_t i = 0; i < LIMIT; i++)
  84.         res[i] = a[i] * b;
  85.     return res;
  86. }
  87.  
  88. void fastSwap(Vec& a, Vec& b) {
  89.     auto tmp = a;
  90.     a = b;
  91.     b = tmp;
  92. }
  93.  
  94.  
  95. struct Solver {
  96.     const Machine& machine;
  97.     int buttons;
  98.     int jolts;
  99.     array<vector<int>, LIMIT> forward;
  100.     array<vector<int>, LIMIT> reverse;
  101.  
  102.     Solver(const Machine& machine) : machine(machine) {
  103.         buttons = machine.buttons.size();
  104.         jolts = machine.joltage.size();
  105.         assert(buttons + 1 <= forward.size());
  106.         assert(jolts + 1 <= reverse.size());
  107.         for (i64 b = 0; b < machine.buttons.size(); b++) {
  108.             for (i64 j = 0; j < machine.joltage.size(); j++) {
  109.                 if (machine.buttons[b] & (1ll << j)) {
  110.                     reverse[j].push_back(b);
  111.                     forward[b].push_back(j);
  112.                 }
  113.             }
  114.         }
  115.     }
  116.  
  117.     int simplify(Vec& v) {
  118.         int g = 0;
  119.         int first = -1;
  120.         for (i64 b = 0; b < buttons; b++) {
  121.             if (v[b] == 0)
  122.                 continue;
  123.             g = gcd(g, v[b]);
  124.             if (first == -1)
  125.                 first = b;
  126.         }
  127.         if (g > 1) {
  128.             if (v[LIMIT - 1] % g != 0)
  129.                 return -1;
  130.             for (auto& x : v)
  131.                 x /= g;
  132.         }
  133.         if (first >= 0) {
  134.             if (v[first] < 0)
  135.                 for (auto& x : v)
  136.                     x = -x;
  137.             assert(v[first] > 0);
  138.             return v[first];
  139.         }
  140.         return 0;
  141.     }
  142.     static void pmat(const span<Vec>& rows) {
  143.         for (auto& row : rows) {
  144.             for (i64 i = 0; i < LIMIT; i++) {
  145.                 cout << format("{:4}", row[i]);
  146.             }
  147.             cout << endl;
  148.         }
  149.     }
  150.  
  151.     [[gnu::noinline]] tuple<int, int, int, unsigned, int> gaussian(vector<Vec>& rows, int limit = -1) {
  152.         bool isPrep = limit < 0;
  153.         // Run gaussian elimination
  154.         // Return a free variable and the maximum value for that variable
  155.         i64 n = rows.size();
  156.         i64 m = buttons;
  157.         for (i64 h = 0, k = 0; h < n && k < m; k++) {
  158.             // Find the kth pivot
  159.             i64 i_pivot = h;
  160.             for (i64 i = h; i < n; i++) {
  161.                 if (rows[i][k] != 0) {
  162.                     i_pivot = i;
  163.                     break;
  164.                 }
  165.             }
  166.             if (rows[i_pivot][k] == 0)
  167.                 continue; // No pivot in this column
  168.             // Swap rows
  169.             fastSwap(rows[h], rows[i_pivot]);
  170.             // For all rows below pivot
  171.             for (i64 i = 0; i < h; i++) {
  172.                 if (rows[i][k] != 0) {
  173.                     auto g = gcd(rows[h][k], rows[i][k]);
  174.                     rows[i] = rows[i] * (rows[h][k] / g) - rows[h] * (rows[i][k] / g);
  175.                 }
  176.             }
  177.             for (i64 i = i_pivot + 1; i < n; i++) {
  178.                 if (rows[i][k] != 0) {
  179.                     auto g = gcd(rows[h][k], rows[i][k]);
  180.                     rows[i] = rows[i] * (rows[h][k] / g) - rows[h] * (rows[i][k] / g);
  181.                 }
  182.             }
  183.             h++;
  184.         }
  185.         array<int, 16> zeroInds{};
  186.         size_t removedZeros = 0;
  187.         unsigned singleInds = 0;
  188.         int singleTotal = 0;
  189.         tuple<int, int, int, unsigned, int> errorResult{-1, -1, -1, 0u, -1};
  190.         array<int, 16> lowerBounds;
  191.         array<int, 16> upperBounds;
  192.         for (i64 b = 0; b < buttons; b++) {
  193.             lowerBounds[b] = 0;
  194.             upperBounds[b] = INT_MAX;
  195.         }
  196.         for (i64 j = 0; j < rows.size(); j++) {
  197.             int count = 0;
  198.             int index = -1;
  199.             int numSame = 0;
  200.             int numGt = 0;
  201.             for (i64 b = 0; b < LIMIT - 1; b++) {
  202.                 if (rows[j][b] != 0) {
  203.                     count++;
  204.                     index = b;
  205.                     // Does it face same direction as the constant term
  206.                     numGt += rows[j][b] > 0;
  207.                     numSame += ((rows[j][b] >= 0) == (rows[j][LIMIT - 1] >= 0)) || (rows[j][LIMIT - 1] == 0);
  208.                 }
  209.             }
  210.             if (count == 0) {
  211.                 if (rows[j][LIMIT - 1] != 0)
  212.                     return errorResult; // No solution
  213.                 rows[j] = rows.back();
  214.                 rows.pop_back();
  215.                 j--;
  216.                 continue;
  217.             }
  218.             if (numSame == 0) {
  219.                 // If none of our variables face the same direction as the constant term, no solution, as variables need to be positive
  220.                 return errorResult;
  221.             }
  222.             if (count == 1) {
  223.                 // We need integer solutions
  224.                 if (rows[j][LIMIT - 1] % rows[j][index] != 0)
  225.                     return errorResult;
  226.                 auto val = rows[j][LIMIT - 1] / rows[j][index];
  227.                 // We need >= 0 solutions
  228.                 if (val < 0)
  229.                     return errorResult;
  230.                 singleInds |= (1u << index);
  231.                 singleTotal += val;
  232.                 rows[j] = rows.back();
  233.                 rows.pop_back();
  234.                 j--;
  235.             } else {
  236.                 if (numSame == count && (numGt == 0 || numGt == count)) {
  237.                     // All variables face the same direction as the constant term
  238.                     // We can compute a proper maximum
  239.                     for (i64 b = 0; b < LIMIT - 1; b++) {
  240.                         if (rows[j][b] != 0) {
  241.                             int coeff = rows[j][LIMIT - 1] / rows[j][b];
  242.  
  243.                             if (coeff == 0) {
  244.                                 for (i64 j2 = 0; j2 < rows.size(); j2++)
  245.                                     rows[j2][b] = 0;
  246.                                 assert(removedZeros < zeroInds.size());
  247.                                 zeroInds[removedZeros++] = b;
  248.                                 continue;
  249.                             }
  250.  
  251.                             assert(coeff >= 0);
  252.                             upperBounds[b] = min(upperBounds[b], coeff);
  253.                         }
  254.                     }
  255.                 } else if (numGt == 1 && rows[j][LIMIT - 1] > 0) {
  256.                     for (i64 b = 0; b < LIMIT - 1; b++) {
  257.                         if (rows[j][b] > 0) {
  258.                             int coeff = (rows[j][LIMIT - 1] + rows[j][b] - 1) / rows[j][b];
  259.                             assert(coeff >= 0);
  260.                             lowerBounds[b] = max(lowerBounds[b], coeff);
  261.                         }
  262.                     }
  263.                 } else if (numGt == count - 1 && rows[j][LIMIT - 1] < 0) {
  264.                     for (i64 b = 0; b < LIMIT - 1; b++) {
  265.                         if (rows[j][b] < 0) {
  266.                             int coeff = (-rows[j][LIMIT - 1] - rows[j][b] - 1) / -rows[j][b];
  267.                             assert(coeff >= 0);
  268.                             lowerBounds[b] = max(lowerBounds[b], coeff);
  269.                         }
  270.                     }
  271.                
  272.                 } else {
  273.                     for (i64 b = 0; b < LIMIT - 1; b++)
  274.                         if (rows[j][b] != 0)
  275.                             upperBounds[b] = min(upperBounds[b], limit);
  276.                 }
  277.             }
  278.         }
  279.         if (removedZeros) {
  280.             if (isPrep) {
  281.                 for (auto z = 0; z < removedZeros; z++) {
  282.                     i64 zeroInd = zeroInds[z];
  283.                     Vec newRow{};
  284.                     newRow[zeroInd] = 1;
  285.                     rows.push_back(newRow);
  286.                 }
  287.             }
  288.             return gaussian(rows, limit);
  289.         }
  290.         array<int, 16> pivots;
  291.         int pp = 0;
  292.         for (int i = 0; i < rows.size(); i++) {
  293.             auto s = simplify(rows[i]);
  294.             if (s < 0)
  295.                 return errorResult;
  296.             if (s > 1)
  297.                 pivots[pp++] = i;
  298.         }
  299.         for (int i = 0; i < pp; i++) {
  300.             for (int j = i+1; j < pp; j++) {
  301.                 auto row = rows[pivots[j]] + rows[pivots[i]];
  302.                 auto s = simplify(row);
  303.                 if (s < 0)
  304.                     return errorResult;
  305.             }
  306.         }
  307.         if (isPrep)
  308.             return {-1, -1, -1, singleInds, singleTotal};
  309.         int candidate = -1;
  310.         for (i64 b = 0; b < buttons; b++) {
  311.             if (upperBounds[b] == INT_MAX)
  312.                 continue;
  313.             if (lowerBounds[b] > upperBounds[b])
  314.                 return errorResult;
  315.             if (candidate == -1 || (upperBounds[b] - lowerBounds[b]) < (upperBounds[candidate] - lowerBounds[candidate])) {
  316.                 candidate = b;
  317.             }
  318.         }
  319.         //pmat(rows);
  320.         if (candidate == -1) {
  321.             return {-1, 0, -1, singleInds, singleTotal};
  322.         }
  323.         //print("--");
  324.         //pmat(rows);
  325.         // Compute finer upper and lower bounds
  326.         for (i64 repeat = 0; repeat < 1; repeat++) {
  327.             for (i64 j = 0; j < rows.size(); j++) {
  328.                 i64 minVal = 0;
  329.                 i64 maxVal = 0;
  330.                 for (i64 b = 0; b < buttons; b++) {
  331.                     if (rows[j][b] < 0) {
  332.                         minVal += i64(upperBounds[b]) * rows[j][b];
  333.                         maxVal += i64(lowerBounds[b]) * rows[j][b];
  334.                     } else if (rows[j][b] > 0) {
  335.                         minVal += i64(lowerBounds[b]) * rows[j][b];
  336.                         maxVal += i64(upperBounds[b]) * rows[j][b];
  337.                     }
  338.                 }
  339.                 if (rows[j][LIMIT -1] < minVal || rows[j][LIMIT -1] > maxVal)
  340.                     return errorResult;
  341.                 for (i64 b = 0; b < buttons; b++) {
  342.                     if (rows[j][b] == 0)
  343.                         continue;
  344.                     i64 minRest, maxRest, maxCur, minCur;
  345.                     if (rows[j][b] < 0) {
  346.                         minRest = minVal - i64(upperBounds[b]) * rows[j][b];
  347.                         maxRest = maxVal - i64(lowerBounds[b]) * rows[j][b];
  348.                         maxCur = (rows[j][LIMIT -1] - maxRest) / rows[j][b];
  349.                         minCur = (rows[j][LIMIT -1] - minRest + rows[j][b] + 1) / rows[j][b];
  350.                     } else if (rows[j][b] > 0) {
  351.                         minRest = minVal - i64(lowerBounds[b]) * rows[j][b];
  352.                         maxRest = maxVal - i64(upperBounds[b]) * rows[j][b];
  353.                         maxCur = (rows[j][LIMIT -1] - minRest) / rows[j][b];
  354.                         minCur = (rows[j][LIMIT -1] - maxRest + rows[j][b] - 1) / rows[j][b];
  355.                     }
  356.                     if (maxCur < minCur)
  357.                         return errorResult;
  358.                     if (maxCur < 0)
  359.                         return errorResult;
  360.                     if (maxCur < upperBounds[b])
  361.                         upperBounds[b] = maxCur;
  362.                     if (minCur > lowerBounds[b])
  363.                         lowerBounds[b] = minCur;
  364.                    
  365.                 }
  366.             }
  367.         }
  368.  
  369.         return {candidate, upperBounds[candidate], lowerBounds[candidate], singleInds, singleTotal};
  370.     }
  371.  
  372.     array<vector<Vec>, 16> cache;
  373.     size_t cacheSize = 0;
  374.  
  375.     auto alloc() {
  376.         if (cacheSize == 0) {
  377.             return vector<Vec>{};
  378.         } else {
  379.             auto v = move(cache[--cacheSize]);
  380.             v.clear();
  381.             return v;
  382.         }
  383.     }
  384.     void dealloc(vector<Vec>&& v) {
  385.         cache[cacheSize++] = move(v);
  386.     }
  387.  
  388.    
  389.     bool feasibleSlow(vector<Vec>& rows, int freeVar, int maxVal, int minVal, int limit, int depth) {
  390.         for (int val = minVal; val <= maxVal; val++) {
  391.             vector cur = alloc();
  392.             cur.insert(cur.end(), rows.begin(), rows.end());
  393.             Vec row{};
  394.             row[freeVar] = 1;
  395.             row[LIMIT - 1] = val;
  396.             cur.push_back(row);
  397.             if (feasible(cur, limit, depth + 1)) {
  398.                 dealloc(move(cur));
  399.                 return true;
  400.             }
  401.             dealloc(move(cur));
  402.         }
  403.         return false;
  404.     }
  405.    
  406.  
  407.     bool feasible(vector<Vec>& rows, int limit, int depth = 0) {
  408.         auto [freeVar, maxVal, minVal, singleInds, singleTotal] = gaussian(rows, limit);
  409.         if (freeVar < 0) {
  410.             return maxVal == 0;
  411.         }
  412.         //if (depth == 0) {
  413.         //    print("feasible", depth, freeVar, maxVal, minVal);
  414.         //    pmat(rows);
  415.         //    print("----");
  416.         //}
  417.         return feasibleSlow(rows, freeVar, maxVal, minVal, limit, depth);
  418.     }
  419.  
  420.     int solvePart2() {
  421.         vector<Vec> rows;
  422.         for (i64 j = 0; j < jolts; j++) {
  423.             Vec row{};
  424.             for (auto b : reverse[j]) row[b] = 1;
  425.             row[LIMIT - 1] = machine.joltage[j];
  426.             rows.push_back(row);
  427.         }
  428.         //pmat(rows);
  429.         auto [freeVar, maxVal, minVal, singleInds, singleTotal] = gaussian(rows);
  430.         //print("gaussianed");
  431.         //pmat(rows);
  432.  
  433.         int val = 0;
  434.         for (auto j : machine.joltage)
  435.             val = max<int>(val, j);
  436.         val = max<int>(val, singleTotal);
  437.         val -= singleTotal;
  438.         for (; true; val++) {
  439.             //print("val", val);
  440.             auto cur = alloc();
  441.             cur.insert(cur.end(), rows.begin(), rows.end());
  442.             Vec row{};
  443.             for (i64 b = 0; b < buttons; b++) {
  444.                 if (!((singleInds >> b) & 1))
  445.                     row[b] = 1;
  446.             }
  447.             row[LIMIT - 1] = val;
  448.             cur.push_back(row);
  449.             if (feasible(cur, val)) {
  450.                 dealloc(move(cur));
  451.                 return val + singleTotal;
  452.             }
  453.             dealloc(move(cur));
  454.         }
  455.     }
  456.  
  457.     i64 solvePart1() {
  458.         i64 best = INT_MAX;
  459.         iterateSets(machine.buttons.size(), [&](uint64_t b) {
  460.             unsigned val = 0;
  461.             iterateBits(b, [&](i64 ind) {
  462.                 val ^= machine.buttons[ind];
  463.                 return true;
  464.             });
  465.             if (val == machine.target) {
  466.                 best = popcount(b);
  467.                 return false;
  468.             }
  469.             return true;
  470.         });
  471.         return best;
  472.     }
  473. };
  474.  
  475. int main() {
  476.     auto lines = readLines(cin);
  477.     vector<Machine> machines;
  478.     for (auto& l : lines) {
  479.         auto parts = split(l, " ");
  480.         Machine m;
  481.         m.len = parts[0].size() - 2;
  482.         for (i64 i = 1; i < parts[0].size() - 1; i++)
  483.             m.target |= (parts[0][i] == '#') << (i - 1);
  484.         for (i64 i = 1; i < parts.size() - 1; i++) {
  485.             auto ss = string_view{parts[i]}.substr(1, parts[i].size() - 2);
  486.             auto ints = splitInts(ss, ",");
  487.             i64 btn = 0;
  488.             for (auto v : ints)
  489.                 btn |= (1ll << v);
  490.             m.buttons.push_back(btn);
  491.         }
  492.         m.joltage = splitInts(string_view{parts.back()}.substr(1, parts.back().size() - 2), ",");
  493.         machines.push_back(move(m));
  494.     }
  495.     //print(machines);
  496.     print("Hello world");
  497.    
  498.     auto st = std::chrono::steady_clock::now();
  499.    
  500.     i64 totBest = 0;
  501.     i64 solTot = 0;
  502.     for (size_t m = 0; m < machines.size(); m++) {
  503.         auto& machine = machines[m];
  504.         //print(machine);
  505.         Solver solver(machine);
  506.         totBest += solver.solvePart1();
  507.  
  508.         //auto stc = std::chrono::steady_clock::now();
  509.         int sol = solver.solvePart2();
  510.         //auto enc = std::chrono::steady_clock::now();
  511.         //print(m, "Solver:", sol, (enc - stc) / 1.0ns, "ns");
  512.         print(m, "Solver:", sol);
  513.         solTot += sol;
  514.     }
  515.  
  516.     print("part1:", totBest);
  517.     print("part2:", solTot);
  518.  
  519.     auto en = std::chrono::steady_clock::now();
  520.     auto diff = en - st;
  521.     print("Time:", (en - st) / 1.0ms, "ms");
  522.  
  523.  
  524.     return 0;
  525. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!