#include "advent.hpp"
#include <bit>
#include <chrono>
#include <format>
#include <queue>
#include <numeric>
#include <utility>


struct Machine {
    i64 len = 0;
    i64 target = 0;
    vector<i64> buttons{};
    vector<i64> joltage{};
};

ostream& printBits(ostream& o, i64 v, i64 len) {
    for (i64 i = len - 1; i >= 0; i--) {
        o << ((v & (1LL << i)) ? '1' : '0');
    }
    return o;
}

ostream& operator<<(ostream& os, const Machine& m) {
    os << "(" << m.len << ", ";
    printBits(os, m.target, m.len);
    os << ", ";
    bool first = true;
    os << "[";
    for (auto b : m.buttons) {
        if (first) first = false; else os << ", ";
        printBits(os, b, m.len);
    }
    os << "], ";
    os << m.joltage;
    os << ")";
    return os;
}

void iterateSets(int n, auto&& callback) {
    uint64_t limit = 1ull << n;  // assumes n <= 63

    for (int k = 1; k <= n; ++k) {
        uint64_t s = (1ull << k) - 1;
        while (s < limit) {
            if (!callback(s))
                return;
            uint64_t c = s & -s;
            uint64_t r = s + c;
            s = (((r ^ s) >> 2) / c) | r;
        }
    }
}

void iterateBits(uint64_t bits, auto&& callback) {
    while (bits) {
        uint64_t t = bits & -bits;
        int r = std::countr_zero(t);
        if (!callback(r))
            return;
        bits &= bits - 1;
    }
}

constexpr size_t LIMIT = 16;
using Vec = array<int16_t, LIMIT>;

Vec operator+(const Vec& a, const Vec& b) {
    Vec res;
    for (size_t i = 0; i < LIMIT; i++)
        res[i] = a[i] + b[i];
    return res;
}
Vec operator-(const Vec& a, const Vec& b) {
    Vec res;
    for (size_t i = 0; i < LIMIT; i++)
        res[i] = a[i] - b[i];
    return res;
}
Vec operator*(const Vec& a, int16_t b) {
    Vec res;
    for (size_t i = 0; i < LIMIT; i++)
        res[i] = a[i] * b;
    return res;
}

void fastSwap(Vec& a, Vec& b) {
    auto tmp = a;
    a = b;
    b = tmp;
}


struct Solver {
    const Machine& machine;
    int buttons;
    int jolts;
    array<vector<int>, LIMIT> forward;
    array<vector<int>, LIMIT> reverse;

    Solver(const Machine& machine) : machine(machine) {
        buttons = machine.buttons.size();
        jolts = machine.joltage.size();
        assert(buttons + 1 <= forward.size());
        assert(jolts + 1 <= reverse.size());
        for (i64 b = 0; b < machine.buttons.size(); b++) {
            for (i64 j = 0; j < machine.joltage.size(); j++) {
                if (machine.buttons[b] & (1ll << j)) {
                    reverse[j].push_back(b);
                    forward[b].push_back(j);
                }
            }
        }
    }

    void simplify(Vec& v) {
        int g = 0;
        for (auto x : v)
            g = gcd(g, x);
        if (g > 1) {
            for (auto& x : v)
                x /= g;
        }
        int first = 0;
        for (; first < buttons; first++) {
            if (v[first] != 0)
                break;
        }
        if (first < buttons && v[first] < 0) {
            for (auto& x : v)
                x = -x;
        }
    }
    static void pmat(const span<Vec>& rows) {
        for (auto& row : rows) {
            for (i64 i = 0; i < LIMIT; i++) {
                cout << format("{:4}", row[i]);
            }
            cout << endl;
        }
    }

    [[gnu::noinline]] pair<int, int> gaussian(vector<Vec>& rows, int limit = -1) {
        bool doClean = limit >= 0;
        // Run gaussian elimination
        // Return a free variable and the maximum value for that variable
        i64 n = rows.size();
        i64 m = buttons;
        for (i64 h = 0, k = 0; h < n && k < m; k++) {
            // Find the kth pivot
            i64 i_pivot = h;
            for (i64 i = h; i < n; i++) {
                if (rows[i][k] != 0) {
                    i_pivot = i;
                    break;
                }
            }
            if (rows[i_pivot][k] == 0)
                continue; // No pivot in this column
            // Swap rows
            fastSwap(rows[h], rows[i_pivot]);
            // For all rows below pivot
            for (i64 i = 0; i < h; i++) {
                if (rows[i][k] != 0) {
                    auto g = gcd(rows[h][k], rows[i][k]);
                    rows[i] = rows[i] * (rows[h][k] / g) - rows[h] * (rows[i][k] / g);
                }
            }
            for (i64 i = i_pivot + 1; i < n; i++) {
                if (rows[i][k] != 0) {
                    auto g = gcd(rows[h][k], rows[i][k]);
                    rows[i] = rows[i] * (rows[h][k] / g) - rows[h] * (rows[i][k] / g);
                }
            }
            h++;
        }
        pair<int, int> candidate = {INT_MAX, INT_MAX};
        array<int, 16> zeroInds{};
        size_t removedZeros = 0;
        for (i64 j = 0; j < rows.size(); j++) {
            int count = 0;
            int index = -1;
            int numSame = 0;
            int numGt = 0;
            for (i64 b = 0; b < LIMIT - 1; b++) {
                if (rows[j][b] != 0) {
                    count++;
                    index = b;
                    // Does it face same direction as the constant term
                    numGt += rows[j][b] > 0;
                    numSame += ((rows[j][b] >= 0) == (rows[j][LIMIT - 1] >= 0)) || (rows[j][LIMIT - 1] == 0);
                }
            }
            if (count == 0) {
                if (rows[j][LIMIT - 1] != 0)
                    return {-1, -1}; // No solution
                rows[j] = rows.back();
                rows.pop_back();
                j--;
                continue;
            }
            if (numSame == 0) {
                // If none of our variables face the same direction as the constant term, no solution, as variables need to be positive
                return {-1, -1};
            }
            if (count == 1) {
                // We need integer solutions
                if (rows[j][LIMIT - 1] % rows[j][index] != 0)
                    return {-1, -1};
                auto val = rows[j][LIMIT - 1] / rows[j][index];
                // We need >= 0 solutions
                if (val < 0)
                    return {-1, -1};
                if (doClean) {
                    rows[j] = rows.back();
                    rows.pop_back();
                    j--;
                }
            } else {
                candidate = min(candidate, {limit, index});

                if (numSame == count && (numGt == 0 || numGt == count)) {
                    // All variables face the same direction as the constant term
                    // We can compute a proper maximum
                    for (i64 b = 0; b < LIMIT - 1; b++) {
                        if (rows[j][b] != 0) {
                            int coeff = rows[j][LIMIT - 1] / rows[j][b];

                            if (coeff == 0) {
                                for (i64 j2 = 0; j2 < rows.size(); j2++)
                                    rows[j2][b] = 0;
                                assert(removedZeros < zeroInds.size());
                                zeroInds[removedZeros++] = b;
                                continue;
                            }

                            candidate = min(candidate, {coeff, b});
                        }
                    }
                }
            }
        }
        if (removedZeros) {
            if (!doClean) {
                for (auto z = 0; z < removedZeros; z++) {
                    i64 zeroInd = zeroInds[z];
                    Vec newRow{};
                    newRow[zeroInd] = 1;
                    rows.push_back(newRow);
                }
            }
            return gaussian(rows, doClean);
        }
        for (auto& row : rows)
            simplify(row);
        if (candidate.first != INT_MAX) {
            return {candidate.second, candidate.first};
        }
        return {-1, 0};
    }

    array<vector<Vec>, 16> cache;
    size_t cacheSize = 0;

    auto alloc() {
        if (cacheSize == 0) {
            return vector<Vec>{};
        } else {
            auto v = move(cache[--cacheSize]);
            v.clear();
            return v;
        }
    }
    void dealloc(vector<Vec>&& v) {
        cache[cacheSize++] = move(v);
    }


    bool feasibleSlow(vector<Vec>& rows, int freeVar, int maxVal, int limit) {
        for (int val = 0; val <= maxVal; val++) {
            vector cur = alloc();
            cur.insert(cur.end(), rows.begin(), rows.end());
            Vec row{};
            row[freeVar] = 1;
            row[LIMIT - 1] = val;
            cur.push_back(row);
            if (feasible(cur, limit)) {
                dealloc(move(cur));
                return true;
            }
            dealloc(move(cur));
        }
        return false;
    }


    bool feasible(vector<Vec>& rows, int limit) {
        auto [freeVar, maxVal] = gaussian(rows, limit);
        if (freeVar < 0) {
            return maxVal == 0;
        }
        return feasibleSlow(rows, freeVar, maxVal, limit);
    }

    int solve() {
        vector<Vec> rows;
        for (i64 j = 0; j < jolts; j++) {
            Vec row{};
            for (auto b : reverse[j]) row[b] = 1;
            row[LIMIT - 1] = machine.joltage[j];
            rows.push_back(row);
        }
        gaussian(rows);

        int val = 0;
        for (auto j : machine.joltage)
            val = max<int>(val, j);
        for (; true; val++) {
            auto cur = alloc();
            cur.insert(cur.end(), rows.begin(), rows.end());
            Vec row{};
            for (i64 b = 0; b < buttons; b++) row[b] = 1;
            row[LIMIT - 1] = val;
            cur.push_back(row);
            if (feasible(cur, val)) {
                dealloc(move(cur));
                return val;
            }
            dealloc(move(cur));
        }
    }
};

int main() {
    auto lines = readLines(cin);
    vector<Machine> machines;
    for (auto& l : lines) {
        auto parts = split(l, " ");
        Machine m;
        m.len = parts[0].size() - 2;
        for (i64 i = 1; i < parts[0].size() - 1; i++)
            m.target |= (parts[0][i] == '#') << (i - 1);
        for (i64 i = 1; i < parts.size() - 1; i++) {
            auto ss = string_view{parts[i]}.substr(1, parts[i].size() - 2);
            auto ints = splitInts(ss, ",");
            i64 btn = 0;
            for (auto v : ints)
                btn |= (1ll << v);
            m.buttons.push_back(btn);
        }
        m.joltage = splitInts(string_view{parts.back()}.substr(1, parts.back().size() - 2), ",");
        machines.push_back(move(m));
    }
    //print(machines);
    print("Hello world");

    auto st = std::chrono::steady_clock::now();

    i64 totBest = 0;
    i64 solTot = 0;
    for (auto& machine : machines) {
        //print(machine);
        i64 best = INT_MAX;
        iterateSets(machine.buttons.size(), [&](uint64_t b) {
            unsigned val = 0;
            iterateBits(b, [&](i64 ind) {
                val ^= machine.buttons[ind];
                return true;
            });
            if (val == machine.target) {
                best = popcount(b);
                return false;
            }
            return true;
        });
        //print(best);
        totBest += best;

        Solver solver(machine);
        auto sol = solver.solve();
        print("Solver:", sol);
        solTot += sol;
    }

    print("part1:", totBest);
    print("part2:", solTot);

    auto en = std::chrono::steady_clock::now();
    auto diff = en - st;
    print("Time:", (en - st) / 1.0ms, "ms");


    return 0;
}