/**
 * Une stratégie qui n'a pas franchement bougé depuis la première samedi après-midi.
 * L'ordre général est le suivant:
 *  - donner un échantillon,
 *  - placer celui qu'on a recu,
 *  - effectuer des catalyses.
 *
 * En détail, voici ce que ca donne :
 *
 * I - Le don d'échantillon
 *   Au premier tour, l'IA donne un échantillon aléatoire qui respecte bien sûr les règles.
 *   Aux autres tours, elle donne en 1er élément l'élément de l'échantillon recu le moins présent sur l'établi de
 * l'adversaire.
 *   Elle donne en deuxième l'élément (différent du premier) le moins présent sur l'établi de l'adversaire.
 *
 * II - Placement de l'échantillon
 *   Si l'établi est entièrement vide, on place l'élément au milieu à peu près (l3 c3 et l4 c3 en comptant à partir de 1).
 *   S'il n'y a initialement aucun emplacement qui puisse accueillir l'échantillon fourni, alors:
 *      Si l'établi ne contient actuellement aucun des deux éléments de l'échantillon, alors on vide l'établi de la zone la
 *     plus étendue à celle la plus réduite jusqu'à ce qu'on puisse placer l'échantillon (ne devrait pas prendre longtemps).
 *      Dans le cas contraire, on effectue la même chose, mais uniquement aux abords immédiats des cases dont l'élément est
 *     le même qu'un de ceux de l'échantillon.
 *      Je fais cela afin de maximiser l'or produit.
 **/
#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}};
/// Mesure du temps pris par tour
long dureeMin = 2L*1000L*1000L*1000L, dureeMax = 0L;
/// Deux graphes, un pour moi, un pour l'adversaire (cf. plus en bas)
vector<vector<position> > zones[2];
vector<vector<int> > voisins[2];
vector<vector<int> > zoneCase[2];
random_device rd;

namespace utils {
/// Renvoie si une position donnée se situe dans l'établi.
bool positionValide(position pos) {
    return pos.ligne >= 0 && pos.ligne < TAILLE_ETABLI && pos.colonne >= 0 && pos.colonne < TAILLE_ETABLI;
}

/// Renvoie si l'établi est entièrement vide.
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;
}

/// Conversion de case_type en int.
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;
    }
}

/// Conversion inverse (par exemple pour le hasard).
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";
}
/// Un graphe où les zones sont des noeuds, reliés aux autres zones si elles partagent un bord.
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);
                    }
                }
            }
        }
    }
}

/// En fin de partie : transmuter tous les éléments qui ne nous font pas perdre d'or.
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});
        }
    }
}

/// Consommer tous les métaux vils en zones de taille supérieure à un certain nombre (ici 4).
void consommerMetauxVils() {
    majGraphe(moi());
    for(vector<position> zone : zones[MOI_GRAPHE]) {
        position arbitraire = zone[0];
        if(propriete_case(arbitraire, moi()) == TRANSMUTABLE_CATALYSEUR && zone.size() >= 4) {
            transmuter(arbitraire);
        }
    }
}
}
using namespace utils;

/// Les 3 fonctions sont dans l'ordre où elles sont utilisées.
namespace strategie {
    void donnerEchantillon(echantillon &aPlacer, int &tour) {
        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> (1,5);
            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) {
        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 de vider le moins possible ce qu'il y a autour en gagnant le plus d'or possible.
                    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;
            vector<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.clear();
                    possibiliteCorres.push_back(possibilite);
                }
                else if(tailleTotale == maxi) {
                    possibiliteCorres.push_back(possibilite);
                }
                annuler();
            }
            uniform_int_distribution<int> distr (0, possibiliteCorres.size()-1);
            position_echantillon pos = possibiliteCorres[distr(rd)];
            placer_echantillon(pos.pos1, pos.pos2);
        }
    }

    int catalyserTout() {
        majGraphe(moi());
        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)
            return 0;

        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)
            return 0;

        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);
        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++;
            }
            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 partie_init() /// rien
{
    //nada
}
void partie_fin() /// stats de temps
{
    cout << "Durées de " << dureeMin << " µs à " << dureeMax << " µs\n";
}
/// Fonction appelée à chaque tour.
void jouer_tour()
{
    auto debut = chrono::high_resolution_clock::now();
    echantillon aPlacer = echantillon_tour();
    int tour = tour_actuel();


    /// DON D'ÉCHANTILLON
    strategie::donnerEchantillon(aPlacer, tour);

    /// PLACEMENT DE L'ÉCHANTILLON RECU
    strategie::placerEchantillon(aPlacer);

    consommerMetauxVils();

    if(tour >= NB_TOURS-1) /// fin des tours : on enlève tout ce qu'on peut
        transmuterPositif();
    /// CATALYSATION DE NOTRE CÔTÉ
    while(nombre_catalyseurs() > 0)
        if(strategie::catalyserTout() == 0)
            break;
    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();
    dureeMax = max(dureeMax, duree);
    dureeMin = min(dureeMin, duree);
}
