#include "api.hh"
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

#define Map vector<vector<etat_case>> 


struct EPosition{  // Enhanced position
    int colonne;
    int ligne;
    int niveau;
    position mama_pos;

    bool operator<(const EPosition& other){
        int diffx = (colonne - mama_pos.colonne), diffy = (ligne - mama_pos.ligne);
        int dist_sq = diffx * diffx + diffy * diffy;

        int other_diffx = (other.colonne - other.mama_pos.colonne), other_diffy = (other.ligne - other.mama_pos.ligne);
        int other_dist_sq = other_diffx * other_diffx + other_diffy * other_diffy;
        return dist_sq < other_dist_sq;
    }
};


struct AftermoveInfo{
    int remain_act_points;
    bool found_any_destination;
    bool target_reached;
};


#pragma region Constantes
const int CONQUETE_NIDS = 0;
const int RECHERCHE_PAIN = 1;
const int MINING = 2;
const int NEST_SEARCH_TURN_LIMIT = 41;
const int OPTIMAL_LENGTH = 10;
const vector<pair<int, int>> DIR = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
#pragma endregion

#pragma region Variables
int player_id, opponent_id;
vector<position> nids(0);
vector<position> nids_obtenus(0);
vector<position> trous(0);
int current_phase;
map<int, vector<direction>> paths;
map<int, position> aim2;
map<int, position> entrance_hole;
map<direction, pair<int, int>> MDIR;
vector<position> blacklist_cases(0); 
bool nest_found, bread_found;
bool nests_done;
bool canmine;
#pragma endregion


vector<position> sort_by_distance(vector<position>& pos, position& mama_pos){
    
    vector<EPosition> ep(pos.size());
    for(int i = 0; i < (int)pos.size(); i++){
        ep.at(i) = {pos.at(i).colonne, pos.at(i).ligne, pos.at(i).niveau, mama_pos};
    }

    sort(ep.begin(), ep.end());

    vector<position> ret(pos.size());
    for(int i = 0; i < (int)pos.size(); i++){
        ret.at(i) = {ep.at(i).colonne, ep.at(i).ligne, ep.at(i).niveau};
    }
    return ret;
}

// Fonction appelée au début de la partie.
void partie_init(void)
{
    player_id = moi();
    opponent_id = adversaire();
    current_phase = CONQUETE_NIDS;
    MDIR[NORD] = make_pair(0, 1);
    MDIR[SUD] = make_pair(0, -1);
    MDIR[EST] = make_pair(1, 0);
    MDIR[OUEST] = make_pair(-1, 0);
    nests_done = false;
    canmine = true;


    for(troupe tr : troupes_joueur(player_id)){
        paths[tr.id] = vector<direction>(0);
    }

    #pragma region Charge la carte
    for(int y = 0; y < HAUTEUR; y++){
        for(int x = 0; x < LARGEUR; x++){
            position pos = {y, x, 0};
            // ajoute au tableau si c'est un nid
            if(info_case(pos).contenu == NID){
                nids.push_back(pos);
            }else if(info_case(pos).contenu == TROU){
                trous.push_back(pos);
            }
        }
    }
    #pragma endregion
}

vector<pair<int, int>> cote(const direction& cur_dir){
    vector<pair<int, int>> ret(0);
    for(pair<int, int> p : DIR){
        if(p.first * MDIR[cur_dir].first + p.second * MDIR[cur_dir].second == 0){  // Produit scalaire
            ret.push_back(p);
        }
    }
    return ret;
}


void debug_path(const troupe& tr, const vector<direction>& path){

    pair<int, int> pos = make_pair(tr.maman.colonne, tr.maman.ligne);
    for(direction dir : path){
        pos.first += MDIR[dir].first;
        pos.second += MDIR[dir].second;
        position tmp = {pos.first, pos.second, tr.maman.niveau};
        debug_poser_pigeon(tmp, PIGEON_ROUGE);
    }
}


troupe get_troupe_by_id(int id){
    for(troupe trp_ : troupes_joueur(player_id)){
        if(trp_.id == id) return trp_;
    }
}


bool is_in_troop(const troupe& tr, const position& target){
    for(position pos : tr.canards){
        if(pos == target) return true;
    }

    return false;
}


void update_nests(){
    nids_obtenus.clear();
    for(position nest_pos : nids){
        etat_nid etat = info_nid(nest_pos);
        if(etat == player_id + 1){
            nids_obtenus.push_back(nest_pos);
        }
    }
}


bool is_the_ennemy_killable(const troupe& adv_troupe){  // si les 2 cotes de l'adversaire sont non traversables
    vector<pair<int, int>> cotes_adv = cote(adv_troupe.dir);
    for(pair<int, int> p : cotes_adv){
        position tmp_pos = {adv_troupe.maman.colonne + p.first, adv_troupe.maman.ligne + p.second, adv_troupe.maman.niveau};
        debug_poser_pigeon(tmp_pos, PIGEON_ROUGE);
        etat_case etat = info_case(tmp_pos);
        type_case stat_tmp = etat.contenu;
        if(!(stat_tmp == BUISSON || (stat_tmp == BARRIERE && info_barriere(tmp_pos) == FERMEE))){
            return false;
        }
    }
    return true;
}


AftermoveInfo go2target(const troupe& tr, const vector<position>& target_list, int pts=PTS_ACTION){  // Renvoie les pts restants
    debug_poser_pigeon(tr.maman, PIGEON_JAUNE);
    troupe cur_tr = get_troupe_by_id(tr.id);
    int action_pt = pts;
    bool found = false, reached = false;
    
    for(position target_pos : target_list){
        int used = 0;

        if(is_in_troop(cur_tr, target_pos) ){
            continue;
        }
        
        // Verifie si la case est deja visee par un autre troupe de ce joueur.
        bool nxt = false;
        for (auto it = aim2.begin(); it != aim2.end(); ++it) {
            if(it -> first != tr.id && it -> second == target_pos){
                nxt = true;
                break;
            }
        } 
        if(nxt) continue;
        // printf("MAMAN %d %d\n", cur_tr.maman.colonne, cur_tr.maman.ligne);
        // printf("TARGET %d %d\n", target_pos.colonne, target_pos.ligne);
        vector<direction> path = trouver_chemin(cur_tr.maman, target_pos);

        erreur can_continue = OK;
        

        // avance
        if(path.size() > 0){
            aim2[tr.id] = target_pos;
            found = true;
        }
        while(can_continue == OK && path.size() > 0){
            can_continue = avancer(cur_tr.id, path.at(0));
            path.erase(path.begin());
            action_pt--;
            used++;
        }
        cur_tr = get_troupe_by_id(cur_tr.id);
        if(cur_tr.maman == target_pos) reached = true;

    }
        
    // if(action_pt > 0){
    //     for(int i = 0; i < 10; i++){
    //         position pig = {LARGEUR - 1, i, 0};
    //         debug_poser_pigeon(pig, PIGEON_ROUGE);
    //     }
    // }

    return {action_pt, found, reached};
}

AftermoveInfo find_hole(troupe tr, int action_pts){
    AftermoveInfo ami = go2target(tr, sort_by_distance(trous, tr.maman), action_pts);

    // AftermoveInfo ami = {1, 1, true};
    action_pts = ami.remain_act_points;
    bool hole_found = ami.found_any_destination;
    if(!hole_found){}  // TODO: faut creuser un nouveau trou

    if(ami.remain_act_points > 0){
        tr = get_troupe_by_id(tr.id);
        if(info_case(tr.maman).contenu == TROU){
            // avancer(tr.id, BAS);
            // ami.remain_act_points--;
            // entrance_hole[tr.id] = tr.maman;
        }
    }

    return ami; 
}


AftermoveInfo make_tunnel(const troupe& tr, const vector<position>& target_list, int act_pts){

    AftermoveInfo ami = go2target(tr, target_list, act_pts);

    if(ami.found_any_destination){
        
        return ami;
    }else{
        position goal = target_list.at(0);
        position cur = tr.maman;
        printf("werqwer %d %d\n", ami.remain_act_points, canmine);
        if(ami.remain_act_points > 0 && canmine){
            
            int dx = goal.colonne - cur.colonne, dy = goal.ligne - cur.ligne;
            direction d;
            if(dx > 0){
                d = EST;
            }else if(dx < 0){
                d = OUEST;
            }else if(dy > 0){
                d = NORD;               
            }else if(dy < 0){
                d = SUD;
            }else{
                cout << "What\n";
            }

            cur = {cur.colonne + MDIR[d].first, cur.ligne + MDIR[d].second, -1};
            erreur tunnel_err = creuser_tunnel(cur);
            // printf("%d %d ", cur.colonne, cur.ligne);
            printf("TUNNEL %d\n", tunnel_err);
            canmine = false;
            printf("%d\n", avancer(tr.id, d));
            ami.remain_act_points--;
            if(cur == goal) ami.target_reached = true;
            ami.found_any_destination = true;   
        }
        return ami;
    }
}


void jouer_tour(void)
{
    printf("Tour %d\n", tour_actuel());
    bread_found = false;
    nest_found = false;
    #pragma region essaye de tuer les advesaires
    int score_rest = score(player_id);
    for(troupe adv_tr : troupes_joueur(opponent_id)){
        if(score_rest < COUT_BUISSON){
            bool killable = is_the_ennemy_killable(adv_tr);
  
            if(killable && adv_tr.taille > 11 && adv_tr.inventaire > 2){  // Place un buisson juste devant l'ennemi
            // if(killable){
                position buisson_pos = {adv_tr.maman.colonne + MDIR[adv_tr.dir].first,
                                        adv_tr.maman.ligne + MDIR[adv_tr.dir].second,
                                        0};
                debug_poser_pigeon(buisson_pos, PIGEON_BLEU);
                erreur err = construire_buisson(buisson_pos);
                if(err == OK) score_rest -= COUT_BUISSON;

            }   
        }
        else{
            break;
        }
    }
    #pragma endregion
    canmine = true;
    for(troupe tr : troupes_joueur(player_id)){
        if(tr.maman.niveau == -1){
            printf("Coords %d %d %d\n", tr.maman.colonne, tr.maman.ligne, tr.maman.niveau);
        }
        for(int i = 0; i < tr.inventaire; i++){
            position dbg = {i, tr.id, 0};
            debug_poser_pigeon(dbg, tr.id == 1 ? PIGEON_ROUGE : PIGEON_BLEU);
        }
        int action_pts = PTS_ACTION;


        #pragma region CONQUETE NIDS
        if(current_phase == CONQUETE_NIDS){
            vector<position> available_nest(0);

            // mise a jour des nids libres
            for(position nest_pos : nids){
                etat_nid etat = info_nid(nest_pos);
                if(etat == LIBRE){
                    available_nest.push_back(nest_pos);
                }
            } 

            // cout << tour_actuel() << endl;
            if(available_nest.size() > 0 && tour_actuel() < NEST_SEARCH_TURN_LIMIT){
                AftermoveInfo ami = go2target(tr, sort_by_distance(available_nest, tr.maman), action_pts);
                action_pts = ami.remain_act_points;
                nest_found = ami.found_any_destination;
            }else{
                current_phase = RECHERCHE_PAIN;
            }

        }
        #pragma endregion
//

        #pragma region RECHERCHE PAIN
        if(current_phase == RECHERCHE_PAIN){
            if(tr.inventaire == inventaire(tr.taille)){
                update_nests();
                
                AftermoveInfo ami =go2target(tr, sort_by_distance(nids_obtenus, tr.maman), action_pts);
                action_pts = ami.remain_act_points;
                nest_found = ami.found_any_destination;
            }

            if(tr.taille < OPTIMAL_LENGTH && action_pts > COUT_CROISSANCE - 1 && tour_actuel() % 3 == 0){  // %3 here?
                grandir(tr.id);
                action_pts -= COUT_CROISSANCE;
            }
            if(tour_actuel() % 7 == 0 && action_pts > COUT_CROISSANCE - 1){
                grandir(tr.id);
                action_pts -= COUT_CROISSANCE; 
            }
            
            vector<position> br = pains();
            AftermoveInfo ami =  go2target(tr, sort_by_distance(br, tr.maman), action_pts);
            action_pts = ami.remain_act_points;
            bread_found = ami.found_any_destination;
        }
        #pragma endregion

        if(action_pts > COUT_CROISSANCE - 1){

            action_pts -= COUT_CROISSANCE;
            grandir(tr.id);
        }
        tr = get_troupe_by_id(tr.id);


        #pragma region TUNNEL MODE
        if(!bread_found && !nest_found){
            tr = get_troupe_by_id(tr.id);
           
            if(tr.maman.niveau == 0){  // Si le troupe doit trouver un trou
                action_pts = find_hole(tr, action_pts).remain_act_points;
            }else{  // Si le troupe est deja sous-terre
                vector<position> available_holes(0);
                for(position pos : trous){
                    position underground_pos = {pos.colonne, pos.ligne, -1};
                    if(pos != entrance_hole.at(tr.id)) available_holes.push_back(underground_pos);
                }
                // AftermoveInfo ami = go2target(tr, sort_by_distance(available_holes, tr.maman), action_pts);
                AftermoveInfo ami = make_tunnel(tr, available_holes, action_pts);
                action_pts = ami.remain_act_points;
                nest_found = ami.found_any_destination;
                
                if(ami.target_reached && action_pts > 0){
                    erreur err = avancer(tr.id, HAUT);
                    if(err == OK){
                        action_pts--;
                        current_phase = (nests_done ? RECHERCHE_PAIN : CONQUETE_NIDS);
                        cout << "HELLO WORLD!!!\n";
                    }
                }
            }
            if(tr.maman.niveau == 0 && info_case(tr.maman).contenu == TROU && canmine){
                position underground = {tr.maman.colonne, tr.maman.ligne, -1};
                creuser_tunnel(underground);
                canmine = false;
                erreur err = avancer(tr.id, BAS);
                debug_poser_pigeon(tr.maman, PIGEON_BLEU);
                if(err == OK){ 
                    action_pts--;
                    entrance_hole[tr.id] = tr.maman;
                    entrance_hole[tr.id].niveau = -1;
                    tr.maman.niveau = -1;
                    printf("i'm here\n");
                }
            }
        }
        #pragma endregion


        // if(){
        //     cout << "ahdfahfklashfaklshfkjahklfhaklhfklah\n" << endl;
        //     current_phase = TUNNEL;
        //     action_pts = find_hole(tr, action_pts).remain_act_points;
        // }

    }
    
}

// Fonction appelée à la fin de la partie.
void partie_fin(void)
{
    // TODO
    
    
}