3
\$\begingroup\$

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;
}
\$\endgroup\$
3
  • \$\begingroup\$ This code shouldn't compile as long as I correctly assume that no new member functions can be declared after class is defined. \$\endgroup\$ – Incomputable Jul 21 '17 at 0:19
  • \$\begingroup\$ This is not the full code, it's just so that you have an idea of what's going on. Full code here if you'd like: pastebin.com/z44bR8VL \$\endgroup\$ – snoopy Jul 21 '17 at 0:25
  • \$\begingroup\$ Are you sure the greedy approach works? \$\endgroup\$ – vnp Jul 21 '17 at 4:15
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ An improvement on this idea would be to use an array, e.g. int count[3][3], to store the counts. (For example, count[SQUARE][2] would count the number of cards with 2+1 squares on them.) Then all of the "finding combinations" logic turns into one nested for-loop, instead of repeated cut-and-paste cases; which reduces the likelihood of introducing cut-and-paste typo-bugs. \$\endgroup\$ – Quuxplusone Jul 21 '17 at 7:45
  • \$\begingroup\$ Excellent idea which pointed to the right direction! Accepted! \$\endgroup\$ – snoopy Jul 21 '17 at 22:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.