explicit HintStrategySetPacking()

in csrc/InfoBot.cc [791:895]

• 84 lines of code
• 20 McCabe index (conditional complexity)

    explicit HintStrategySetPacking(const HandInfo& info) {
        // Make a matrix with info.size() rows and NUMCOLORS columns.
        // Set each cell (r,c) to 1 if the r'th card could be of color c.
        // Find the max-cardinality set of disjoint rows; this is the
        // NP-complete "set-cover" problem, so we just do brute force
        // search over the at-most-32 possible row-sets.
        // Each row in the max-cardinality set corresponds to a
        // card in the hand where touching that card with a color hint
        // cannot possibly be confused with any other hint generated
        // by this algorithm.
        //
        int nrows = info.size();
        unsigned rowsetmax = (1u << nrows);
        unsigned largest_disjoint_color_rowset = 1;
        int best_cardinality = 1;
        for (unsigned rowset = 3; rowset < rowsetmax; ++rowset) {
            int cardinality_of_rowset = __builtin_popcount(rowset);
            if (cardinality_of_rowset <= best_cardinality) {
                // Go on only if this rowset has a chance of being a new "best".
                continue;
            }
            bool rowset_is_disjoint = true;
            unsigned kmask = 0;
            for (int i=0; i < nrows; ++i) {
                if (rowset & (1u << i)) {
                    info[i].for_each_possibility([&](Card card) {
                        unsigned km = (1u << int(card.color));
                        if (kmask & km) {
                            rowset_is_disjoint = false;
                        }
                        kmask |= km;
                    });
                }
            }
            if (rowset_is_disjoint) {
                best_cardinality = cardinality_of_rowset;
                largest_disjoint_color_rowset = rowset;
            }
        }

        // Also perform the same operation, but for value hints.
        //
        unsigned largest_disjoint_value_rowset = 1;
        best_cardinality = 1;
        for (unsigned rowset = 3; rowset < rowsetmax; ++rowset) {
            int cardinality_of_rowset = __builtin_popcount(rowset);
            if (cardinality_of_rowset <= best_cardinality) {
                // Go on only if this rowset has a chance of being a new "best".
                continue;
            }
            bool rowset_is_disjoint = true;
            unsigned vmask = 0;
            for (int i=0; i < nrows; ++i) {
                if (rowset & (1u << i)) {
                    info[i].for_each_possibility([&](Card card) {
                        unsigned vm = (1u << int(card.value));
                        if (vmask & vm) {
                            rowset_is_disjoint = false;
                        }
                        vmask |= vm;
                    });
                }
            }
            if (rowset_is_disjoint) {
                best_cardinality = cardinality_of_rowset;
                largest_disjoint_value_rowset = rowset;
            }
        }

        // Now generate our mapping from hints to ints.
        std::fill(color_to_int_, std::end(color_to_int_), -1);
        std::fill(value_to_int_, std::end(value_to_int_), -1);
        count_ = 0;
        for (int i = 0; i < nrows; ++i) {
            if (largest_disjoint_color_rowset & (1u << i)) {
                info[i].for_each_possibility([&](Card card) {
                    color_to_int_[card.color] = count_;
                });
                count_ += 1;
            }
            if (largest_disjoint_value_rowset & (1u << i)) {
                info[i].for_each_possibility([&](Card card) {
                    value_to_int_[card.value] = count_;
                });
                count_ += 1;
            }
        }

        // Some colors and values might not be touched by any of the rows
        // in our largest disjoint rowset. Permit those hints to be given,
        // since their "overt" information might be useful to the hintee.
        int cur_block = 0;
        for (Color k = RED; k <= BLUE; ++k) {
            if (color_to_int_[k] == -1) {
                color_to_int_[k] = cur_block;
                cur_block = (cur_block + 1) % count_;
            }
        }
        for (int v = 1; v <= 5; ++v) {
            if (value_to_int_[v] == -1) {
                value_to_int_[v] = cur_block;
                cur_block = (cur_block + 1) % count_;
            }
        }
    }