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

#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 900

int function(std::vector<int> sol, 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(matrix[i][j] < min)
                min = matrix[i][j];
        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, 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, std::vector<std::vector<int>> matrix){
    int bestScore = function(child, matrix);
    std::vector<int> localBest = child, current;
    int localScore;
    for(int i = 0; i < FACILITY_COUNT; i++){
        current = child;
        if(current[i]==0){
            current[i] = 1;
            localScore = function(current,matrix);
            if(localScore < bestScore)
                localBest = current;
            for(int j = i + 1; j < FACILITY_COUNT; j++){
                if(current[i]==1)
                    current[i] = 0;
                localScore = function(current,matrix);
                if(localScore < bestScore)
                    localBest = current;
            }
        }
        else{
            current[i] = 0;
            localScore = function(current,matrix);
            if(localScore < bestScore)
                localBest = current;
            for(int j = i + 1; j < FACILITY_COUNT; j++){
                if(current[i]==0)
                    current[i] = 1;
                localScore = function(current,matrix);
                if(localScore < bestScore)
                    localBest = current;
            }
        }
        child = localBest;
    }
}

void updatePopulation(std::vector<std::vector<int>> &population, std::vector<int> child, 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, std::vector<std::vector<int>> matrix){
    std::vector<std::vector<int>>::iterator numberOfWorst;
    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)
            numberOfWorst = i;
    return *numberOfWorst;
}

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 < 10; i++){
        child = selectionAndCrossover(population, matrix);
        mutation(child);
        localFall(child,matrix);
        updatePopulation(population,child,matrix);
        std::cout<<function(bestInPopulation(population,matrix),matrix);
    }
    return 0;
}