#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}};
uniform_int_distribution<int> distMetauxNormaux(1,3);
uniform_int_distribution<int> distMetauxVils(4,5);
uniform_int_distribution<int> distTousMetaux(1,5);

long dureeMin = 2L*1000L*1000L*1000L, dureeMax = 0L;
vector<vector<position> > zones[2];
vector<vector<int> > voisins[2];
vector<vector<int> > zoneCase[2];
random_device rd;

/// Paramètres des algos
const int TAILLE_MIN_ZONE_CATALYSABLE = 4;

namespace utils {
    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;
    }

    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;
        }
    }

    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);
                        }
                    }
                }
            }
        }
    }

    case_type typeZoneGraphe(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());
    }
}

using namespace utils;

namespace strategie {

    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;
    }

    /// De la plus petite à la plus grande.
    bool compareTypePresence(const pair<int, int> &l, const pair<int, int> &r) {
        return l.second < r.second;
    }

    /// De la plus grande à la plus petite.
    bool compareSizePosition2(const pair<int, position> &l, const pair<int, position> &r) {
        return l.first > r.first;
    }

    /** Les vils en groupes de 2 ou + par taille décroissante, puis les normaux en groupes de 2 ou + par taille
     *  décroissante, puis les groupes de 1.
     **/
    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;
    }

    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(vector<position> zone : zones[MOI_GRAPHE]) {
            position arbitraire = zone[0];
            if(propriete_case(arbitraire, moi()) == TRANSMUTABLE_CATALYSEUR && zone.size() >= TAILLE_MIN_ZONE_CATALYSABLE)
                transmuter(arbitraire);
        }
    }

    void donnerEchantillon(echantillon aPlacer, int tour) {
        echantillon aDonner;


        if(tour == 1) { /// Premier tour : un peu random
            uniform_int_distribution<int> dist(0,1);
            if(dist(rd) == 0)
                aDonner.element1 = FER;
            else
                aDonner.element1 = PLOMB;
            dist = distMetauxVils;
            aDonner.element2 = inttotype(dist(rd));;
        }

        else { /// Les éléments les moins présents chez l'adversaire
            vector<pair<int, int>> nbParType(NB_TYPE_CASES, pair<int, int> (0,0));
            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 ++;
                }
            }
            if(nbParType[typetoint(aPlacer.element1)].second < nbParType[typetoint(aPlacer.element2)].second)
                aDonner.element1 = aPlacer.element1;
            else
                aDonner.element1 = aPlacer.element2;

            sort(nbParType.begin(), nbParType.end(), compareTypePresence);
            for(pair<int, int> typ : nbParType)
            {
                if(aDonner.element1 != inttotype(typ.first) && aDonner.element2 != inttotype(typ.first))
                {
                    aDonner.element2 = inttotype(typ.first);
                    break;
                }
            }
        }

        donner_echantillon(aDonner);

    }

    void placerEchantillon(echantillon aPlacer) {

        /// 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()) { /// S'il y a des cases du même élément qu'un de ceux de l'échantillon
                    /// 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)); // on ne met chaque zone qu'une seule fois
                    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++) {
                                /// On teste si ca peut être une case à transmuter.
                                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);
        }

    }

    /// Retourne le nombre de catalyses effectives.
    int catalyserExtension(int nbMaxCatas) {
        majGraphe(moi());
        int iZone1 = -1, iZone2 = -1;
        /// Recherche de la plus grosse zone, évidemment de métaux normaux (on n'utilise pas de métaux vils pour en faire moins, ca va de soi
        vector<pair<int, int> > tailleEtId;
        for(int iZone = 0; iZone < (int)zones[MOI_GRAPHE].size(); iZone++) {
            position arbitraire = zones[MOI_GRAPHE][iZone][0];
            if(propriete_case(arbitraire, moi()) == TRANSMUTABLE_OR)
                tailleEtId.push_back(pair<int, int> (zones[MOI_GRAPHE][iZone].size(), iZone));
        }

        if(tailleEtId.size() == 0)
            return 0;

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

        if(iZone2 == -1)
            return 0;

        //cout << "Catalysation entre zones " << iZone1 << " et " << iZone2 << "\n";
        /// BFS en partant d'une case arbitraire de la zone 1, en restant sur les zones 1 et 2
        {
            position arbitraireZone1 = zones[MOI_GRAPHE][iZone1][0];
            case_type elementZone1 = type_case(arbitraireZone1, moi());
            vector<vector<bool> > visite(TAILLE_ETABLI, vector<bool> (TAILLE_ETABLI, false));
            visite[arbitraireZone1.ligne][arbitraireZone1.colonne] = true;
            deque<position> aTraiter;
            aTraiter.push_back(arbitraireZone1);
            int nbCatas = 0;
            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);
                    nbCatas++;
                    if(nbCatas >= nbMaxCatas)
                        return nbCatas;
                }
                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;
                    }
                }
            }
            return nbCatas;
        }
    }

    void catalyserToutExtension() {
        /// CATALYSATION AUTANT QUE POSSIBLE
        while(nombre_catalyseurs() > 0) {
            if(catalyserExtension(100000000) == 0)
                break;
        }
    }

    int catalyserAgression(int nbMaxCatas) {
        if(nombre_catalyseurs() == 0)
            return 0;
        majGraphe(adversaire());
        vector<pair<int, int> > taillesEtIds;
        for(int iZone = 0; iZone < (int)zones[ADVERSAIRE_GRAPHE].size(); iZone++)
            taillesEtIds.push_back(pair<int, int> (zones[ADVERSAIRE_GRAPHE][iZone].size(), iZone));
        sort(taillesEtIds.begin(), taillesEtIds.end(), greater<pair<int, int> > ());
        /// Pour l'instant random (tournoi dans 10 min)
        int nbCatas = 0;
        for(pair<int, int> entree : taillesEtIds) {
            if(entree.first > 1) {
                vector<position> &positions = zones[ADVERSAIRE_GRAPHE][entree.second];
                uniform_int_distribution<int> dist(0, (int)positions.size()-1);
                position aCatalyser = positions[dist(rd)];
                element_propriete prop = propriete_case(aCatalyser, adversaire());
                if(prop == TRANSMUTABLE_OR) {
                    catalyser(aCatalyser, adversaire(), inttotype(distMetauxVils(rd)));
                    nbCatas++;
                    if(nbCatas >= nbMaxCatas || nombre_catalyseurs() == 0)
                        return nbCatas;
                }
            }
        }
        return nbCatas;
    }

    void catalyserToutMoitieMoitie() {
        int nbCatasDebut = nombre_catalyseurs();
        for(int iCata = 0; iCata < nbCatasDebut; iCata++)
            if(iCata % 2 == 0)
                cout << catalyserAgression(1) << " agressions\n";
            else
                cout << catalyserExtension(1) << " extensions\n";
    }

    int catalyserDefense(int nbMaxCatas) {

    }
}


void partie_init() { /// nada
}

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

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

    strategie::donnerEchantillon(aPlacer, tour);
    //strategie::consommerMetauxVils();
    strategie::placerEchantillon(aPlacer);
    strategie::consommerMetauxVils();
    if(tour >= NB_TOURS-1) /// fin des tours : on enlève tout ce qu'on peut
        strategie::transmuterPositif();
    strategie::catalyserToutMoitieMoitie();
    if(tour >= NB_TOURS-1)
        strategie::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)
}
