#include <cstdlib>
#include <iostream>
#include <vector>
#include <ctime>
#include <algorithm>

using namespace std;

int countCaptures(vector<int> queens)
{
    int counter = 0;
    for(int i=0; i<queens.size()-1; ++i)
    {
        for(int j=i+1; j<queens.size(); ++j)
        {
            if(i-queens[i] == j-queens[j] || i+queens[i] == j+queens[j]) counter++;
        }
    }
    return counter;
}

void showVector(vector<int> queens)
{
    for(int i=0; i<queens.size(); i++) cout << queens[i] << "\t";
    cout << endl;
}

void showBoard(vector<int> queens)
{
    for(int i=0; i<queens.size(); i++)
    {
        for(int j=0; j<queens.size(); j++)
        {
            if(queens[i]==j) cout << "1 ";
            else cout << "0 ";
        }
        cout << endl;
    }
}

void randomSwapElements(vector<int>& queens)
{
    int pos1 = rand()%queens.size();
    int pos2 = rand()%queens.size();
    int temp = queens[pos1];
    queens[pos1] = queens[pos2];
    queens[pos2] = temp;
}


int main()
{
    srand(time(nullptr));
    int n, k, g;
    float m;
    cout << "Podaj rozmiar planszy: ";
    cin >> n;
    cout << "Podaj licznosc populacji: ";
    cin >> k;
    g = 1;
    cout << "Podaj liczbe generacji: ";
    cin >> g;
    cout << "Podaj prawdopodobienstwo mutacji: ";
    cin >> m;
    vector<vector <int>> population(k, vector<int>(n));
    vector<vector <int>> newPopulation(k, vector<int>(n));
    vector <int> best(n);
    vector <int> captures(k,0);
    vector <int> ranking(k,0);
    vector <float> averages(g,0);
    vector <int> bests (g);
    bool isFound = false;
    for(int i=0; i<k; ++i)
    {
        for(int j=0; j<n; ++j)
        {
            population[i][j] = j;
        }
        random_shuffle(begin(population[i]), end(population[i]));
    }
    int capturesMax, rankSum;


    for(int i=0; i<g; i++)
    {
        best = population[0];
        capturesMax = 0;
        rankSum = 0;
        for(int j=0; j<k; j++)
        {
            captures[j] = countCaptures(population[j]);
            averages[i] += captures[j];
            if(captures[j]==0)
            {
                best = population[j];
                isFound = true;
                break;
            }
            if(captures[j] > capturesMax) capturesMax = captures[j];
            if(captures[j] < countCaptures(best)) best = population[j];
        }
        averages[i] /= k;
        bests[i] = countCaptures(best);

        cout << "average\t" << i << ":\t" << averages[i] << endl;
        cout << "best\t" << i << ":\t" << bests[i] << endl;

        if(isFound == true) break;

        for(int j=0; j<k; j++)
        {
            ranking[j] = capturesMax - captures[j] + 1;
            rankSum += ranking[j];
        }

        int roulette;
        for(int j=0; j<k; j++)
        {
            roulette = rand()%rankSum+1;
            int temp = 0;
            for(int l=0; l<k; l++)
            {
                temp += ranking[l];
                if(temp >= roulette)
                {
                    newPopulation[j] = population[l];
                    break;
                }
            }
        }

        for(int j=0; j<k; j++)
        {
            if(rand()%101 < m*100)
            {
                randomSwapElements(newPopulation[j]);
            }
        }

        population = newPopulation;
    }



    cout << endl << endl;
    showVector(best);
    showBoard(best);
    cout << endl << "Liczba bic: " << countCaptures(best);



    return 0;
}