/*
 * Cette IA est un torchon improvisé en 4 heures.
 *
 * On y trouve du Dijkstra bricolé, et c'est probablement tout.
 * J'avais initialement fait un Floyd-Warshall, mais j'ai laissé tomber
 * par peur d'être un peu juste en temps (même en C !).
 *
 * Avec plus de temps j'aurais trituré les coefficients qui pondèrent les
 * arcs « magiques » dans mon Dijkstra : i.e. j'aurais commencé par coder
 * ce torchon hier matin que ce soir j'aurais eu quelque chose de fonctionnel.
 */
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#include "prologin.h"


typedef struct position P;
typedef struct {
  P p; int v, b, e;
} A;

#define x       ligne
#define y       colonne

#define $(p)    (p.x*25+p.y)
#define _(u,v)  ((P){.x=(u),.y=(v)})


static struct {
  P elem[200000];
  int size;
} stack;

P d[4] = {{0,1},{1,0},{0,-1},{-1,0}};
static int dist[625], seen[625], prev[625], tdst[625];

static struct {
  A elem[625];
  int count;
} aliens;


static inline bool blocked(P p) {
  return type_case(p) != LIBRE || agent_sur_case(p) != -1;
}

static inline int my_abs(int x) {
  return x > 0 ? x : -x;
}

static inline int my_max(int a, int b) {
  return a > b ? a : b;
}
static inline int my_min(int a, int b) {
  return a < b ? a : b;
}

static inline int true_dist(P x) {
  int t;

  if (blocked(x) || !seen[$(x)])
    return 0xfffffff;
  t = tdst[$(x)] / 8;
  return (t - 1 >= 0) ? t - 1 : 0;
}

/* Rapproche un agent d'une case en utilisant les données du Dijkstra */
static inline void move(int a, P x) {
  P p = position_agent(moi(), a), q;
  int n = $(x);

  if (!seen[n])
    return;
  while (prev[n] != prev[prev[n]])
    n = prev[n];

  q = _(n/25,n%25);
  if (p.x - q.x > 0)
    (p.x - q.x == 1) ? deplacer(a, NORD) : glisser(a, NORD);
  else if (p.x - q.x < 0)
    (p.x - q.x == -1) ? deplacer(a, SUD) : glisser(a, SUD);
  else if (p.y - q.y > 0)
    (p.y - q.y == 1) ? deplacer(a, OUEST) : glisser(a, OUEST);
  else if (p.y - q.y < 0)
    (p.y - q.y == -1) ? deplacer(a, EST) : glisser(a, EST);
}

static inline void dijkstra(P p) {

  for (int i = 0; i < 625; i++) {
    dist[i] = 0xfffffff;
    seen[i] = false;
    prev[i] = -1;
    tdst[i] = 0xfffffff;
  }

  stack.elem[0] = p;
  stack.size = 1;

  dist[$(p)] = 0;
  seen[$(p)] = true;
  prev[$(p)] = $(p);
  tdst[$(p)] = 0;

  while (stack.size) {
    P cur;
    int m = 0;

    for (int i = 0; i < stack.size; i++)
      if (dist[$(stack.elem[i])] < dist[$(stack.elem[m])])
        m = i;
    cur = stack.elem[m];
    stack.elem[m] = stack.elem[--stack.size];

    for (int i = 0; i < 4; i++) {
      P next = _(cur.x+d[i].x,cur.y+d[i].y);

      if ((!blocked(next) || agent_sur_case(next) == adversaire())
          && !seen[$(next)]) {
        int delay = 500;

        /* On fait un truc obscur pour favoriser le passage sur des aliens */
        tdst[$(next)] = tdst[$(cur)] + 1;
        for (int j = 0; j < aliens.count; j++)
          if ($(aliens.elem[j].p) == $(next)) {
            delay = my_max(aliens.elem[j].b - (tour_actuel()
                           + tdst[$(next)] / 8), 0);
            if (aliens.elem[j].e > tour_actuel() + tdst[$(next)] / 8)
              delay = 500;
            break;
          }
        delay = my_min(delay, 500);
        delay *= delay;
        dist[$(next)] = dist[$(cur)] + 1 + delay;
        seen[$(next)] = true;
        prev[$(next)] = $(cur);
        stack.elem[stack.size++] = next;
      }
    }

    for (int i = 0; i < 4; i++)
      for (int j = 1; j < 25; j++) {
        P next = _(cur.x+j*d[i].x,cur.y+j*d[i].y);

        if (blocked(next)) {
          next = _(cur.x+(j-1)*d[i].x,cur.y+(j-1)*d[i].y);
          if (!seen[$(next)]) {
            int delay = 500;

            /* Idem */
            tdst[$(next)] = tdst[$(cur)] + 3;
            for (int j = 0; j < aliens.count; j++)
              if ($(aliens.elem[j].p) == $(next)) {
                delay = my_max(aliens.elem[j].b - (tour_actuel()
                               + tdst[$(next)] / 8), 0);
                if (aliens.elem[j].e > tour_actuel() + tdst[$(next)] / 8)
                  delay = 500;
                break;
              }
            delay = my_min(delay, 500);
            delay *= delay;
            dist[$(next)] = dist[$(cur)] + 3 + delay;
            seen[$(next)] = true;
            prev[$(next)] = $(cur);
            stack.elem[stack.size++] = next;
          }
          break;
        }
      }
  }
}

/* À chaque tour, on se construit une belle liste fraîche d'aliens */
static inline void update_aliens(void) {
  alien_info_array a = liste_aliens();

  aliens.count = 0;
  for (int i = 0; i < a.length; i++) {
    int end = a.datas[i].tour_invasion + a.datas[i].duree_invasion - 3;

    if (a.datas[i].capture_en_cours
        && tour_actuel() + (3 - a.datas[i].capture_en_cours) < end
        && alien_sur_case(a.datas[i].pos))
      end = tour_actuel() + (3 - a.datas[i].capture_en_cours);
    if ((end >= tour_actuel())
        && (a.datas[i].points_capture > 0)
        && (a.datas[i].capture_en_cours != NB_TOURS_CAPTURE)) {
      aliens.elem[aliens.count++] = (A){.p=a.datas[i].pos,
                                        .v=a.datas[i].points_capture,
                                        .b=a.datas[i].tour_invasion,
                                        .e=end};
    }
  }
  free(a.datas);
}

static int focus[4] = {-1, -1, -1, -1};


void jouer_tour(void) {

  update_aliens();

  /*
   * Le principe est de faire un Dijkstra après chaque coup, pour chaque
   * agent.
   * Comme ça on tient compte de la nouvelle position des agents au fur et à
   * mesure.
   */
  for (int m = 0; m < 8; m++)
    for (int k = 0; k < 4; k++) {
      P p = position_agent(moi(), k);

      if (!alien_sur_case(p)) {
        int best = 0, best_dist = aliens.count ? true_dist(aliens.elem[0].p) : 0xfffffff, best_taken = true;

        dijkstra(p);
        for (int i = 0; i < aliens.count; i++) {
          int alien_dist = true_dist(aliens.elem[i].p), taken = false;

          /* On évite de marcher sur les plate-bandes des autres */
          for (int j = 0; j < k; j++)
            if (focus[j] == i) {
              taken = true;
              break;
            }

          /* Cette condition moche détermine l'alien à suivre */
          if ((!taken && ((alien_dist + tour_actuel() <= aliens.elem[i].e)
              && ((best_dist + tour_actuel() > aliens.elem[best].e)
                  || (aliens.elem[i].b <= aliens.elem[best].b)
                  || ((aliens.elem[i].b - aliens.elem[best].b <= 2)
                      && (aliens.elem[i].v > aliens.elem[best].v * 2)))))
              || (taken && best_taken
                  && (alien_dist + tour_actuel() <= aliens.elem[i].e)
                  && (aliens.elem[i].b <= aliens.elem[best].b))) {
            best = i;
            best_dist = alien_dist;
            best_taken = taken;
          }
        }

        if (aliens.count) {
          move(k, aliens.elem[best].p);
          focus[k] = best;
        }
      }

      /* On pousse sauvagement ce qu'il y a autour, par précaution */
      for (int i = 0; i < 4; i++)
        pousser(k, i);
    }
}

void partie_init(void) {
}

void partie_fin(void) {
}

