//http://www.expressnewsindia.com/site/katni/C++%20tutorial%206_1,%20Input-Output%20with%20files.htm
//http://www.cppreference.com/cppio/all.html

#include <iostream>
#include <string>
#include <algorithm>  // for sort
#include <vector>
#include <fstream>
#include <cstdlib>
using namespace std;

//bool checkThree(string, istream &, ostream &);
int get6Words(vector< vector<string> > &vw, istream &input);
int get5Words(vector< vector<string> > &vw, istream &input, int, int);
//void findChemWords(vector<string> &, istream &, ostream &);
void printArr(string [][3]);
void printArr2File(ostream &outfile, string [][3]);
void printVvtoFile(ostream &outfile, const vector<vector<string> > &vv, unsigned size);
void bubbleSort(vector<vector<string> > &vw, const unsigned size);
void printVv(const vector<vector<string> > &, unsigned);
bool fit2downWith2across(vector<vector<string> > &vw, string a[][3], unsigned wordCount);
bool gotLastSquare(vector<vector<string> > &vw, string a[][3], unsigned wordCount);

int main() {
    char c;
    //keep a running total of how many words we've got
    unsigned wordCount;
	

    // vw is a vector of vectors of strings...a db structure to hold the chem words
    vector<vector<string> > vw(1200);//(0);
    //vw.clear();  //putting this in caused crash

    // Tap into 6-letter chem words file we built
    ifstream sixChem( "sixChemWords.txt", ios::in); //, ios::in
    if( !sixChem ) {
		cerr << "File could not be opened." << endl;
		exit(1);
    }

    // Build data base structure of vector of vectors of strings, each string a chemical symbol
    wordCount = get6Words(vw, sixChem);	
    cout << vw[wordCount-1][0]; //.end(); 
	
    //vw.erase( &vw[wordCount-1],&vw[wordCount]);  // this creates an error in devcpp but not vc++
    vw.pop_back(); wordCount -= 1;  //Somehow I'm getting a garbage string at the end
    sixChem.close();  //thoughtful cleanup that may not really be needed
    
    // Load up vw chem symbols from 5-letter words in pattern 1-2-2
    ifstream fiveChem122( "fiveChem122.txt", ios::in);
    if( !fiveChem122 ) {
    	cerr << "File could not be opened." << endl;
    	exit(1);  
    }
    
    // grow word count for 5 letter chem words, first in 2-2-1 pattern.
    wordCount = get5Words(vw, fiveChem122, wordCount, 221);
    vw.pop_back(); wordCount -= 1; // garbage at end?!
	
    // Load up vw chem symbols from 5-letter words in pattern 2-1-2
    ifstream fiveChem212( "fiveChem212.txt", ios::in); //, ios::in
    if( !fiveChem212 ) {
    	cerr << "File could not be opened." << endl;
    	exit(1);
    }
    wordCount = get5Words(vw, fiveChem212, wordCount, 212);
    vw.pop_back();  wordCount -= 1; 
	
    // Load up vw chem symbols from 5-letter words in pattern 2-2-1
    ifstream fiveChem221( "fiveChem221.txt", ios::in); //, ios::in
    if( !fiveChem221 ) {
    	cerr << "File could not be opened." << endl;
    	exit(1);
    }
    wordCount = get5Words(vw, fiveChem221, wordCount, 122);
    vw.pop_back(); wordCount -= 1;
    fiveChem122.close(); 	fiveChem212.close(); 	fiveChem221.close();

    // Sort the big list
    bubbleSort(vw,wordCount);

    // Write sorted words to a file
    ofstream chemWords("chemWordsSorted.txt", ios::out);
    printVvtoFile(chemWords, vw, wordCount);

    // You may want to print word list to the console...or not
    //printVv(vw, wordCount);
    
    bool gotaMatch = 0;  // ...see code
    unsigned i,j,k,m,n;  // need a bund of counters
    
    // the matrix 'a' will hold the solution as we attempt to build it
    string a[3][3];
    
    // Create file stream for recording solutions
    ofstream chemSquares("chemSquareSolns.txt", ios::out);
    
    // Here's where we search for puzzle solutions.
    // Take advantage of the words being in alphabetical order.
    for(i = 0; i < wordCount; ++i) { //for each word in the sorted data base structure
    	for(j = 0; j < 3; ++j)    // Put the ith word in first row across
    		a[0][j] = vw[i][j];
    	k = i+1; // this is probably not all that good a thing! Miss some solutions.
    	//keep testing as long as the next word's first symbol is the same
    	// and there are no repeats--that's 4 additional comparisons!
    	while(vw[k][0] == a[0][0] && k < wordCount) { 
        // the kth word has the same first symbol as the ith word (which is in 1 across)
    	    if(vw[k][1] != a[0][1] &&
    	       vw[k][1] != a[0][2] &&
    	       vw[k][2] != a[0][1] &&
    	       vw[k][2] != a[0][2]) { // the second and third symbs of the kth word are new
            	for(j = 1; j < 3; ++j)// fill in first column's word symbols
       	        	a[j][0] = vw[k][j];			
			// Find the words the start with v[i][1]=a[0][1] and v[k][1] 
			// (first two while loops immediately below)
			// are there words such that the second chem symbol of each matches?, 
			// if so, find them (first two while loops) put it there
				
			m = 0; // m advances to a word (if it exists) 
			       // whose first symbol matches second of 1 across
			while(vw[m][0] < a[0][1] && m < wordCount) { //vw[i][1] 
				++m; //cout << "\nn = " << n;
			}
			n = 0; //n counts to a word whose first symbol matches second of 1 down
			while(vw[n][0] < a[1][0] && n < wordCount) {
			    ++n; //cout << "\nn = " << n;
			}
			// Starting with v[m][0] = a[0][1] and v[n][0] = a[1][0], 
			// look for a match in v[m][1] = v[n][1]
			for(int q = m; vw[q][0] == a[0][1]; ++q)
			    for(int r = n; vw[r][0] == a[1][0]; ++r) {
				if(vw[q][1]==vw[r][1])  // this might be a good place to check for doubles
				{ 
				    // we found a match in the middle so fill in 2 across and 2 down
				    a[1][1] = vw[q][1]; a[1][2] = vw[r][2]; a[2][1] = vw[q][2];
				    // find 3rd symbs that could be seconds for the cross thirds
					    if(fit2downWith2across(vw,a,wordCount)) {
						if(gotLastSquare(vw,a,wordCount)) {
						    printArr(a);
						    printArr2File(chemSquares, a );
						} //end print solution if
					    } // end 2-down & 2-across if
				} //end if fit2downWith2across
			   } //end for loops
	    // end 1 down symbols are new ones if	
	    ++k; //cout << "\nk = " << k; // check next word to see if it's the same	
	}// end while 1-down and 1-across match first symbols
    }// end for i

    cin >> c; //pause
    return 0;
}  //end main ///////////////////////////////////////////////////////////////////

int get6Words(vector<vector<string> > &vw, istream &input) {
  // accumulate the characters in cSymbol in pairs and load these into 
  // sets of three 2-letter strings in each vector of the vector of vectors of strings
    string cSymbol = "";
    unsigned j=0;  // char c; cin >> c;
    input.clear(); //	cout << "\nhi there after clear";
    char letter;
    while( !input.eof() ) {
    	for(int k = 0; k < 3; ++k) {
    	    cSymbol = "";
            for(int i = 0; i < 2; ++ i) {
        	input >> letter;
		cSymbol += letter;
		    } //cout << "\ncSymbol = " << cSymbol << " and j = " << j;
		    vw[j].push_back(cSymbol); 
	    } // end word vector for 
	    // for(int y = 0; y < 3; ++y) cout << "\nvw[" << j << "][" << y << "] = " << vw[j][y];
	    ++j;	
    } // end while
    return j;
} ////////////////////////////////////////////////////////////////////////


int get5Words(vector< vector<string> > &vw, istream &input, int j, int pattern) {
    //get5Words takes pattern to follow either 221, 212 or 122 pattern
    char letter;
    string cSymbol; //vw.pop_back();
    int i,k,p; //char c; //input.clear();
    while( !input.eof() ) {
    	p = pattern;
    	for(k = 0; k < 3; ++k) {
            cSymbol = "";
		for(i = 0; i < p%10; ++i) {
			input >> letter; //cout << "\nletter = " << letter;
			cSymbol += letter; //cout << "\nword = " << word;
		} //end for
		p /= 10;  // read pattern
		vw[j].push_back(cSymbol);
		//cout << "\nvw[" << j << "][0] = " << vw[j][0];
	} // end word vector for
	++j;
    } // end while
    return j;
} ////////////////////////////////////////////////////////////////////////


bool fit2downWith2across(vector<vector<string> > &vw, string a[][3], unsigned wordCount) {
    bool foundFirst = false, foundSecond = false;
    unsigned x=0,y=0;//,m,n;
    // Trying to match the 3 across and 3 down words now
    // advance x, y counters to positions in alphabetized list...or to end
    while(vw[x][0]<a[2][0] && x < wordCount) ++x;  
    while(vw[y][0]<a[0][2] && y < wordCount) ++y;
    while(x < wordCount && vw[x][0] == a[2][0] && !foundFirst) {
      //if 2nd symbs of xth word and 3across match and are new, skip to next while
      if(vw[x][1] == a[2][1] && a[2][1] != a[0][0]
  			     && a[2][1] != a[1][0]
			     && a[2][1] != a[0][2]) 
		foundFirst = true;
      ++x;
    }
    while(y < wordCount && vw[y][0] == a[0][2] && !foundSecond) {
      //if 2nd symbs of yth word and 3down match and are new, return
      if(vw[y][1] == a[1][2] && a[1][2] != a[0][0]
  			     && a[1][2] != a[0][1]
			     && a[1][2] != a[2][0]
			     && a[1][2] != a[2][1]) 
                foundSecond = true;
      ++y;
    }
    return (foundFirst && foundSecond);
}   //end fit2downWith2Across ////////////////////////////////////////////////////
	
bool gotLastSquare(vector<vector<string> > &vw, string a[][3], unsigned wordCount) {
    bool found = false; //char c;
    unsigned x=0,y=0; //cout << "\nWe're here in gotLastSquare.";
    // 1&2across and 1&2down are matched, so we're looking to see if the bottom square is good too
    // advance x, y counters to first symbol position--it might be better to pass these parameters?
    while(vw[x][0]<a[2][0] && x < wordCount) ++x;
    while(vw[y][0]<a[0][2] && y < wordCount) ++y;
    // Assuming the database (v of v of s) is sorted 
    while(vw[x][0]==a[2][0] && vw[x][1]<a[2][1] && x < wordCount) ++x;
    while(vw[y][0]==a[0][2] && vw[y][1]<a[1][2] && y < wordCount) ++y;
    // cout<<"\nvw["<<x<<"][2]="<<vw[x][2]<<"=?vw["<<y<<"][2]="<<vw[y][2];
    if( vw[x][2]==vw[y][2] && vw[x][2]!=a[0][0]
      			   && vw[x][2] != a[1][0]
			   && vw[x][2] != a[0][1]
			   && vw[x][2] != a[1][1]) 
    {     // if we find a new symbol that makes 3across and 3down words, put it in!!
	a[2][2] = vw[x][2];
	found = true;
    }
    return found;
} /////////////////////////////////////////////////////////////
  

void printArr(string a[][3]) {
    cout << endl << endl; 
    for(int h = 0; h < 3; ++h) {
        for(int i = 0; i < 3; ++i) 
	    cout << a[h][i] << " ";
	cout << endl; 
    }
    //  cout << endl << a[1][0] << " " << a[1][1] << endl << a[2][0];
}  //////////////////////////////////////////////////////////////////

void printArr2File(ostream &outfile, string a[][3] ) {
    outfile << endl << endl; 
    for(int h = 0; h < 3; ++h) {
        for(int i = 0; i < 3; ++i) 
	    outfile << a[h][i] << " ";
	outfile << endl;
    }
    //	cout << endl << a[1][0] << " " << a[1][1] << endl << a[2][0];
}	 ////////////////////////////////////////////////////////////////

void printVv(const vector<vector<string> > &vv, unsigned size) {
    int wrap1 = 0;
    cout << endl << endl;
    for(unsigned i = 0; i < size; ++i) {
	for(unsigned j = 0; j < 3; ++j) 
	    cout << vv[i][j];
        cout << "  ";
	++wrap1;
        if (wrap1%10 == 0) cout << endl;
    }
} //////////////////////////////////////////////////////////////

void printVvtoFile(ostream &outfile, const vector<vector<string> > &vv, unsigned size) {
    int wrap1 = 0;
    outfile << endl << endl;
    for(unsigned i = 0; i < size; ++i) {
	for(unsigned j = 0; j < 3; ++j) 
	    outfile << vv[i][j];
        outfile << "  ";
	++wrap1;
        if (wrap1%10 == 0) outfile << endl;
    }
} /////////////////////////////////////////////////////////////////////

void bubbleSort(vector<vector<string> > &vw, const unsigned size) {
    //loop to control passes
    for( unsigned pass = 0; pass < size - 1; pass++)
	// loop to control comparisons during each pass
	for( unsigned k = 0; k < size - 1; k++)
	    // swap adjacent elements if they are out of order
	    if( vw[k][0] > vw[k+1][0])
		swap( vw[k],vw[k+1] );
	unsigned z = 0;
	//char ch;
	unsigned symCount = 0;
	while (z < size - 1 ) {
	    // count how many start with each symbol
	    symCount = 0;
	    string currWord = vw[z][0];
	    while(currWord == vw[z+symCount][0] && z+symCount < size) ++symCount;
	    //cout << "\nThere are " << symCount << " words starting with " << vw[z][0];
	    //cin >> ch;
	    for( unsigned pass = 0; pass < size - 1; pass++)
	        // loop to control comparisons during each pass
		for( unsigned k = z; k < z + symCount - 1; k++)
		    // swap adjacent elements if they are out of order
		    if( vw[k][1] > vw[k+1][1])
			swap( vw[k],vw[k+1] );
	    z +=symCount;
	} // end while(z < sizeO
} // end function bubbleSort