#include <iostream>
#include <vector>
#include <ctime>
#include <random>
#include <chrono>
#include <fstream>
#include <string>
#include "Neighbours.h"
string mainstr = "C:\\Users\\asus\\Desktop\\petya\\Coursework\\Coursework\\graphs\\";
int N;
using namespace std;
using namespace chrono;
default_random_engine eng(time(0));

using Graph = vector<vector<double>>;
using NN = vector<double>;//сеть с нейронами, где нейрон - это double
using Weights = vector<vector<double>>;
using Ways = vector<int>;

void GraphPrinter(Graph graph) {
    for (int i = 0; i < graph.size(); i++) {
        for (int j = 0; j < graph.size(); j++)
            cout << graph[i][j] << " ";
        cout << endl;
    }
}
void WaysPrinter(Ways ways) {
    for (int i = 0; i < ways.size(); i++)
        cout << ways[i] << " ";
    cout << endl;
}

void NNPrinter(NN nn) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << round(nn[i * N + j]) << " ";
        cout << endl;
    }
}
//Graph GraphGenerator() {
//  Graph graph(N);
//  for (int i = 0; i < graph.size(); i++) {
//      graph[i].resize(N);
//  }
//  uniform_real_distribution<double> distr(1, 10);
//  for (int i = 0; i < graph.size(); i++) {
//      for (int j = 0; j < i; j++) {
//          if (i == j) {
//              graph[i][j] = 0;
//              graph[j][i] = 0;
//              continue;
//          }
//          double dist = distr(eng);
//          graph[i][j] = dist;
//          graph[j][i] = graph[i][j];
//      }
//  }
//  return graph;
//}

void NeuronUpdater(NN& nn, double A, double B, double C, double D, int index, const Graph& graph) {
    double NET = 0;
    for (int endex = 0; endex < nn.size(); endex++) {
        if (endex == index) continue;
        NET += -C * nn[endex];
    }
    int x = index / N;
    int i = index % N;
    for (int j = 0; j < N; j++) {
        if (j == i)continue;
        int y = x;
        int endex = y * N + j;
        NET += -A * nn[endex];
    }
    for (int y = 0; y < N; y++) {
        if (x == y)continue;
        int j = i;
        int endex = y * N + j;
        NET += -B * nn[endex];
    }
    for (int y = 0; y < N; y++) {
        int j = i + 1;
        if (j == N) j = 0;
        int endex = y * N + j;
        NET += -D * graph[x][y] * nn[endex];

        j = i - 1;
        if (j == -1) j = N - 1;
        endex = y * N + j;
        NET += -D * graph[x][y] * nn[endex];
    }

    double w_0_j = C * (N - 0.5);
    NET += w_0_j;
    double u_0 = 5;
    /*if (NET > 0)
        nn[j] = 1;
    if (NET < 0)
        nn[j] = 0;*/
        /*nn[j] = 0.5 * (1 + tanh(NET / u_0));*/
    nn[index] = 0.5 * (1 + tanh(NET / u_0));
    /*nn[index] = 1.0 / (1 + exp(-NET * u_0));*/
}

double EnegryChecker(const NN& nn, double A, double B, double C, double D, const Graph& graph) {
    double E = 0;
    double w_0_j = C * (N - 0.5);
    for (int index = 0; index < nn.size(); index++) {
        double NET = 0;
        for (int endex = 0; endex < nn.size(); endex++) {
            if (endex == index) continue;
            NET += -C * nn[endex];
        }
        int x = index / N;
        int i = index % N;
        for (int j = 0; j < N; j++) {
            if (j == i)continue;
            int y = x;
            int endex = y * N + j;
            NET += -A * nn[endex];
        }
        for (int y = 0; y < N; y++) {
            if (x == y)continue;
            int j = i;
            int endex = y * N + j;
            NET += -B * nn[endex];
        }
        for (int y = 0; y < N; y++) {
            int j = i + 1;
            if (j == N) j = 0;
            int endex = y * N + j;
            NET += -D * graph[x][y] * nn[endex];

            j = i - 1;
            if (j == -1) j = N - 1;
            endex = y * N + j;
            NET += -D * graph[x][y] * nn[endex];
        }
        E += nn[index] * NET;
    }
    E *= -0.5;

    for (int j = 0; j < nn.size(); j++)
        E -= (w_0_j * nn[j]);
    return E;
}

bool OkayNNChecker(NN nn, Ways& ways) {
    ways.resize(N);
    int counter1 = 0, counter2 = 0;
    for (int i = 0; i < N; i++) {
        int counter1 = 0;
        for (int j = 0; j < N; j++) {
            int index = i * N + j;
            if (nn[index] >= 0.5) {
                counter1++;
                ways[j] = i;
            }
        }
        counter2 = 0;
        for (int k = 0; k < N; k++) {
            if (nn[i + k * N] >= 0.5)
                counter2++;
        }
        if (counter1 != 1 || counter2 != 1) return false;
    }
    return true;
}
double LengthCounter(Ways ways, Graph graph) {
    double length = 0;
    for (int i = 0; i < N - 1; i++)
        length += graph[ways[i]][ways[i + 1]];
    length += graph[ways[0]][ways[N - 1]];
    return length;

}
void NNFilling(NN& nn) {
    for (int i = 0; i < N; i++)
        nn[i] = rand() % 2;
}
//нужно сделать чтобы в каждом городе ровно 1 единица матрицы nn и в кадждый момент времени был только один город
// найти длину пути
bool NarayanaPermutation(Ways& ways) {

    int index = -1;
    for (int i = (N - 2); i >= 0; i--) {
        if (ways[i] < ways[i + 1]) {
            index = i;
            break;
        }
    }
    if (index == -1)
        return false;
    for (int j = (N - 1); j > index; j--) {
        if (ways[index] < ways[j]) {
            swap(ways[index], ways[j]);
            break;
        }
    }
    reverse(ways.begin() + (index + 1), ways.end());
    return true;
}

Ways OrdinaryTravelingSalesman(Graph graph) {
    Ways ways(N); Ways minimalWays(N);
    for (int i = 0; i < N; i++)
        ways[i] = i;
    double min = INFINITY;
    while (true) {
        double newMinimum = LengthCounter(ways, graph);
        if (newMinimum < min) {
            min = newMinimum;
            minimalWays = ways;
        }
        if (!NarayanaPermutation(ways)) break;
    }
    return minimalWays;
}
Ways WorstOrdinaryTravelingSalesman(Graph graph) {
    Ways ways(N); Ways maximumWays(N);
    for (int i = 0; i < N; i++)
        ways[i] = i;
    double max = -INFINITY;
    while (true) {
        double newMinimum = LengthCounter(ways, graph);
        if (newMinimum > max) {
            max = newMinimum;
            maximumWays = ways;
        }
        if (!NarayanaPermutation(ways)) break;
    }
    return maximumWays;
}


void GraphReader(Graph& graph, int& N, const string strr) {
    ifstream gin(strr);
    gin >> N;
    graph.resize(N);
    for (int i = 0; i < N; i++) {
        graph[i].resize(N);
    }
    double dub;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            gin >> graph[i][j];
            //if (i == j) dub = INFINITY;
            //graph[i][j] = dub;
        }
    }
    gin.close();
}
int main()
{


    srand(time(0));
    int TEST = 10;
    int EPOCH = 50;
    int FINALEPOCH = EPOCH - 1;
    ofstream filetime("time-N.txt");
    ofstream filelongway("longway-N.txt");
    for (int NUMBER = 5; NUMBER <= 100; NUMBER+=5) {

        double bests_Hopefield = 0, bests_NNS = 0, bests_BNNS = 0;
        double timeHopfield = 0,  timeBNNS = 0, timeNNS = 0;
        //Хопфилд
        for (int graphforN = 0; graphforN < 20; graphforN++) {

            cout << "\nGraph " << graphforN + 1 << endl;
            //Graph graph = GraphGenerator();
            //GraphPrinter(graph);
            //cout << endl;
            string strr = mainstr + to_string(NUMBER) + "_" + to_string(graphforN) + ".txt";
            Graph graph;
            GraphReader(graph, N, strr);
            Ways ways(N, 0);
            double sum = 0;
            double best = INFINITY;
            int count = 0;
            auto tH1 = high_resolution_clock::now();
            for (int test = 0; test < TEST; test++) {
                //auto t1 = high_resolution_clock::now();
                //cout << "test: " << test << endl;
                NN nn(N * N);
                NNFilling(nn);
                for (int i = 0; i < EPOCH; i++) {
                    if (i < EPOCH - 5) {
                        for (int j = 0; j < N * N; j++)
                            NeuronUpdater(nn, 5, 5, 5, 1, rand() % (N * N), graph);
                        for (int j = 0; j < N * N; j++)
                            NeuronUpdater(nn, 5, 5, 5, 1, j, graph);
                    }
                    for (int j = 0; j < N * N; j++)
                        NeuronUpdater(nn, 20, 20, 10, 0.2, rand() % (N * N), graph);
                    for (int j = 0; j < N * N; j++)
                        NeuronUpdater(nn, 20, 20, 10, 0.2, j, graph);

                    double E1 = EnegryChecker(nn, 5, 5, 5, 1, graph);
                    double E2 = EnegryChecker(nn, 20, 20, 20, 0.2, graph);
                    //file << i << "\t" << E1 << "\t" << E2 << endl;
                    ways.clear();

                    bool NNCheck = OkayNNChecker(nn, ways);

                    if (NNCheck) {
                        double l = LengthCounter(ways, graph);

                        if (l < best) best = l;
                        if (i == FINALEPOCH) {
                            sum += l;
                            count++;
                            /*cout << "BEST NOW: " << best << endl;*/

                        }
                    }
                }
                //auto t2 = high_resolution_clock::now();
                //cout << duration_cast<milliseconds>(t2 - t1).count() << endl;
                //cout << endl;
                //file << endl;
            }
            auto tH2 = high_resolution_clock::now();
            timeHopfield += duration_cast<milliseconds>(tH2 - tH1).count();
            //file << endl;
            cout << "Average Hopfield: " << sum / count << endl;
            cout << "Best Hopfield: " << best << endl;

            //Модифицированный Ближайший сосед
            auto tBNNS1 = high_resolution_clock::now();
            Visit BNNSvisit = BNNSVisitGenerator();
            double BNNS = BNNSFinder(graph, BNNSvisit);
            auto tBNNS2 = high_resolution_clock::now();
            timeBNNS += duration_cast<milliseconds>(tBNNS2 - tBNNS1).count();
            cout << "BNNS: " << BNNS << endl;
            bests_BNNS += BNNS;
            //Ближайший сосед
            auto tNNS1 = high_resolution_clock::now();
            Visit NNSvisit = NNSVisitGenerator();
            double NNS = NNSTravelingSalesmanNeighbour(graph, NNSvisit);
            auto tNNS2 = high_resolution_clock::now();
            timeNNS += duration_cast<milliseconds>(tNNS2 - tNNS1).count();
            cout << "NNS: " << NNS << endl;
            bests_NNS += NNS;

            bests_Hopefield += best; // Хопфилд
            cout << "Hopfield: " << best << endl;
        }
        filelongway << "\nAverages on N=" << N << ": \nHopefield " << bests_Hopefield / 20 << "\nNeighbour " << bests_NNS / 20 << "\nSuper-Neighbour " << bests_BNNS / 20 << endl;
        filetime << "\nAverages on N=" << N << ": \nHopefield " << timeHopfield / 20 << "\nNeighbour " << timeNNS / 20 << "\nSuper-Neighbour " << timeBNNS / 20 << endl;
        filetime << endl;

    }
    filelongway.close();
    filetime.close();
}