#include <algorithm>
#include <iostream>
#include <queue>

#include "prologin.hh"
#include "pathfinding.hh"

using namespace std; 

const int neverSeen = -1;

// PONDERATION SUR LES PULSARS
double Pulsar::puissanceMoyenne() const {
    pulsar_info info = info_pulsar(pulsar);
    return 0.25*double(info.puissance)/double(info.periode);
}

double Pulsar::puissanceTotale() const {
    pulsar_info info = info_pulsar(pulsar);
    return 0.25*double(info.puissance)*double(info.pulsations_restantes);
}

// SELECTION DE PULSARS NON ETEINTS
vector<Pulsar> pulsarsVivants() {
    vector<position> pulsars = liste_pulsars();
    vector<Pulsar> dispo;
    for (const auto& pulsar: pulsars) {
        if (info_pulsar(pulsar).pulsations_restantes == 0)
            continue ;
        vector<position> sites = neighbours(pulsar);
        for (const auto& site: sites)
            if (inside(site))
                dispo.emplace_back(site, pulsar);
    }
    return dispo;
}

// SELECTION DE PULSARS ACCESSIBLES
vector<Pulsar> pulsarsLibres() {
    vector<Pulsar> pulsars = pulsarsVivants();
    vector<Pulsar> dispo;
    for (const auto& pulsar: pulsars) {
        if (est_libre(pulsar.site))
            dispo.push_back(pulsar);
    }
    return dispo;
}

// UTILITAIRE DE PATHFINDING

position makePos(int x, int y) {
    position pos;
    pos.x = x;
    pos.y = y;
    return pos;
}

position departTuyau(position pos) {
    if (pos.x == 0)
        return makePos(1, pos.y);
    if (pos.x == TAILLE_TERRAIN-1)
        return makePos(TAILLE_TERRAIN-2, pos.y);
    if (pos.y == 0)
        return makePos(pos.x, 1);
    if (pos.y == TAILLE_TERRAIN-1)
        return makePos(pos.x, TAILLE_TERRAIN-2);
    return pos;
}

vector<position> neighbours(position pos) {
    int x = pos.x;
    int y = pos.y;
    vector<position> cases = {makePos(x+1,y), makePos(x-1,y), makePos(x,y+1), makePos(x,y-1)};
    return cases;
}

int d1(position a, position b) {
    return abs(a.x - b.x) + abs(a.y - b.y);
}

// PARAMETRES DU DIJKTRA (DIFFRENTES POLITIQUES, DIFFERENTS VOISINS, DIFFERENTES PONDERATIONS)

bool inside(position pos) {
    return pos.x >= 0 && pos.y >= 0 && pos.x < TAILLE_TERRAIN && pos.y < TAILLE_TERRAIN;
}

bool toutChemins(position pos) {
    return est_libre(pos) || est_tuyau(pos) || est_debris(pos);
}

bool tuyauxSeulement(position pos) {
    return est_tuyau(pos);
}

int reseauEtTrous(position dest, Edge current) {
    if (est_tuyau(dest))
        return current.weight;
    if (est_debris(dest))
        return current.weight+3;
    return current.weight+1;
}

int tuyauxLong(position dest, Edge current) {
    if (est_tuyau(dest))
        return current.weight+1;
    return current.weight;
}

int poidsBFS(position dest, Edge current) {
    return current.weight+1;
}

vector<Edge> aretesBases(vector<position> positions) {
    vector<Edge> edges;
    for (const auto& pos : positions)
        edges.emplace_back(pos, 5 - puissance_aspiration(pos));
    return edges;
}

vector<Edge> poidsUniforme(vector<position> positions, int poids) {
    vector<Edge> edges;
    for (const auto& pos : positions)
        edges.emplace_back(pos, poids);
    return edges;
}

// DIJKSTRA PARAMETRABLE
vector<vector<int>> dijkstra(const vector<Edge>& edges, function<bool (position)> correct, function<int (position, Edge)> poids) {
    vector<vector<int>> weights(TAILLE_TERRAIN, vector<int>(TAILLE_TERRAIN, neverSeen));
    priority_queue<Edge> waiting;
    for (const auto& edge : edges)
        waiting.push(edge);
    while (!waiting.empty()) {
        Edge current = waiting.top();
        waiting.pop();
        if (weights[current.pos.x][current.pos.y] != neverSeen)
            continue ;
        weights[current.pos.x][current.pos.y] = current.weight;
        for (const auto& neighbor : neighbours(current.pos))
            if (inside(neighbor) && correct(neighbor) && weights[neighbor.x][neighbor.y] == neverSeen)
                waiting.push(Edge(neighbor, poids(neighbor, current)));
    }
    return weights;
}

// SUPERPOSE L'INFLUENCE DE DEUX GRILLES
vector<vector<int>> differenceGrille(vector<vector<int>> a, vector<vector<int>> b) {
    vector<vector<int>> grille(TAILLE_TERRAIN, vector<int>(TAILLE_TERRAIN, 0));
    for (int x = 0; x < TAILLE_TERRAIN; ++x) {
        for (int y = 0; y < TAILLE_TERRAIN; ++y) {
            
            if (a[x][y] != neverSeen)
                grille[x][y] += a[x][y];
            else
                grille[x][y] += 1000;
            
            if (b[x][y] != neverSeen)
                grille[x][y] -= b[x][y];
            else
                grille[x][y] -= 1000;
        }
    }
    return grille;
}

// CASES CONTROLLEES PAR MOI OU L'ADVERSAIRE
vector<vector<int>> getInfluence() {
    vector<vector<int>> myInfluence = dijkstra(aretesBases(ma_base()), tuyauxSeulement, tuyauxLong);
    vector<vector<int>> enemyInfluence = dijkstra(aretesBases(base_ennemie()), tuyauxSeulement, tuyauxLong);
    return differenceGrille(enemyInfluence, myInfluence);
}

// CASES POUR LESQUELLES J'AI L'ESPOIR DE LES CONQUERIR
vector<vector<int>> getPretentions() {
    return dijkstra(aretesBases(ma_base()), toutChemins, poidsBFS);
}

// COMME AVANT, MAIS EN PRENANT EN COMPTE L'ADVERSAIRE
vector<vector<int>> getCandidates() {
    return differenceGrille(dijkstra(aretesBases(base_ennemie()), tuyauxSeulement, tuyauxLong), getPretentions());
}

// SELECTIONNE LES PROCHAIN PULSARS QUI VONT ETRE CONQUIS
vector<Pulsar> selectCandidates() {
    vector<vector<int>> candidates = getCandidates();
    vector<vector<int>> influence = getInfluence();
    vector<Pulsar> pulsars = pulsarsVivants();
    vector<Pulsar> taken;
    for (const auto& pulsar : pulsars) {
        if (candidates[pulsar.site.x][pulsar.site.y] >= 0 
            && influence[pulsar.site.x][pulsar.site.y] <= 0)
            taken.push_back(pulsar);
    }
    return taken;
}

// A PARTIR DES PULSARS ET DE LEURS CARACTERISTIQUES, AINSI QUE DU CONTROL MAP DE L'ADVERSAIRE, POSER DES TUYAUX MAXIMISANT NOTRE SCORE
void choisirItineraire() {
    vector<Pulsar> pulsars = selectCandidates();
    vector<vector<int>> mauvaiseInfluence = dijkstra(aretesBases(base_ennemie()), tuyauxSeulement, tuyauxLong);
    vector<vector<double>> scores(TAILLE_TERRAIN, vector<double>(TAILLE_TERRAIN, 0.0));
    
    cout << pulsars.size() << "\t";
    for (const auto& pulsar : pulsars) {
        
        int influenceEnemy = mauvaiseInfluence[pulsar.site.x][pulsar.site.y];
        if (influenceEnemy == neverSeen)
            influenceEnemy = 1000;
        vector<Edge> singleton(1, Edge(pulsar.site, 1));
        vector<vector<int>> atteignable = dijkstra(singleton, toutChemins, poidsBFS);
        
        auto contrainte = [&](position pos){ return toutChemins(pos) && atteignable[pos.x][pos.y] <= influenceEnemy;};
        singleton[0].weight = (est_tuyau(pulsar.site))? 0 : 1;
        vector<vector<int>> grille = dijkstra(singleton, contrainte, reseauEtTrous);
        
        // debugGrille(grille);
        
        vector<position> chemin = retrouverChemin(grille, pulsar.site);
        // cout << chemin.size() << " ";
        if (chemin.empty())
            continue ;
        int longueur = chemin.size();
        double score = pulsar.puissanceTotale()/double(longueur*longueur); 
        
        for (const auto& pos : chemin)
            scores[pos.x][pos.y] += score;
    }
    
    // cout << endl;
    
    vector<position> meilleurChemin;
    for (int x = 0; x < TAILLE_TERRAIN; ++x)
        for (int y = 0; y < TAILLE_TERRAIN; ++y)
            if (scores[x][y] != 0.0)
                meilleurChemin.push_back(makePos(x, y));
    sort(begin(meilleurChemin), end(meilleurChemin), 
         [&](position a, position b){ return scores[a.x][a.y] > scores[b.x][b.y];});
    
    for (const auto& pos : meilleurChemin) {
        bool fragile = est_debris(pos);
        if (fragile)
            deblayer(pos);
        erreur ok = construire(pos);
        if (fragile)
            ameliorer(pos);
        if (ok == OK)
            return ;
    }
    /*
    cout << endl << ">> ";
    debugTableau(meilleurChemin);
    cout << endl;
    */
}

// RETROUVER UN CHEMIN SUR UNE CARTE MARQUEE PAR DIJKSTRA
vector<position> dfs(vector<vector<int>>& coutTuyau, position arrive, position pos) {
    if (coutTuyau[pos.x][pos.y] == neverSeen)
        return vector<position>();
    
    if (pos == arrive)
        return vector<position>(1, arrive);
    
    // cout << "[" << pos.x << "," << pos.y << "] " << coutTuyau[pos.x][pos.y] << endl;
    int score = coutTuyau[pos.x][pos.y];
    coutTuyau[pos.x][pos.y] = neverSeen;
    
    vector<position> voisins = neighbours(pos);
    for (unsigned int i = 0; i < voisins.size(); ++i) {
        auto economie = [&](position a, position b) {
            if (coutTuyau[a.x][a.y] == neverSeen)
                return false;
            if (coutTuyau[b.x][b.y] == neverSeen)
                return true;
            if (coutTuyau[a.x][a.y] != coutTuyau[b.x][b.y])
                return coutTuyau[a.x][a.y] < coutTuyau[b.x][b.y];
            return d1(a, arrive) < d1(b, arrive);
        };
        
        auto next = min_element(begin(voisins), end(voisins), economie);
        if (coutTuyau[next->x][next->y] > score 
            || coutTuyau[next->x][next->y] == neverSeen)
            break ;
        
        vector<position> fils = dfs(coutTuyau, arrive, *next);
        if (!fils.empty()) {
            fils.push_back(pos);
            return fils;
        }
    }
    return vector<position>();
}

// RETROUVER LE CHEMIN A PARTIR DU DIJKSTRA, EN NE PRENANT QUE LES TERRAINS CONSTRUCTIBLES
vector<position> retrouverChemin(vector<vector<int>> coutTuyau, position arrive) {
    vector<position> bases = ma_base();
    vector<position> departs;
    for (const auto& base : bases)
        departs.push_back(departTuyau(base));
    auto economie = [&](position a, position b) {
        if (coutTuyau[a.x][a.y] == neverSeen)
            return false;
        if (coutTuyau[b.x][b.y] == neverSeen)
            return true;
        if (coutTuyau[a.x][a.y] != coutTuyau[b.x][b.y])
            return coutTuyau[a.x][a.y] < coutTuyau[b.x][b.y];
        return d1(a, arrive) < d1(b, arrive);
    };
    
    auto meilleur = min_element(begin(departs), end(departs), economie);
    vector<position> chemin = dfs(coutTuyau, arrive, *meilleur);
    
    vector<position> constructible;
    for (const auto& pos : chemin)
        if (!est_tuyau(pos))
            constructible.push_back(pos);
    return constructible;
}

void debugGrille(vector<vector<int>> grille) {
    for (int y = 0; y < TAILLE_TERRAIN; ++y) {
        for (int x = 0; x < TAILLE_TERRAIN; ++x) {
            cout << grille[x][y] << "\t";
        }
        cout << endl;
    }
    cout << endl;
}

void debugTableau(vector<position> grille) {
    for (const auto& pos : grille)
        cout << "(" << pos.x << "|" << pos.y << ") ";
    cout << endl;
}
