#include <fstream>
#include <vector>
#include <iostream>
#include <time.h>
#include <iterator>

#define N 1500
#define LINE_SIZE 40
#define FACILITY_COUNT 100
#define CLIENT_COUNT 100
#define POPULATION_SIZE 30
#define FIXED_COST 3000
#define PROPABILITY_TO_BE_IN_POOL_OF_PARENTS 500
#define PROPABILITY_OF_MUTATION 950

unsigned int function(const std::vector<int> &sol, const std::vector<std::vector<int>> &matrix){
	int result = 0;
	for(int i = 0; i < FACILITY_COUNT; i++)
		if(sol[i] == 1)
			result += FIXED_COST;
	for(int j = 0; j < CLIENT_COUNT; j++){
		int min = INT_MAX;
		for(int i = 0; i < FACILITY_COUNT; i++)
			if(sol[i] == 1){
				int a = matrix[i][j];
				if(a < min)
					min = matrix[i][j];
			}
		result += min;
	}
	return result;
}

unsigned int function(const std::vector<int> &sol, const std::vector<std::vector<int>> &matrix,
						std::vector<int> &best, std::vector<int> &bestValue, std::vector<int> &second, std::vector<int> &secondValue){
	int result = 0;
	for(int i = 0; i < FACILITY_COUNT; i++)
		if(sol[i] == 1)
			result += FIXED_COST;
	for(int j = 0; j < CLIENT_COUNT; j++){
		int min = INT_MAX;
		for(int i = 0; i < FACILITY_COUNT; i++)
			if(sol[i] == 1){
				int a = matrix[i][j];
				if(a < min){
					second[j] = best[j];
					secondValue[j] = bestValue[j];
					best[j] = i;
					bestValue[j] = a;
					min = a;
				}
			}
		result += min;
	}
	return result;
}

void readMatrix(std::vector<std::vector<int>> &matrix, char* filename){
	int u, v, c;
	char line[LINE_SIZE];
	std::fstream fs;
	matrix.resize(FACILITY_COUNT);
	for(int i = 0; i < FACILITY_COUNT; i++)
		matrix[i].resize(CLIENT_COUNT);
	for(int i = 0; i < FACILITY_COUNT; i++)
		for(int j = 0; j< CLIENT_COUNT; j++)
			matrix[i][j] = INT_MAX;
	fs.open(filename,std::fstream::in);
	for(int i = 0; i<4; i++)
		fs.getline(line,LINE_SIZE);
	while(!fs.eof()){
		fs >> u >> v >> c;
		matrix[u-1][v-1] = c;
	}
	fs.close();
}

void generateFirstPopulation(std::vector<std::vector<int>> &population){
	population.resize(POPULATION_SIZE);
	for(int i = 0; i < POPULATION_SIZE; i++){
		population[i].resize(FACILITY_COUNT);
			for(int j = 0; j < FACILITY_COUNT; j++){

				int res = rand()%1000;
				if (res > 500)
					population[i][j] = 1;
				else
					population[i][j] = 0;
			}
	}
}

void mutation(std::vector<int> &child){
	for(int i = 0; i < FACILITY_COUNT; i++){
		int res = rand()%1000;
		if (res > PROPABILITY_OF_MUTATION){
			if(child[i] == 0)
				child[i] = 1;
			else
				child[i] = 0;
		}

	}
}

std::vector<int> selectionAndCrossover(std::vector<std::vector<int>> &population, const std::vector<std::vector<int>> &matrix){
	std::vector<std::vector<int>> poolOfParents;
	for(int i = 0; i < POPULATION_SIZE; i++){
		int res = rand()%1000;
		if (res > PROPABILITY_TO_BE_IN_POOL_OF_PARENTS)
			poolOfParents.push_back(population[i]);
	}
	std::vector<int> first;
	std::vector<int> second;
	std::vector<int> child;
	child.resize(FACILITY_COUNT);
	int firstRec = INT_MAX;
	int secondRec = INT_MAX;
	for(int i = 0; i < poolOfParents.size(); i++){
		int res = function(poolOfParents[i], matrix);
		if (res < firstRec){
			secondRec = firstRec;
			second = first;
			firstRec = res;
			first = poolOfParents[i];
		}
		else
			if (res < secondRec){
				secondRec = res;
				second = poolOfParents[i];
			}
	}

	for(int i = 0; i < FACILITY_COUNT; i++){
		if(first[i] == 0 && second[i] == 0){
			child[i] = 0;
			continue;
		}
		if(first[i] == 1 && second[i] == 1){
			child[i] = 1;
			continue;
		}
		int res = rand()%1000;
		if (res > 500)
			child[i] = 1;
		else
			child[i] = 0;
	}
	return child;
}

void localFall(std::vector<int> &child, const std::vector<std::vector<int>> &matrix){

	std::vector<int> localBest = child;
	std::vector<int> current;
	std::vector<int> best;
	best.resize(CLIENT_COUNT);
	std::vector<int> bestValue;
	bestValue.resize(CLIENT_COUNT);
	std::vector<int> second;
	second.resize(CLIENT_COUNT);
	std::vector<int> secondValue;
	secondValue.resize(CLIENT_COUNT);

	//int bestScore = function(child, matrix,best,bestValue,second,secondValue);
	int bestScore = function(child, matrix);
	int localScore = bestScore;
	int a = 0;
	while(1){
		int bestScore = function(child, matrix,best,bestValue,second,secondValue);
//		std::cout<<a++<<std::endl;
		int flag = 0;
		for(int i = 0; i < FACILITY_COUNT; i++){
			current = child;
			if(current[i]==0){
				localScore += 3000;
				for(int j = 0; j < CLIENT_COUNT; j++)
					if (matrix[i][j] < bestValue[j]){
						secondValue[j] = bestValue[j];
						second[j] = best[j];
						bestValue[j] = matrix[i][j];
						best[j] = i;
						localScore -= secondValue[j];
						localScore += bestValue[j];
					}
				current[i] = 1;
				//localScore = function(current,matrix);
				if(localScore < bestScore){
					flag = 1;
					bestScore = localScore;
					localBest = current;
				}
				for(int j = i + 1; j < FACILITY_COUNT; j++){
					if(current[i]==1){
						current[i] = 0;
					//	localScore = function(current,matrix);
						localScore -= 3000;
						for(int k = 0; k < CLIENT_COUNT; k++){
							if(best[k] == i){
								localScore -= bestValue[j];
								localScore += secondValue[j];
							}
						}
						if(localScore < bestScore){
							bestScore = localScore;
							localBest = current;
							flag = 1;
						}
						current[i] = 1;
					}
				}
			}
			else{
				current[i] = 0;
				//localScore = function(current,matrix);
				localScore -= 3000;
				for(int k = 0; k < CLIENT_COUNT; k++){
					if(best[k] == i){
						localScore -= bestValue[k];
						localScore += secondValue[k];
					}
				}
				if(localScore < bestScore){
					bestScore = localScore;
					localBest = current;
					flag = 1;
				}
				for(int j = i + 1; j < FACILITY_COUNT; j++){
					if(current[i]==0){
						current[i] = 1;
					//	localScore = function(current,matrix);
						localScore += 3000;
						for(int j = 0; j < CLIENT_COUNT; j++)
							if (matrix[i][j] < bestValue[j]){
								localScore += matrix[i][j];
								localScore -= bestValue[j];
							}
						if(localScore < bestScore){
							bestScore = localScore;
							localBest = current;
							flag = 1;
						}
						current[i] = 0;
					}
				}
			}
			child = localBest;
		}
		if(flag == 0)
			break;
	}
}

void updatePopulation(std::vector<std::vector<int>> &population, std::vector<int> child, const std::vector<std::vector<int>> &matrix){
	std::vector<std::vector<int>>::iterator numberOfWorst;
	int max = function(population[0],matrix);
	for(std::vector<std::vector<int>>::iterator i =population.begin(); i < population.end(); i++)
		if (function(*i, matrix)>=max)
			numberOfWorst = i;
	population.erase(numberOfWorst);
	population.push_back(child);
}

std::vector<int> bestInPopulation(std::vector<std::vector<int>> &population, const std::vector<std::vector<int>> &matrix){
	std::vector<std::vector<int>>::iterator numberOfBest;
	unsigned int min = function(population[0],matrix);
	for(std::vector<std::vector<int>>::iterator i = population.begin(); i < population.end(); i++)
		if (function(*i, matrix)<=min){
			min = function(*i, matrix);
			numberOfBest = i;
		}
	return *numberOfBest;
}

int main(){
	std::vector<std::vector<int>> population;
	std::vector<std::vector<int>> matrix;
	std::vector<int> child;
	srand(time(NULL));
	readMatrix(matrix,"test.txt");
	generateFirstPopulation(population);
	std::cout<<function(bestInPopulation(population,matrix),matrix)<<std::endl;
	for(int i = 0; i < N; i++){
		child = selectionAndCrossover(population, matrix);
		mutation(child);
		localFall(child,matrix);
		updatePopulation(population,child,matrix);
		int bestScore = function(bestInPopulation(population,matrix),matrix);
		std::cout<<"i "<< i<< " Score "<< bestScore<<std::endl;
	}
	std::vector<int> best = bestInPopulation(population,matrix);
	for(int i = 0; i < FACILITY_COUNT; i++)
		if(best[i]==1)
		std::cout<<i<<std::endl;
	return 0;
}