Looking for SET-free card group. Primitive attempt

set.cpp

// -*- coding: utf-8; compile-command: "scons" -*-

// Hacking over the problem of maximal set of cards not containing "SET"

#include <iostream>
#include <iterator>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>

using namespace std;

/**
 * Single card representation. Templatized to generalize, dimension
 * is the number of features (4 in SET), valcount is the number of possible
 * values per feature (3 in SET).
 *
 * Apart from obvious operations cards handle + and - operations implemented
 * so that the group of cards is SET iff their sum is a 0 card.
 **/
template <short dimension=4, short valcount=3>
class Card
{
public:
    Card()
    {
        for(short *v = values;
            v < values + dimension;
            ++ v)
        {
            *v = 0;
        }
    }
    Card(const Card<dimension, valcount>& card)
    {
        copy(card.values, card.values + dimension, values);
    }
    void printOn(ostream& o) const
    {
        o << "(";
        copy(values, values + dimension, ostream_iterator<short>(o, ""));
        o << ")";
    }
    short& operator[] (unsigned int pos)
    {
        return values[pos];
    }
    bool operator< (const Card<dimension, valcount>& other) const
    {
        const short *his = other.values;
        for(const short* my = values;
            my < values + dimension;
            ++ my, ++ his)
        {
            if( *my < *his )
                return true;
            if( *my > *his )
                return false;
        }
        return false;
    }
    bool operator== (const Card<dimension, valcount>& other) const
    {
        const short *his = other.values;
        for(const short* my = values;
            my < values + dimension;
            ++ my, ++ his)
        {
            if( (*my) != (*his) )
                return false;
        }
        return true;
    }
    Card& incAt(unsigned int pos)
    {
        values[pos] = (values[pos] + 1) % valcount;
        return *this;
    }
    Card& setAt(unsigned int pos, short value)
    {
        values[pos] = value % valcount;
        return *this;
    }
    Card<dimension, valcount>& operator+= (const Card<dimension, valcount>& c)
    {
        const short* his = c.values;
        for( short* my = values;
             my != values + dimension;
             ++ my, ++ his)
        {
            *my = (*my + *his) % valcount;
        }
        return *this;
    }
    Card& operator-= (const Card& c)
    {
        const short *his = c.values;
        for( short *my = values;
             my != values + dimension;
             ++ my, ++ his)
        {
            *my = (valcount + *my - *his) % valcount;
        }
        return *this;
    }
    bool isZero() const
    {
        for( short *my = values;
             my != values + dimension;
             ++ my )
        {
            if (*my)
                return false;
        }
        return true;
    }

private:
    short values[dimension];
};

template <short dimension, short valcount>
ostream& operator<<(ostream& o, const Card<dimension, valcount>& c)
{
    c.printOn(o);
    return o;
}

template <short dimension, short valcount>
Card<dimension, valcount> operator+ (
    const Card<dimension, valcount>& c1,
    const Card<dimension, valcount>& c2)
{
    Card<dimension, valcount> c(c1);
    return c += c2;
}

template <short dimension, short valcount>
Card<dimension, valcount> operator- (
    const Card<dimension, valcount>& c1, const Card<dimension, valcount>& c2)
{
    Card<dimension, valcount> c(c1);
    return c -= c2;
}

/**
 * Group of cards. Used while searching for maximal SET-free groups.
 * Knows not only which cards are in the group, but also which are not yet
 * "forbidden" (because they would make a SET with already present cards).
 **/
template <short dimension=4, short valcount=3>
class CardGroup
{
public:
    typedef Card<dimension, valcount> CardType;

    // Trickery to avoid the need to define all template variations of zero
    static const CardType& zero()
    {
        static CardType zero;
        return zero;
    }

    CardGroup(const CardType& initial=zero())
    {
        populateSpare(zero(), 0);
        // Let's start from 0,0,0 card, by simmetry it doesn't matter
        present.push_back(initial);
        spare.erase(initial);
    }
    CardGroup(const CardGroup& other)
        : present(other.present), spare(other.spare)
    {
    }

    void printOn(ostream& o) const
    {
        o << "{ ";
        copy(present.begin(), present.end(), ostream_iterator<CardType>(o, " "));
        o << endl << "    spare: ";
        copy(spare.begin(), spare.end(), ostream_iterator<CardType>(o, " "));
        o << endl;
        o << "}";
    }

    // Helper operator used inside next method. Remove from candidates (spare)
    // sums of the given card and card specified in the constructor.
    struct ForbidSum
    {
        ForbidSum(set<CardType> &spare_, const CardType& c_)
            : spare(spare_), c(c_)
        {}

        void operator() (const CardType& card)
        {
            CardType removed = zero() - (card + c);
            spare.erase(removed);
        }
        set<CardType> &spare;
        const CardType& c;
        //const CardType zero;
    };

    // Adds given card to the group and forbids any cards which woudl make SET with it
    // and previously present cards. Note: the card is NOT removed from spare, it is assumed
    // it was already picked from there.
    void addToPresent(CardType c)
    {
        for_each(present.begin(), present.end(), ForbidSum(spare, c));
        present.push_back(c);
    }

    // Grabs one of spare cards and returns it, removing from spare at the same time.
    // Can be only called when ! isMaximal
    CardType grabSpare()
    {
        CardType c = * spare.begin();
        spare.erase(spare.begin());
        return c;
    }

    size_t presentCount() const
    {
        return present.size();
    }

    size_t spareCount() const
    {
        return spare.size();
    }

    // Returns true if the group is maximal and nothing can be added to it
    bool
    isMaximal() const
    {
        return spare.empty();
    }

    // Can this group, by any chance, exceed given number?
    bool
    canBeat(size_t currentBest)
    {
        return present.size() + spare.size() > currentBest;
    }

private:

    // Fills "spare" with all possible cards
    void populateSpare(CardType initial, short firstVaryingDim)
    {
        if( firstVaryingDim >= dimension )
        {
            spare.insert(initial);
            return;
        }
        for( short i = 0; i < valcount; ++ i)
        {
            populateSpare(initial, firstVaryingDim + 1);
            initial.incAt(firstVaryingDim);
        }
    }

    vector<CardType> present;
    set<CardType> spare;
};

template <short dimension, short valcount>
ostream& operator<<(ostream& o, const CardGroup<dimension, valcount>& c)
{
    c.printOn(o);
    return o;
}

// Comparable for card groups (used for priority queue). Makes group the bigger,
// the more present items it has, and - after that - the more spare items it has
template< class CardGroup >
struct CardGroupStrengthCompare
{
    // compare(a,b) = true  <===>  a<b
    bool operator() (const CardGroup& g1, const CardGroup& g2)
    {
        int size_diff = int(g1.presentCount()) - int(g2.presentCount());
        if (size_diff > 0)
        {
            return false;
        }
        else if (size_diff < 0)
        {
            return true;
        }
        else
        {
            return g1.spareCount() < g2.spareCount();
        }
    }
};

template <short dimension, short valcount>
CardGroup<dimension, valcount> searchBest(ostream& o)
{
    typedef CardGroup<dimension, valcount> CardGroupType;
    typedef typename CardGroup<dimension, valcount>::CardType CardType;

    unsigned short bestSize = 0;
    CardGroupType bestGroup;

    // All groups not yet checked. Implemented as priority queue
    // to ensure we check biggest items first

    priority_queue<CardGroupType, vector<CardGroupType>, CardGroupStrengthCompare<CardGroupType> > pending;
    pending.push( CardGroupType(CardGroupType::zero()) );

    while( ! pending.empty() )
    {
        CardGroupType group = pending.top();
        pending.pop();

        if (group.isMaximal())
        {
            size_t groupSize = group.presentCount();
            if (groupSize > bestSize)
            {
                o << "New best, size " << groupSize << ": " << group << endl;
                bestSize = groupSize;
                bestGroup = group;
            }
        }
        else
        {
            if (group.canBeat(bestSize))
            {
                CardType c = group.grabSpare();
                // Dwie wersje: używamy c albo nie
                pending.push(group);
                group.addToPresent(c);
                pending.push(group);
            }
        }
    }
    return bestGroup;
}


int main()
{
    {
        CardGroup<2> bset = searchBest<2,3>(cout);
        cout << "Best for 2: " << bset.presentCount() << endl << bset << endl;
    }
    {
        CardGroup<3> bset = searchBest<3,3>(cout);
        cout << "Best for 3: " << bset.presentCount() << endl << bset << endl;
    }
    {
        CardGroup<4> bset = searchBest<4,3>(cout);
        cout << "Best for 4: " << bset.presentCount() << endl << bset << endl;
    }
    return 0;
}