#ifndef UTILS_H
#define UTILS_H

#include <algorithm>
#include <vector>
#include <cstring>
#include "prologin.hh"

const int INF = 1e9;

position DIRS[4] = {{-1,0},{1,0},{0,-1},{0,1}};

position operator+(position& a, position& b)
{
    return position { a.ligne + b.ligne, a.colonne + b.colonne };
}

int BONUS[TAILLE_MINE][TAILLE_MINE];

struct dag_dist
{
    int bonus;
    int pm, pa;
    double score;
    
    void reset() { memset(this, 0, sizeof(*this)); }

    void maj()
    {
        score = ((double) bonus) / (pm + pa +1);
    }
};

struct dag_sit
{
    position pos;
    bool accr;
    bool retour;

    dag_dist dist;

    void reset() { memset(this, 0, sizeof(*this)); }

    int maj()
    {
        if(pos.ligne < 0 || TAILLE_MINE <= pos.ligne || pos.colonne < 0 || TAILLE_MINE <= pos.colonne)
            return -1;

        if(type_case(pos) == OBSIDIENNE)
            return -1;

        int ret = 0;

        if(type_case(pos) == GRANITE)
        {
            ret = 1;
            minerai minfo = info_minerai(pos);
            if(minfo.resistance != -1)
                dist.pa += COUT_MINER * minfo.resistance;
            else
                dist.pa += COUT_MINER;
        }

        if(nain_sur_case(pos) == adversaire())
        {
            ret = 1;
            for(int i = 0; i < NB_NAINS; i++)
                if(info_nain(adversaire(), i).pos == pos)
                    dist.pa += (info_nain(adversaire(), i).vie + DEGAT_PIOCHE-1) / DEGAT_PIOCHE;
        }
        
        bool chuteok = accr;
        if(!accr)
        {
            for(int i = 0; i < 4 && !chuteok; i++)
            {
                pos = pos + DIRS[BAS];
                if(type_case(pos) != LIBRE || nain_sur_case(pos) == adversaire())
                    chuteok = true;
            }
            pos = pos + DIRS[HAUT];
        }
        if(!chuteok)
            return -1;

        return ret;
    }

    inline int hash()
    {
        return ((((pos.ligne * TAILLE_MINE) + pos.colonne
                    ) * 2 + accr
                    ) * 2 + retour
                    ) * (BUTIN_MAX+1) + dist.bonus;
    }
};

dag_dist operator+(dag_dist a, dag_dist b)
{
    a.pa += b.pa;
    a.pm += b.pm;
    a.bonus += b.bonus;
    a.bonus = std::min(a.bonus, BUTIN_MAX);
    a.maj();
    return a;
}

bool operator<(const dag_dist& a, const dag_dist& b) { return a.score < b.score; }
bool operator<(const dag_sit& a, const dag_sit& b) { return a.dist.score > b.dist.score; }


const int DAG_HASH = TAILLE_MINE * TAILLE_MINE * 2 * 2 * (BUTIN_MAX+1);

dag_dist dag_score[DAG_HASH];
std::pair<dag_sit, action_hist> dag_next[DAG_HASH];
bool dag_vu[DAG_HASH];

dag_dist optimal_int(dag_sit source, dag_sit dest);

void dag_valide(dag_sit source, dag_sit dest, dag_sit nouv, action_hist act, dag_dist offset)
{
    offset.bonus += BONUS[nouv.pos.ligne][nouv.pos.colonne];
    offset.bonus = std::min(offset.bonus, BUTIN_MAX);
    offset.maj();

    int maj = nouv.maj(); 
    act.sens = BAS; 
    if(maj == 1) 
        act.sens = HAUT; 
    if(maj != -1) 
    { 
        dag_dist rec = optimal_int(nouv, dest) + offset; 
        rec.maj();

        int hash = source.hash();
        if(dag_score[hash] < rec) 
        {
            dag_score[hash] = rec;
            nouv.dist.reset();
            dag_next[hash].first = nouv; 
            dag_next[hash].second = act; 
        } 
    } 
}

dag_dist optimal_int(dag_sit source, dag_sit dest)
{
    if(source.pos == dest.pos && source.accr == dest.accr && source.retour == dest.retour)
    {
        dag_dist dist;
        dist.reset();
        return dist;
    };

    int hash = source.hash();

    if(!dag_vu[hash])
    {
        dag_vu[hash] = true;

        dag_score[hash].bonus = -INF;
        dag_score[hash].maj();
        dag_next[hash].first.pos.ligne = -42;

        dag_sit nouv;      nouv.reset();
        dag_dist offset; offset.reset();
        action_hist act; memset(&act, 0, sizeof(act));

        if(!source.retour)
        {
            act.id_nain = -1;
            nouv = source;
            nouv.retour = true;
            offset.reset();
            dag_valide(source, dest, nouv, act, offset);
            act.id_nain = 0;
        }

        if(source.accr)
        {
            /*act.atype = ACTION_LACHER;
            nouv = source;
            nouv.accr = false;
            offset.reset();
            dag_valide(source, dest, nouv, act, offset);*/

            for(int i = 0; i < 4; i++)
            {
                act.atype = ACTION_DEPLACER;
                nouv = source;

                act.dir = (direction) i;
                nouv.pos = source.pos + DIRS[i];
                offset.reset();
                offset.pm = (corde_sur_case(nouv.pos) ? COUT_ESCALADER_CORDE : COUT_ESCALADER);
                dag_valide(source, dest, nouv, act, offset);
            }
        }
        else
        {/*
            act.atype = ACTION_AGRIPPER;
            nouv = source;
            nouv.accr = true;
            offset.reset();
            dag_valide(source, dest, nouv, act, offset);

            act.atype = ACTION_DEPLACER;

            act.dir = DROITE;
            nouv = source;
            nouv.pos = source.pos + DIRS[DROITE];
            offset.reset();
            offset.pm += COUT_DEPLACEMENT;
            dag_valide(source, dest, nouv, act, offset);

            act.dir = GAUCHE;
            nouv = source;
            nouv.pos = source.pos + DIRS[GAUCHE];
            offset.reset();
            offset.pm += COUT_DEPLACEMENT;
            dag_valide(source, dest, nouv, act, offset);*/
        }
    }

    printf("pos %d %d  r %d  %.7lf\n",  source.pos.ligne, source.pos.colonne, source.retour, dag_score[source.hash()].score);

    return dag_score[source.hash()];
}


std::vector<action_hist> optimal(dag_sit source, dag_sit dest)
{
    memset(dag_vu, 0, sizeof(dag_vu));
    memset(dag_score, 0, sizeof(dag_score));
    memset(dag_next, 0, sizeof(dag_next));

    optimal_int(source, dest);

    std::vector<action_hist> act;

    auto curr = dag_next[source.hash()];
    while(curr.first.pos != dest.pos || curr.first.accr != dest.accr || curr.first.retour != dest.retour)
    {
        dag_sit& sit = curr.first;
        debug_afficher_drapeau(sit.pos, DRAPEAU_BLEU);

        printf("ACT %d  dir %d  nain %d   pos %d %d\n", curr.second.atype, curr.second.dir,
                    curr.second.id_nain, sit.pos.ligne, sit.pos.colonne);

        if(curr.second.id_nain != -1)
        {
            if(curr.second.sens == HAUT)
            {
                action_hist a2 = curr.second;
                a2.atype = ACTION_MINER;
                act.push_back(a2);
            }

            act.push_back(curr.second);
        }
        curr = dag_next[sit.hash()];
    }

    return act;
}

#endif
