5
\$\begingroup\$

I am having a challenge problem. I have solved the problem but my solution is slow.

The problem is basically the distribution of scores among players. e.g for a 2 player game the possible scorecards combination is 2 because either player can win \$\{0,1\}\$ or \$\{1,0\}\$ while for a 3 player game the possible scorecards combination is 7: \$\{1,1,1\}\$, \$\{0,1,2\}\$, \$\{0,2,1\}\$, \$\{1,0,2\}\$, \$\{1,2,0\}\$, \$\{2,0,1\}\$, \$\{2,1,0\}\$ as a single player can win maximum by 2 other players and minimum by no one.

As I can guess the reason my code is slow is because I am trying to find all valid scorecards and displaying the number.

  1. In my first attempt I tried to find all possible combination of scorecards and storing them in a vector, then removing the invalid combinations. This approach was slow.

  2. In my second attempt I applied some checks such as that in a series no 2 players can have a score of \$0\$ i.e \$\{0,0,...\}\$ etc cause it is logically not possible. Because if a player doesn't win from any other player then all other player must have won from that particular player so every other player will have at least 1 win. It reduced my calculations by almost 50-60% but it is still slow.

I think my code/logic can be improved: instead of finding all valid combinations, I may find the number of valid combinations with some kind of formula.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

bool hasElement(vector<int>& arr, const int& element)
{
    vector<int>::iterator found = find(arr.begin(), arr.end(), element);
    if (found != arr.end())
        return true;
    return false;
}

int sumElements(const vector<int>& arr)
{
    int s = accumulate(arr.begin(), arr.end(), 0);
    return s;
}

bool isPossible(vector<int>& arr, const int& sum, const int& nMax)
{
    if (hasElement(arr, -1) || *max_element(arr.begin(), arr.end()) > nMax)
        return false;
    int s = sumElements(arr);
    if (s == sum)
        return true;
    return false;
}

int rangeSum (int start, int end)
{
    int sum = 0;
    for (int i = start; i < end; i++)
        sum += i;
    return sum;
}

int size = 0;

int maxSum;
int n;
int maxZero;
int maxMax;
int maxAllowed;
int range;

vector<int> tempVec;
vector<vector<int>> mainVec;


void printTempVec()
{
    for(int i = 0; i < tempVec.size(); i++)
    {
        if (tempVec[i] >= 0)
            cout << tempVec[i] << " ";
        else
            cout << -1 << " ";
    }
    cout << endl;
}

int summation(const int& places, const int& max)
{
    int s = 0;
    for (int i = 0; i < places; i++)
    {

    }
    return s;
}

bool isValid(vector<int>& arr, const int& nMax)
{
    int sz = 0;
    int sm = 0;
    for (int i = 0; i < arr.size(); i++)
    {
        if (arr[i] == nMax)
            sm++;
        if (sm > 1)
            return false;
    }
    return true;
}

void findNum(int i, int max, int rSum, int mZero, int mMax)
{
    max = max > maxAllowed ? maxAllowed : max;

    if (max == 0)
        mZero++;
    if (mZero > 1)
        return;
    if (max == -1)
        return;

    tempVec[i] = max;

    int tempSum = rSum - max;
    max--;

    if(i != n)
    {
        findNum(i + 1, tempSum, tempSum, mZero, mMax);
        findNum(i, max, rSum, mZero, mMax);
    }
    else if(i == n)
    {
        if (isPossible(tempVec, range, maxAllowed) && isValid(tempVec, maxAllowed))
            mainVec.push_back(tempVec);
        else
            printTempVec();
        maxSum++;
    }
}

int missing(const vector<int>& temp)
{
    int s = 0;
    for (int i = 0; i < temp.size(); i++)
    {
        if (temp[i] == -1)
            s++;
    }
    return s;
}

int remainingSum(const vector<int>& temp)
{
    int s = rangeSum(0, temp.size());
    for (int i = 0; i < temp.size(); i++)
    {
        if (temp[i] != -1)
            s -= temp[i];
    }
    return s;
}

int main()
{
    vector<vector<int>> mainArray;

    vector<int>temp;
    for (int i = 0; i < 3; i++)
        temp.push_back(-1);
    mainArray.push_back(temp);

    for (int i = 0; i < mainArray.size(); i++)
    {
        size = mainArray[i].size();
        tempVec.clear();
        tempVec.resize(size);
        maxZero = 0;
        maxSum = 0;
        maxMax = 0;
        int rSum = remainingSum(mainArray[i]);
        int tSum = rangeSum(0, mainArray[i].size());
        range = tSum;
        n = missing(mainArray[i]) - 1;
        maxAllowed = mainArray[i].size() - 1;

        if (isPossible(mainArray[i], tSum, maxAllowed))
            maxSum = 1;
        else
            findNum(0, rSum, rSum, 0, maxMax);

        cout << maxSum << endl;
        cout << mainVec.size() << endl;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ a few notes on your code: 1. There's no reason to pass an integer as a const-ref. Just pass it by value. 2. Instead of if(x==y) return true; return false; you simply can do return x==y. 3. Instead of int s = accumulate(…); return s; simply do return accumulate(…). 4. Try not to use global variables; 5. In summation() is an loop without a body. Therefore that function doesn't have an effect. 6. vector<vector<int>> is only possible in C++0x. Are you allowed to use it? 7. A vector is not an array. Why do you call your vectors arr? \$\endgroup\$ – Polybos Feb 21 '12 at 14:04
  • \$\begingroup\$ @Polybos Thanks for your comment. I improved the code as you suggested. I used global variables cause of the recursive function findSum(...) because it requires same values for all calls. Others don't have any effect on the speed though. Will really appreciate if you can provide more insight on improving the logic for speeding it up. \$\endgroup\$ – Azeem Feb 21 '12 at 14:30
  • \$\begingroup\$ Can you describe why it is to slow and how fast it is supposed to be? And maybe explain the problem a little so that everybody understands what this is all about. \$\endgroup\$ – inf Feb 21 '12 at 21:37
  • \$\begingroup\$ @bamboon Thanks for your comment. I have updated the question. \$\endgroup\$ – Azeem Feb 22 '12 at 14:42
6
\$\begingroup\$

Some more comments.

  1. The function rangeSum() can be optimized to:

    int rangeSum(int start, int end)
    {
      return start*(start-1)/2 + end*(end-1)/2 - 2;
    }
    

    which is much better since it's O(1) and not O(n).

  2. The function hasElement() can be reimplemented to:

    template<typename T>
    inline bool hasElement(const vector<T>& vec, T elem)
    {
      return std::find(vec.begin(), vec.end(), elem) != vec.end();
    }
    
  3. Assuming you can use C++0x, missing() can be reimplemented to:

    template<typename T>
    inline std::size_t missing(const std::vector<T>& tmp)
    {
      return std::count_if(tmp.begin(), tmp.end(), [](T elem) {
        return elem == -1;
      });
    }
    
  4. The variables maxMax and size aren't used globally. Just declare them locally.

  5. You might think of using a functor FindNum – something like:

    struct FindNum
    {
      void operator()(int i, int max, int rSum, int mZero, int mMax)
      {
        /* … */
      }
    
      int maxSum, n, maxAllowed, range;
      std::vector<int> tempVec;
      std::vector<std::vector<int>> mainVec;
    };
    

    You really shouldn't use global variables.

\$\endgroup\$
  • \$\begingroup\$ Really appreciate your help. These changes have been made but there is no change in the performance. Major work is being done in FindNum. I want to improve FindNum so that it can run efficiently. \$\endgroup\$ – Azeem Feb 21 '12 at 19:16
3
\$\begingroup\$
  • The names isPossible() and missing() are not very good at all. What could be possible? What could be missing? Use accurate names; don't leave the reader guessing.

  • summation() doesn't appear to be doing anything. It initializes s to 0, has a loop that does nothing with s, then returns it. Essentially, it will always return 0. You could just get rid of this function if you aren't needing to fill in the loop body anymore.

  • Why's all this hanging around in global (and in between other functions)?

    int size = 0;
    
    int maxSum;
    int n;
    int maxZero;
    int maxMax;
    int maxAllowed;
    int range;
    
    vector<int> tempVec;
    vector<vector<int>> mainVec;
    

    It appears that you're using all of this in main(), so it should just be declared or initialized there. Avoid global variables as they could introduce unexpected bugs anywhere in the code.

  • This can be reduced quite a bit:

    vector<vector<int>> mainVec;
    
        vector<int>temp;
        for (int i = 0; i < 3; i++)
            temp.push_back(-1);
        mainVec.push_back(temp);
    

    You can initialize temp and eliminate the loop:

    std::vector<int> temp(3, -1); // elems: -1, -1, -1
    vector<vector<int>> mainVec(temp);
    
\$\endgroup\$

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.