Count Scorecards challenge problem related to partition number theory

Question

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;
    }
}

Answer 1

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.

Answer 2

• 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);