#include "prologin.hh"
#include <vector>
#include <algorithm>
#include <chrono>
#include <iostream>
#include <deque>
#include <random>

using namespace std;

const int NON_VISITE_GRAPHE = -2, VIDE_GRAPHE = -1, MOI_GRAPHE = 0, ADVERSAIRE_GRAPHE = 1;
const position DELTAS_ADJ_DIRECT[] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
long dureeMin = 2L*1000L*1000L*1000L, dureeMax = 0L;
vector<vector<position> > zones[2];
vector<vector<int> > voisins[2];
vector<vector<int> > zoneCase[2];

bool positionValide(position pos) {
    return pos.ligne >= 0 && pos.ligne < TAILLE_ETABLI && pos.colonne >= 0 && pos.colonne < TAILLE_ETABLI;
}

bool estEntierementVide()
{
    for(int lig = 0; lig < TAILLE_ETABLI; lig++)
    {
        for(int col = 0; col < TAILLE_ETABLI; col++)
        {
            if(!est_vide({lig, col}, moi()))
                return false;
        }
    }
    return true;
}

bool compareSizePosition(const pair<int, position> &l, const pair<int, position> &r)
{
    if(l.first <= 1 && r.first > 1)
        return false; // le -1 passe en dernier
    else if(l.first > 1 && r.first <= 1)
        return true;
    return l.first < r.first;
}

bool compareSizePosition2(const pair<int, position> &l, const pair<int, position> &r)
{
    return l.first > r.first;
}

bool compareSizePosition3(const pair<int, position> &l, const pair<int, position> &r)
{
    /// Les tailles de 1 passent automatiquement à la fin
    if(l.first == 1 && r.first > 1)
        return false;
    else if(l.first > 1 && r.first >= 1)
        return true;

    /// Les métaux vils passent tous au-dessus des métaux normaux
    element_propriete typ1 = propriete_case(l.second, moi()), typ2 = propriete_case(r.second, moi());
    if(typ1 == TRANSMUTABLE_OR && typ2 == TRANSMUTABLE_CATALYSEUR)
        return false;
    else if(typ1 == TRANSMUTABLE_CATALYSEUR && typ2 == TRANSMUTABLE_OR)
        return true;

    /// Comme avant, par taille
    return l.first > r.first;
}

bool compareTypePresence(const pair<int, int> &l, const pair<int, int> &r)
{
    return l.second < r.second;
}

void partie_init() /// rien
{
    //nada
}

void partie_fin() /// stats de temps
{
    cout << "Durées de " << dureeMin << " µs à " << dureeMax << " µs\n";
}

int typetoint(case_type typ)
{
    switch(typ)
    {
    case VIDE:
        return 0;
    case CUIVRE:
        return 1;
    case PLOMB:
        return 2;
    case FER:
        return 3;
    case SOUFRE:
        return 4;
    case MERCURE:
        return 5;
    default:
        return -1;
    }
}

case_type inttotype(int i)
{
    switch(i)
    {
    case 0:
        return VIDE;
    case 1:
        return CUIVRE;
    case 2:
        return PLOMB;
    case 3:
        return FER;
    case 4:
        return SOUFRE;
    case 5:
        return MERCURE;
    default:
        return VIDE;
    }
}

case_type typeCaseZone(int iGraphe, int iZone) {
    if(iGraphe == MOI_GRAPHE)
        return type_case(zones[iGraphe][iZone][0], moi());
    else
        return type_case(zones[iGraphe][iZone][0], adversaire());
}

void debugGrille(int qui) {
    for(int lig = 0; lig < TAILLE_ETABLI; lig++) {
        for(int col = 0; col < TAILLE_ETABLI; col++) {
            cout << zoneCase[qui][lig][col] << " ";
        }
        cout << "\n";
    }
    cout << "------------------------\n";
}
void majGraphe(int adversaireOuMoi) {
    int iGraphe;
    if(adversaireOuMoi == adversaire())
        iGraphe = ADVERSAIRE_GRAPHE;
    else if(adversaireOuMoi == moi())
        iGraphe = MOI_GRAPHE;
    else {
        cerr << "majGraphe : le paramètre passé ne correspond ni à l'adversaire, ni à moi !!!\n";
        return;
    }
    zones[iGraphe] = vector<vector<position> > ();
    voisins[iGraphe] = vector<vector<int> > ();
    zoneCase[iGraphe] = vector<vector<int> >(TAILLE_ETABLI, vector<int> (TAILLE_ETABLI, NON_VISITE_GRAPHE));
    /// Détection des zones en elles-mêmes
    for(int lig = 0; lig < TAILLE_ETABLI; lig++) {
        for(int col = 0; col < TAILLE_ETABLI; col++) {
            if(zoneCase[iGraphe][lig][col] != NON_VISITE_GRAPHE)
                continue;
            if(type_case({lig, col}, adversaireOuMoi) == VIDE) {
                zoneCase[iGraphe][lig][col] = VIDE_GRAPHE;
            }
            else {
                zones[iGraphe].push_back(positions_region({lig, col}, adversaireOuMoi));
                for(position pos : zones[iGraphe].back()) {
                    zoneCase[iGraphe][pos.ligne][pos.colonne] = zones[iGraphe].size()-1;
                }
                voisins[iGraphe].push_back(vector<int>());
            }
        }
    }
    /// Détection des arêtes
    for(vector<position> zone : zones[iGraphe]) {
        for(position pos : zone) {
            int iZone1 = zoneCase[iGraphe][pos.ligne][pos.colonne];
            for(position delta : DELTAS_ADJ_DIRECT) {
                position adj = {pos.ligne + delta.ligne, pos.colonne + delta.colonne};
                if(positionValide(adj)) {
                    int iZone2 = zoneCase[iGraphe][adj.ligne][adj.colonne];
                    if(iZone2 != VIDE_GRAPHE && iZone2 != iZone1) {
                        voisins[iGraphe][iZone1].push_back(iZone2);
                        voisins[iGraphe][iZone2].push_back(iZone1);
                    }
                }
            }
        }
    }
}

int nbCasesZone(int iGraphe, int iZone) {
    return zones[iGraphe][iZone].size();
}

int nbCasesVoisins(int iGraphe, int iZone) {
    int ret = 0;
    for(int iVoisin : voisins[iGraphe][iZone])
        ret += nbCasesZone(iGraphe, iVoisin);
    return ret;
}

int nbCatalysesPlusGrosseZone(int iGraphe) {
    vector<pair<int, int> > tailleEtId;
    for(int iZone = 0; iZone < (int)zones[iGraphe].size(); iZone++) {
        if(propriete_case_type(typeCaseZone(iGraphe, iZone)) == TRANSMUTABLE_OR)
            tailleEtId.push_back(pair<int, int> (zones[iGraphe][iZone].size(), iZone));
    }
    sort(tailleEtId.begin(), tailleEtId.end(), greater<pair<int, int> > ());
    return nbCasesVoisins(iGraphe, tailleEtId[0].second);
}

void transmuterPositif() {
    for(int lig = 0; lig < TAILLE_ETABLI; lig++)
    {
        for(int col = 0; col < TAILLE_ETABLI; col++)
        {
            if(propriete_case({lig, col}, moi()) == TRANSMUTABLE_OR && quantite_transmutation_or(taille_region({lig, col}, moi())) >= 0)
                transmuter({lig, col});
            if(propriete_case({lig, col}, moi()) == TRANSMUTABLE_CATALYSEUR && quantite_transmutation_catalyseur_or(taille_region({lig, col}, moi())) >= 0)
                transmuter({lig, col});
        }
    }
}

void consommerMetauxVils() {
    majGraphe(moi());
    for(int iZone = 0; iZone < (int)zones[MOI_GRAPHE].size(); iZone++) {
        vector<position> &zone = zones[MOI_GRAPHE][iZone];
        position arbitraire = zone[0];
        if(propriete_case(arbitraire, moi()) == TRANSMUTABLE_CATALYSEUR && zone.size() >= 3 && nbCatalysesPlusGrosseZone(MOI_GRAPHE) >= quantite_transmutation_catalyseur(zone.size())) {
            transmuter(arbitraire);
        }
    }
}

/// Fonction appelée à chaque tour.
void jouer_tour()
{
    random_device rd;
    auto debut = chrono::high_resolution_clock::now();
    echantillon aPlacer = echantillon_tour();
    int tour = tour_actuel();

    /// DON D'ÉCHANTILLON
    echantillon aDonner;
    if(tour == 1) { /// Random !
        uniform_int_distribution<int> dist(0,1);
        if(dist(rd) == 0)
            aDonner.element1 = FER;
        else
            aDonner.element1 = PLOMB;
        dist = uniform_int_distribution<int> (4,5); /// Seulement les métaux vils
        aDonner.element2 = inttotype(dist(rd));;
    }
    else { /// Les éléments les moins présents chez l'adversaire
        /// Changement de stratégie planifié : si possible, un métal (pour essayer de m'en garantir un) et le métal vil le moins présent (oui !)
        vector<pair<int, int>> nbParType(NB_TYPE_CASES, pair<int, int> (0,0)); /// La pair contient le type puis sa présence
        for(int i = 0; i < NB_TYPE_CASES; i++)
            nbParType[i].first = i;

        for(int lig = 0; lig < TAILLE_ETABLI; lig++)
            for(int col = 0; col < TAILLE_ETABLI; col++)
                nbParType[typetoint(type_case({lig, col}, adversaire()))].second ++;

        /// Ah oui, il y a la règle. 2 cas:
        /// - Deux métaux de même propriété. Le cas est vite résolu : le moins présent chez l'adversaire, à égalité le plus présent chez nous.
        /// - Un métal normal, un métal vil. On lui donne le métal normal pour nous en assurer un.
        bool memePropriete = propriete_case_type(aPlacer.element1) == propriete_case_type(aPlacer.element2);
        bool deuxVils = false;
        if(memePropriete && propriete_case_type(aPlacer.element1) == TRANSMUTABLE_CATALYSEUR) {
            aDonner = aPlacer;
            deuxVils = true;
        }
        else {
            if(propriete_case_type(aPlacer.element1) == TRANSMUTABLE_OR)
                aDonner.element1 = aPlacer.element1;
            else
                aDonner.element1 = aPlacer.element2;
        }
        //if(nbParType[typetoint(aPlacer.element1)].second < nbParType[typetoint(aPlacer.element2)].second)
        //    aDonner.element1 = aPlacer.element1;
        //else
        //    aDonner.element1 = aPlacer.element2;
        //bool estVil = propriete_case_type(aDonner.element1) == TRANSMUTABLE_CATALYSEUR;

        /// Cas de l'élément 2, deux cas :
        /// - Le métal choisi en 1er est normal. On lui donne un vil ?
        /// - Le métal choisi est vil. Vaut mieux s'assurer une chance d'avoir un normal.
        /// - Idée : si on recoit deux métaux vils, surtout répondre par la même !
        if(!deuxVils) {
            sort(nbParType.begin(), nbParType.end(), compareTypePresence);
            for(pair<int, int> typ : nbParType)
            {
                if(propriete_case_type(inttotype(typ.first)) == TRANSMUTABLE_CATALYSEUR)
                //if(aDonner.element1 != inttotype(typ.first) && aDonner.element2 != inttotype(typ.first))
                {
                    aDonner.element2 = inttotype(typ.first);
                    break;
                }
            }
        }
    }
    donner_echantillon(aDonner);

    consommerMetauxVils();

    /// PLACEMENT DE L'ÉCHANTILLON RECU
    if(estEntierementVide()) { /// Plateau vide : on fait confiance au milieu
        placer_echantillon({2,2}, {3,2});
    }

    else {
        vector<position_echantillon> possibilitesPlacement = placements_possible_echantillon(aPlacer, moi());
        if(possibilitesPlacement.empty())
        {
            /// Deux situations :
            /// - soit toute case du même élément qu'un des deux de l'échantillon donné est entourée par d'autres éléments,
            /// - soit le plateau n'a plus de place.
            vector<position> possibilitesReglage; /// Contient toutes les cases avec le même élément qu'un des deux de ĺ'échantillon fourni
            for(int lig = 0; lig < TAILLE_ETABLI; lig++)
            {
                for(int col = 0; col < TAILLE_ETABLI; col++)
                {
                    int typeCase = type_case({lig, col}, moi());
                    if(typeCase == aPlacer.element1 || typeCase == aPlacer.element2)
                        possibilitesReglage.push_back({lig, col});
                }
            }
            if(!possibilitesReglage.empty()) {
                /// On essaie (pour l'instant) de vider le moins possible ce qu'il y a autour en gagnant le plus d'or possible.
                /// A voir ce que l'on peut éventuellement faire avec les catalyseurs.
                vector<vector<bool> > prisEnCompte(TAILLE_ETABLI, vector<bool> (TAILLE_ETABLI, false));
                vector<pair<int, position> > scoresPotentiels;
                for(position pos : possibilitesReglage)
                {
                    case_type typeCase = type_case(pos, moi());
                    for(int dlig = -1; dlig <= 1; dlig++)
                    {
                        for(int dcol = -1; dcol <= 1; dcol++)
                        {
                            if(dlig == 0 && dcol == 0) continue;
                            position posAdj = {pos.ligne + dlig, pos.colonne + dcol};
                            if(posAdj.ligne < 0 || posAdj.ligne >= TAILLE_ETABLI || posAdj.colonne < 0 || posAdj.colonne >= TAILLE_ETABLI) continue;
                            if(prisEnCompte[posAdj.ligne][posAdj.colonne]) continue;
                            case_type typeCaseAdj = type_case(posAdj, moi());
                            if(typeCaseAdj == typeCase || typeCaseAdj == VIDE) continue;

                            vector<position> positionsRegion = positions_region(posAdj, moi());
                            scoresPotentiels.push_back(pair<int, position> ((int)positionsRegion.size(), posAdj));
                            for(position posRegion : positionsRegion)
                                prisEnCompte[posRegion.ligne][posRegion.colonne] = true;
                        }
                    }
                }
                sort(scoresPotentiels.begin(), scoresPotentiels.end(), compareSizePosition2);
                for(pair<int, position> positionPotentielle : scoresPotentiels)
                {
                    transmuter(positionPotentielle.second);
                    possibilitesPlacement = placements_possible_echantillon(aPlacer, moi());
                    if(!possibilitesPlacement.empty())
                        break;
                }
            }
            if(possibilitesPlacement.empty()) {
                /// en gros, tableau rempli : on vide tant qu'il y a pas de place
                do {
                    int maxi = 0;
                    position posMaxi;
                    for(int lig = 0; lig < TAILLE_ETABLI; lig++) {
                        for(int col = 0; col < TAILLE_ETABLI; col++) {
                            int taille = taille_region({lig, col}, moi());
                            if(type_case({lig, col}, moi()) != VIDE && taille > maxi) {
                                maxi = taille;
                                posMaxi = {lig, col};
                            }
                        }
                    }
                    transmuter(posMaxi);
                } while ((possibilitesPlacement = placements_possible_echantillon(aPlacer, moi())).empty());
            }
        }

        /// Placer l'échantillon là où la somme des tailles des zones formées est maximale.
        int maxi = 0;
        position_echantillon possibiliteCorres;
        for(position_echantillon possibilite : possibilitesPlacement) {
            placer_echantillon(possibilite.pos1, possibilite.pos2);
            int tailleTotale = taille_region(possibilite.pos1, moi());
            if(aPlacer.element1 != aPlacer.element2)
                tailleTotale += taille_region(possibilite.pos2, moi());
            if(tailleTotale > maxi) {
                maxi = tailleTotale;
                possibiliteCorres = possibilite;
            }
            annuler();
        }
        placer_echantillon(possibiliteCorres.pos1, possibiliteCorres.pos2);
    }

    consommerMetauxVils();

    if(tour >= NB_TOURS-1) /// fin des tours : on enlève tout ce qu'on peut
        transmuterPositif();


    /// CATALYSATION AUTANT QUE POSSIBLE
    while(nombre_catalyseurs() > 0) {
        //cout << nombre_catalyseurs() << " catalyseur(s) inutilisés\n";
        //afficher_etablis();
        majGraphe(moi());
        //debugGrille(MOI_GRAPHE);
        int iZone1 = -1, iZone2 = -1;
        /// Recherche de la plus grosse zone
        vector<tuple<int, int, int> > tailleEtId;
        for(int iZone = 0; iZone < (int)zones[MOI_GRAPHE].size(); iZone++) {
            position arbitraire = zones[MOI_GRAPHE][iZone][0];
            int estMetal = propriete_case(arbitraire, moi()) == TRANSMUTABLE_OR ? 1 : 0;
            tailleEtId.push_back(tuple<int, int, int> (estMetal, zones[MOI_GRAPHE][iZone].size(), iZone));
        }

        if(tailleEtId.size() == 0) {
            //cout << "Aucune zone\n";
            break;
        }

        sort(tailleEtId.begin(), tailleEtId.end(), greater<tuple<int, int, int> >() );
        for(int i = 0; i < (int)tailleEtId.size(); i++) {
            if(voisins[MOI_GRAPHE][get<2>(tailleEtId[i])].size() > 0) {
                /// Recherche de la plus petite zone adjacente à la première
                iZone1 = get<2>(tailleEtId[i]);
                int tailleMin = 2*1000*1000*1000;
                for(int voisin : voisins[MOI_GRAPHE][iZone1]) {
                    int taille = zones[MOI_GRAPHE][voisin].size();
                    if(taille < tailleMin) {
                        iZone2 = voisin;
                        tailleMin = taille;
                    }
                }
                break;
            }
        }

        if(iZone2 == -1) {
            //cout << "Zones toutes séparées ou une seule zone\n";
            break;
        }

        //cout << "Catalysation entre zones " << iZone1 << " et " << iZone2 << "\n";
        position arbitraireZone1 = zones[MOI_GRAPHE][iZone1][0];
        case_type elementZone1 = type_case(arbitraireZone1, moi());

        /// BFS en partant d'une case arbitraire de la zone 1, en restant sur les zones 1 et 2
        vector<vector<bool> > visite(TAILLE_ETABLI, vector<bool> (TAILLE_ETABLI, false));
        visite[arbitraireZone1.ligne][arbitraireZone1.colonne] = true;
        deque<position> aTraiter;
        aTraiter.push_back(arbitraireZone1);
        while(nombre_catalyseurs() > 0 && !aTraiter.empty()) {
            position traiter = aTraiter.front();
            aTraiter.pop_front();
            if(zoneCase[MOI_GRAPHE][traiter.ligne][traiter.colonne] == iZone2) {
                catalyser(traiter, moi(), elementZone1);
            }
            for(position delta : DELTAS_ADJ_DIRECT) {
                position adj = {traiter.ligne + delta.ligne, traiter.colonne + delta.colonne};
                if(positionValide(adj) && (zoneCase[MOI_GRAPHE][adj.ligne][adj.colonne] == iZone1 || zoneCase[MOI_GRAPHE][adj.ligne][adj.colonne] == iZone2) && !visite[adj.ligne][adj.colonne]) {
                    aTraiter.push_back(adj);
                    visite[adj.ligne][adj.colonne] = true;
                }
            }
        }
    }

    if(tour >= NB_TOURS-1)
        transmuterPositif();

    /// Mesure du temps
    auto fin = chrono::high_resolution_clock::now();
    long duree = chrono::duration_cast<chrono::microseconds>(fin - debut).count();
    //cout << "Tour " << tour << ", durée de " << duree << " µs\n";
    dureeMax = max(dureeMax, duree);
    dureeMin = min(dureeMin, duree);
    /// Temps d'exécution de 20 à 550 µs environ (sur 500000 µs max)
}
