Slow execution time of search algorithm

Question

I have solved a problem of a game named 'Set'. The full problem is detailed on it's website: https://www.urionlinejudge.com.br/judge/en/problems/view/1090

However my code for the search algorithm is too slow, I'd like to achieve something around \$O(n)\$. How can I make SetGameManager::CountSet() better?

This is not the full code, it's just so that you have an idea of what's going on:

#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>

enum TYPE{
    SQUARE,
    CIRCLE,
    TRIANGLE,
};

struct _card
{
    TYPE type;
    int amount;
    _card( int a, TYPE t) { type = t; amount = a;};
};


inline bool canMatch(_card a, _card b)
{
    return((a.type == b.type && a.amount != b.amount) || (a.type == b.type && a.amount == b.amount) );
}

inline bool canMatch3(_card a, _card b, _card c)
{
    return((a.type == b.type && a.type == c.type)
           && ((a.amount != b.amount && b.amount != c.amount && a.amount != c.amount) ||
               ( a.amount == b.amount && a.amount == c.amount )));
}


inline bool cannotMatch(_card a, _card b)
{
    return(a.type != b.type && a.amount != b.amount);
}

inline bool cannotMatch3(_card a, _card b, _card c)
{
    return((a.type != b.type && b.type != c.type && a.type != c.type) &&
           (a.amount != b.amount && b.amount != c.amount && a.amount != c.amount));
}


class SetGameManager {
public:
    std::vector<_card> gameCards;
}

inline unsigned int SetGameManager::CountSet()
{
    unsigned int SetMatches = 0;

    unsigned int i1 = 0;

    std::sort(this->gameCards.begin(), this->gameCards.end());

    while(gameCards.size() > 2)
    {
        auto continue_outer_loop(true);
        for(unsigned int i2=1; continue_outer_loop && (i2<gameCards.size()); i2++)
        {
            if(i2 == 2) continue;
            auto const p_match_3_func
            (
                cannotMatch(gameCards.at(i1), gameCards.at(i2))
                ?
                &cannotMatch3
                :
                &canMatch3
            );
            for(unsigned int i3=2; i3<gameCards.size(); i3++)
            {
                if((*p_match_3_func)(gameCards.at(i1), gameCards.at(i2), gameCards.at(i3)))
                {
                    SetMatches++;
                    gameCards.erase(gameCards.begin()+i3);
                            gameCards.erase(gameCards.begin()+i2);
                    continue_outer_loop = false;
                    break;
                }
            }
        }
        gameCards.erase(gameCards.begin());
    }


    return SetMatches;
}

Answer 1

I think in this case the answer is to count rather than sort and search. I would create a struct that simply keeps count of how many cards of each type. Something like this:

struct cardCounts {
    unsigned long numOneCircles;
    unsigned long numTwoCircles;
    unsigned long numThreeCircles;
    unsigned long numOneSquares;
    unsigned long numTwoSquares;
    unsigned long numThreeSquares;
    unsigned long numOneTriangles;
    unsigned long numTwoTriangles;
    unsigned long numThreeTriangles;
};

You can initialize them all to 0, then increment each one as you read a card of that type from the input.

Once you've read all the cards, you can make combinations from them. For example, you can figure out how many sets containing 3 cards of 1 circle are possible by simply dividing numOneCircles by 3. Then the same for each other member of the struct.

Next, you can find combinations where 1 property is the same and the other are all different. So either the shape is the same but the counts are different, or the counts are the same and the shapes are different. You can take the minimum of numOneCircles, numTwoCircles, and numThreeCircles, and that's how many sets you can make with 1 card from each stack. Do the same for squares then triangles. Then switch it so the number stays the same but the shapes are different - so across numOneCircles, numOneSquares, and numOneTriangles.

Finally, find all combinations where both the shape and the number are different. This one is a little trickier, but not too bad. Check for one circle, two squares, three triangles. (Again, taking the min of those 3 as the result.) Then one circle, two triangles, three squares. There are 9 combinations you have to cover (I think?).

This should be O(n) in time and O(1) in space, as you'll only read through the data once when counting up the amounts, and you'll only ever use the 9 elements to store the sums.