//Chad Williamson

#include <iostream> 
#include <fstream> 
#include <string> 
#include <vector> 

struct matrix {
	char name;
	int numRows;
	int numCols;
};

std::vector<std::vector< int >> findSplit(int i, int j, std::vector<std::vector< int >> k, std::vector<std::vector<std::vector< int >>> o);
void drawLine(int w);

int main(int argc, char* argv[]) {
	//matrix names
	char abet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	int numOfMatrices = 0;
	std::vector<matrix> inputMatrices;
	std::string resultString = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	std::string input = "";
	std::cout << "Give each matrix in brackets, separated by commas." << std::endl;
	std::cout << "Example input: [2,4], [4,10], [10,6] <- this input gives three matrices" << std::endl;
	std::cout << "Enter matrices: ";
	std::getline(std::cin, input);
	char curr;
	std::string rowStr = ""; std::string colStr = "";
	//dfa	
	int state = 0;
	while (input.length() > 0) {
		curr = input.at(0);
		if (curr != ' ') {
			switch (state) {
			case -1:
				break;
			case 0:
				if (curr == '[') {
					state = 1;
				}
				else {
					state = -1;
				}
				break;
			case 1:
				if (isdigit(curr)) {
					rowStr += curr;
					state = 2;
				}
				else {
					state = -1;
				}
				break;
			case 2:
				if (isdigit(curr)) {
					rowStr += curr;
				}
				else if (curr == ',') {
					state = 3;
				}
				else {
					state = -1;
				}
				break;
			case 3:
				if (isdigit(curr)) {
					colStr += curr;
					state = 4;
				}
				else {
					state = -1;
				}
				break;
			case 4:
				if (isdigit(curr)) {
					colStr += curr;
				}
				else if (curr == ']') {
					state = 5;
				}
				else {
					state = -1;
				}
				break;
			case 5:
				matrix m;
				m.name = abet[inputMatrices.size()];
				m.numCols = std::stoi(colStr);
				m.numRows = std::stoi(rowStr);
				rowStr = "";
				colStr = "";
				inputMatrices.push_back(m);
				if (curr == ',') {
					state = 6;
				}
				else {
					state = -1;
				}
				break;
			case 6:
				if (curr == '[') {
					state = 1;
				}
				else {
					state = -1;
				}
			}
			//end switch case
		}
		//end if not space character
		input.erase(0, 1);
	}
	//end while
	//valid exit state is 5. need to handle last matrix that is given.
	if (state == 5) {
		matrix m;
		m.name = abet[inputMatrices.size()];
		m.numCols = std::stoi(colStr);
		m.numRows = std::stoi(rowStr);
		inputMatrices.push_back(m);
	}
	else {
		std::cout << "Invalid input. Enter matrices in form: \n\n [0, 1] , [1, 2], [2, 3] \n\n Exiting \n\n" << std::endl;
		return 0;
	}

	//all matrices are in the vector inputMatrices
	numOfMatrices = inputMatrices.size();
	std::vector<std::vector< int > > results(numOfMatrices, std::vector< int >(numOfMatrices, 0));
	std::vector<std::vector< int > > kvalues(numOfMatrices, std::vector< int >(numOfMatrices, 0));
	std::vector<std::vector<std::vector< int >>> operations(numOfMatrices, std::vector<std::vector< int >>(numOfMatrices, std::vector< int >(4)));

	int loopOuter = numOfMatrices - 1;
	int loopInner = loopOuter;
	int loopInnerInc = 1;
	int ival = 0; int jval = 0;
	int kval = 1;
	int diff = 0;

	int first_target_i = 0;
	int first_target_j = 0;
	int second_target_i = 0;
	int second_target_j = 0;
	int value = 0;
	int x = 0; int y = 0; int z = 0;
	while (loopOuter > 0) {
		loopInner = loopOuter;
		while (loopInner > 0) {
			ival = loopInnerInc;
			jval = numOfMatrices - loopInner + 1;

			//will perform number of operations for each walk up the result matrix.
			//use ival and jval for placing into correct result matrix index
			//each successive pass requires 1 more value calculated per index - find min of this value.
			kval = ival;
			//numOfMatrices - loopOuter gives the pass number.
			for (int i = ival; i < jval; i++) {
				first_target_i = ival;
				first_target_j = jval - ((numOfMatrices - loopOuter) - ((i - ival) + 1) + 1);
				second_target_i = ival + ((i - ival) + 1);
				second_target_j = jval;
				x = inputMatrices[ival - 1].numRows;
				y = inputMatrices[kval].numRows;
				z = inputMatrices[jval - 1].numCols;
				value = results[first_target_i - 1][first_target_j - 1] + results[second_target_i - 1][second_target_j - 1] + (x * y * z);
				if ((results[ival - 1][jval - 1] == 0) || (value < results[ival - 1][jval - 1])) {
					results[ival - 1][jval - 1] = value;
					kvalues[ival - 1][jval - 1] = kval;
					operations[ival - 1][jval - 1] = { first_target_i, first_target_j, second_target_i, second_target_j };
				}
				//end kval loop
				kval++;
			}
			//end ival jval
			loopInnerInc++;
			loopInner--;
		}
		std::cout << std::endl;
		loopInnerInc = 1;
		loopOuter--;
	}

	resultString = resultString.substr(0, numOfMatrices);
	std::vector<std::vector< int >> splitLocations = findSplit(0, numOfMatrices - 1, kvalues, operations);
	for (int q = 0; q < splitLocations.size(); q++) {
		char firstLetter = abet[splitLocations[q][0] - 1];
		char secondLetter = abet[splitLocations[q][1] - 1];
		std::size_t foundFirst = resultString.find(firstLetter);
		resultString.insert(foundFirst, 1, '(');
		std::size_t foundSecond = resultString.find(secondLetter);
		resultString.insert(foundSecond + 1, 1, ')');
	}

	for (int i = 0; i < numOfMatrices; i++) {
		drawLine(numOfMatrices);
		std::cout << "\n";
		for (int j = 0; j < numOfMatrices; j++) {
			if (i > j) {
				std::cout << "|X\t";
			}
			else {
				std::cout << "|" << results[i][j] << "\t";
			}
		}
		std::cout << "|" << std::endl;
	}
	drawLine(numOfMatrices);
	std::cout << "\nMinimum work value: " << results[0][numOfMatrices - 1] << std::endl;
	std::cout << resultString << std::endl;
	return 0;
}


std::vector<std::vector< int >> findSplit(int i, int j, std::vector<std::vector< int >> kVals, std::vector<std::vector<std::vector< int >>> opVals) {
	//recursively finds where splits should be placed
	std::vector < std::vector< int >> result2D;
	int f_i = 0; int f_j = 0;
	int s_i = 0; int s_j = 0;
	f_i = opVals[i][j][0];
	f_j = opVals[i][j][1];
	s_i = opVals[i][j][2];
	s_j = opVals[i][j][3];
	if (f_i != f_j) {
		result2D.push_back({ f_i, f_j });
	}
	if (s_i != s_j) {
		result2D.push_back({ s_i, s_j });
	}
	if ((f_j - f_i) > 1) {
		std::vector<std::vector< int >> itrmdt = findSplit(f_i - 1, f_j - 1, kVals, opVals);
		for (int i = 0; i < itrmdt.size(); i++) {
			result2D.push_back(itrmdt[i]);
		}
	}
	if ((s_j - s_i) > 1) {
		std::vector<std::vector< int >> itrmdt = findSplit(s_i - 1, s_j - 1, kVals, opVals);
		for (int i = 0; i < itrmdt.size(); i++) {
			result2D.push_back(itrmdt[i]);
		}
	}
	return result2D;
}

void drawLine(int w) {
	for (int k = 0; k < w * 8 + 1; k++) {
		if (k == 0 || k == (w * 8)) {
			std::cout << "|";
		}
		else {
			std::cout << "-";
		}
	}
}