#include <windows.h>
#include <time.h>

#include <windows.h>
#include <tchar.h>
#include <strsafe.h>

//for timer
#include <iostream>
#include <cstdio>
#include <ctime>
#include <list>


// solution-properities-Common Language Runtime Support (/clr)
//// compile with: /clr
//.net collect garbages!

using namespace System;
using namespace System::Threading;

//#define MAX_THREADS 1
// 49.88900
//#define MAX_THREADS 2
// 26.56700
//#define MAX_THREADS 4
// 13.47900
//#define MAX_THREADS 8
// 13.22800
//#define MAX_THREADS 16
// 13.21300
//#define MAX_THREADS 32
// 13.43100
#include <windows.h>
#include <tchar.h>
#include <strsafe.h>
#define MAX_THREADS 4
#define MAX_SOLUTIONS 1024
ref class solution {
public:
	int count;
	array < Int32 >^ data ;
	void store (int n,int * input);
	void print();
};
void solution::store(int n, int *input) {
	int i = 0;
	data = gcnew array< Int32 >(n);
	for (i=0; i< n; ++i)
		data[i] = input[i];
	count = n;
}
void solution::print(){
	int i = 1;
	Console::WriteLine();
	for (i=1; i<= count; ++i)
	{
		Console::Write( data[i-1] );
		Console::Write( L", " );
	}
}

ref class solutionList
{
public:
	static Mutex^ mut = gcnew Mutex;
	int count;
	array< solution^ >^ data;
	solutionList() {
		count = 0;
		data = gcnew array< solution^ >(MAX_SOLUTIONS);
	}
	void  addSolution(int n, int * input) {
		data[count] = gcnew solution;
		data[count]->store(n,input);
		++count;
	}
	void print() {
		int i = 0;
		for (i =0; i< count;++i) {
			data[i]->print();
		}
	}
};
inline void parsePermutation (int n, int m, int * rindx,int *results) {
	int data[20] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};

	for (int i=0; i<m;++i) {
		int p = rindx[i];
		results[i] = data[p];
		for(int j=p; j<n-i; ++j)
			data[j] = data[j+1];
	}
}

inline void getXs(int n,int *inputs, int * rs) {
	rs[10]=inputs[0], rs[11]=inputs[1], rs[14]=inputs[2], rs[15]=inputs[3], 
		rs[16]=inputs[4], rs[18]=inputs[5], rs[19]=inputs[6];
	rs[17] = 38 -rs[18] -rs[19];
	rs[13] = 38 - rs[14] - rs[15] - rs[16];
	rs[12] = 38 - rs[16] - rs[19];
	rs[8] = 38 -rs[13] - rs[17];
	rs[9] = 38 - rs[8] - rs[10] - rs[11] - rs[12];
	rs[7] = 38 -rs[11] -rs[15] -rs[18];
	rs[3] = 38 - rs[7] -rs[12];
	rs[6] = 38 - rs[3] - rs[10]- rs[14]- rs[17];
	rs[5] = rs[6] -rs[9] +rs[11] -rs[13] +rs[16];
	rs[4] = 38 -rs[9] -rs[14] -rs[18];
	rs[1] = 38 -rs[5] -rs[10] -rs[15] -rs[19];
	rs[2] = 38-rs[1]-rs[3];
}

bool testXs(int n, int * x, int * rs ) {

	int tmp[20] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 
		-1, -1, -1, -1, -1, -1 };

	int i = 0;
	bool tmpflag = true;

	for (i = 1; i<= n ;i++) {
		if ( x[i] <= n && x[i] >= 1) {
			if (tmp[ x[i] ] == -1) {
				tmp[ x[i] ] = x[i];
			} else {
				tmpflag = false;
				break;
			}
		} else {
			tmpflag = false;
			break;
		}
	}

	if (tmpflag == false) 
		return false;

	for (i = 1; i<= n ;i++) {
		if (tmp[ i ] == -1 || tmp[ i ] != i) {
			tmpflag = false;
			break;
		}
		rs[i-1]= x[i];
	}
	return tmpflag;
}

inline void createIndices(int n, int m, int k, int * rindx) {
	int i = 0,dsi =1,j=0;
	for (i=0; i<m; i++) {
		dsi = (k) %(n-i);
		if (dsi==0)
			dsi = n-i;
		rindx[i] = dsi;
		if (k<= n-i) {
			for (j = i+1;j<m;j++)
				rindx[j] = 1;
			break;
		}
		k = (k-1)/(n-i)+1;
	}
}

inline void increaseIndices(int n, int m, int k, int * rindx) {
	int i = 0,dsi =1,j=0;
	for (i=0; i<m; ++i) {
		++rindx[i];
		if (rindx[i] <= n-i) return;
		rindx[i] -= (n-i); 
		// carry forward
		for(j=i+1; j<m;++j) {
			++rindx[j]; 
			if (rindx[j] <= (n-j)) return;
			rindx[j] -= (n-j);
		}
	}
}

public ref class worker 
{
private:
	int id;
	solutionList^ warehouse;
	int t_m;
	int t_n;
	int t_startIndex;
	int t_endIndex;

public:
	// The constructor obtains the state information.
	worker( int number, int new_m, int new_n, 
		int new_startIndex, int new_endIndex,solutionList^ new_warehouse ) 
	{
		t_m  = new_m ;
		t_n  =  new_n;
		t_startIndex  =new_startIndex;
		t_endIndex = new_endIndex;
		warehouse = new_warehouse;
		id = number;
	}

	void ThreadProc() 
	{
		int m = t_m;
		int n = t_n;
		int startIndex = t_startIndex;
		int endIndex = t_endIndex;

		//Console::WriteLine("Thread No. {0} 0/10.",id); 
		int indxs [ 8] ;
		int results[8];
		int results2[20];
		int x[20];
		bool b = false;
		int i = 0;
		int segs = (endIndex- startIndex)/10;
		int segk=0;
		createIndices(n,m,startIndex,indxs);
		indxs[0] --;
		for (i =startIndex; i<=endIndex;++i) {
			increaseIndices(n,m,i, indxs) ;
			parsePermutation (n,m,indxs,results);
			getXs(n,results, results2);
			b = testXs(n, results2, x ) ;

			if (b ) {
				//Console::WriteLine("Thread No. {0} access mutex.",id);
				// store to the warehouse
				warehouse->mut->WaitOne();
				warehouse->addSolution(19,x);
				warehouse->mut->ReleaseMutex();
				//Console::WriteLine("Thread No. {0} store finished.",id);
			}
		}
		//Console::WriteLine("Thread No. {0} 10/10.",id);
	}
};

void main() 
{
	solutionList^ warehouse = gcnew solutionList;
	std::clock_t start;
	double diff;
	int i;

	start = std::clock();
	diff = ( std::clock() - start ) / (double)CLOCKS_PER_SEC;
	printf ("\nTotal time elapsed: %10.5f",diff);

	array< worker^ >^ team = gcnew array< worker^ >(MAX_THREADS);
	array< Thread^ >^ jobs = gcnew array< Thread^ >(MAX_THREADS);

	// Create MAX_THREADS worker threads.
	int total = 1,m=7,n=19;
	int j=0;
	total = 1;
	for (i = 1; i<= m; i++) {
		total *= (n-i+1);
	}
	int segs = total/(MAX_THREADS);

	for( i=0; i<MAX_THREADS; i++ )
	{
		int startIndex=0,endIndex =0;
		if (i< MAX_THREADS -1) {
			startIndex= i*segs +1;
			endIndex = (i+1)*segs;
		} else {
			startIndex= i*segs +1;
			endIndex = total;
		}
		team[i] = gcnew worker(i+1,m,n,startIndex,endIndex,warehouse);
		jobs[i] = gcnew Thread(	gcnew ThreadStart(team[i], &worker::ThreadProc));
	}


	for( i=0; i<MAX_THREADS; i++ )
	{
		jobs[i]->Start();
	} // End of main thread creation loop.
	for( i=0; i<MAX_THREADS; i++ )
	{
		jobs[i]->Join();
	} // End of main thread creation loop.

	diff = ( std::clock() - start ) / (double)CLOCKS_PER_SEC;
	printf ("\nTotal time elapsed: %10.5f",diff);

	warehouse->print();
}