/*
  Scrunch code for the NUTS potm.
  Finished 1st in the solo potm and 10th in the multi potm.

  The code for the solo potm is an implementation of "Guided Local Search" (GLS hereafter).
  Description available here: ftp://ftp.essex.ac.uk/pub/csc/technical-reports/CSM-247.ps.Z

  The code for the multi potm is not so interesting. Basically, it tries to sort the nuts to
  figure out which one are interesting.
 */

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define TEMP_FILE     "nuts_temp"

#define MAX_WIDTH     (25)
#define MAX_NUTS      (312)
#define MAX_SQUIRRELS (999)
#define LAMBDA        (3.0/8.0)
#define MAX_LOOPS     (50000)

typedef int(*qsortf)(const void *, const void *);

/******************************************************************************/

static int width;
static int height;

static int nr_nuts;
static int nr_squirrels;
static int nr_squares;

/* My squirrel position. Equivalent to squirrels[0]. */
static int me;

/* Lookup table for squirrels positions in the squares[] array.
   Used to avoid duplicate entries in squares[] if several squirrels sit on the same square.
   My squirrel is always located at index 0. */
static int squirrels[MAX_SQUIRRELS];

/* Squares that are going to figure in a path:

   squares[0..nr_nuts-1]            contains the nuts positions
   squares[nr_nuts]                 is an end of path marker
   squares[nr_nuts+1..nr_squares-1] contains the squirrels positions

   Note that this array does not contain any duplicate entry.

   Indexes within squares[] are the key to identify grid locations, eg:
   - edges[3][12] contains the information about the edge going from squares[3] to squares[12].
   - squares[squirrels[3]] contains the location of the 4th squirrel.
 */
static struct square
{
  int x;
  int y;
} squares[MAX_WIDTH * MAX_WIDTH + 1];

/* all the edges that may figure in a path.  */
static struct edge
{
  int length;
  int penalty;
  float cost;     /* GLS augmented cost == length + penalty * LAMBDA */
  float util;     /* GLS penalty == length / (1.0 + penalty) */
  int dont_look;  /* don't look bit - used to speed up 2-opt */
} **edges;

/* A path through all the nuts for the solo potm.
   At any time, only 2 paths are needed: the best found so far and the
   one on which we are working. */
static struct path
{
  int nr_nuts;
  int length;
  int *nuts;      /* nuts[-1]       is the starting point
                     nuts[nr_nuts]  is the end of path marker */
} *best, *path;

/* used in the multi potm to sort the nuts and figure out a path */
static struct nut
{
  int id;
  int nr_closer;    /* nr of squirrels that can grab this nut before me */
  int nr_shares;    /* nr of squirrels that can grab this nut with me */
  int delta_d;      /* 'spare time'. When positive, it's the number of moves can be spent trying to grab
                       other nuts before this one. If negative, it tells how late I am */
  int s_dist;       /* sum of the distances from this nut to all the other squirrels */
  int n_dist;       /* sum of the distances from this nut to all the other nuts */
  struct nut *next; /* used to build a path */
} *nuts;

/******************************************************************************/

static struct path *  new_path      (void);
static void           free_path     (struct path *path);
static struct path *  copy_path     (struct path *dst, const struct path *src);
static void           display_path  (const struct path *p);
static struct path *  random_path   (struct path *p, int start);

static void improve_2opt            (void);
static void update_costs            (void);
static void search_single_squirrel  (void);

static int  sort_nuts               (const struct nut *n1, const struct nut *n2);
static void init_nuts               (void);
static void search_multi_squirrels  (void);

static void clean_exit    (void);
static int  dist          (const struct square *p1, const struct square *p2);
static void init_edges    (void);
static void read_datafile (const char *file);

static int  read_tempfile   (void);
static void write_tempfile  (void);

/******************************************************************************/

static struct path * new_path(void)
{
  struct path *p;

  p = malloc(sizeof(struct path));
  if(p != NULL)
  {
    p->nr_nuts = 0;
    p->length = 0;
    p->nuts = malloc((nr_nuts + 2) * sizeof(int));
    if(p->nuts != NULL)
    {
      p->nuts++;
      return p;
    }
  }

  printf("new_path: out of memory\n");
  exit(EXIT_FAILURE);
  return NULL;
}

/******************************************************************************/

static void free_path(struct path *p)
{
  if(p != NULL)
  {
    free(p->nuts - 1);
    free(p);
  }
}

/******************************************************************************/

static struct path * copy_path(struct path *dst, const struct path *src)
{
  if(dst == NULL)
    dst = new_path();

  dst->length = src->length;
  dst->nr_nuts = src->nr_nuts;
  memcpy(dst->nuts - 1, src->nuts - 1, (src->nr_nuts + 2) * sizeof(int));

  return dst;
}

/******************************************************************************/

static struct path * random_path(struct path *p, int start)
{
  int i, tmp, pick;
  int p1, p2;

  if(p == NULL)
    p = new_path();

  p->nr_nuts = nr_nuts;
  p->length = 0;

  p->nuts[-1] = start;
  p->nuts[nr_nuts] = nr_nuts;

  for(i = 0; i < nr_nuts; i++)
    p->nuts[i] = i;

  p2 = p->nuts[-1];
  for(i = 0; i < nr_nuts; ++i)
  {
    pick = i + (rand() / (1.0 + RAND_MAX)) * (nr_nuts - i);

    tmp = p->nuts[i];
    p->nuts[i] = p->nuts[pick];
    p->nuts[pick] = tmp;

    p1 = p2;
    p2 = p->nuts[i];
    p->length += edges[p1][p2].length;
  }

  return p;
}

/******************************************************************************/

static void display_path(const struct path *path)
{
  int i;
  int p1, p2;
  int l, tl;
  float c, tc;

  if(path == NULL)
    return;

  tc = 0.0;
  tl = 0;
  for(i = -1; i < path->nr_nuts; i++)
  {
    p1 = path->nuts[i];
    p2 = path->nuts[i + 1];

    tc += (c = edges[p1][p2].cost);
    tl += (l = edges[p1][p2].length);
    printf("%3d: %2d,%2d l: %2d tl: %3d c: %4.1f tc: %5.1f\n", i, squares[p1].x, squares[p1].y, l, tl, c, tc);
  }

  printf("nr_nuts: %d\n", path->nr_nuts);
  printf("length:  %d\n", path->length);
}

/******************************************************************************/

static void improve_2opt(void)
{
  int i, j;
  int start, end, tmp;
  int p1, p2, p3, p4;
  struct edge *e1, *e2, *e3, *e4;

  p2 = path->nuts[-1];
  for(i = 0; i <= path->nr_nuts; ++i)
  {
    p1 = p2;
    p2 = path->nuts[i];

    /* e1 == edges[path->nuts[i-1]][path->nuts[i]] */
    e1 = &edges[p1][p2];

    if(e1->dont_look)
      continue;

loop_again:

    p4 = path->nuts[-1];
    for(j = 0; j < i - 1; ++j)
    {
      p3 = p4;
      p4 = path->nuts[j];

      e2 = &edges[p3][p4];
      e3 = &edges[p3][p1];
      e4 = &edges[p4][p2];

      /* e2 == edges[path->nuts[j-1]][path->nuts[j]  ] */
      /* e3 == edges[path->nuts[j-1]][path->nuts[i-1]] */
      /* e4 == edges[path->nuts[j]  ][path->nuts[i]  ] */

      /* try to replace edges e1 and e2 by e3 and e4 */

      if(e1->cost + e2->cost > e3->cost + e4->cost)
      {
        path->length += e3->length + e4->length - e1->length - e2->length;

        edges[p1][p3].dont_look = e3->dont_look = 0;
        edges[p2][p4].dont_look = e4->dont_look = 0;

        /* reverse path between j and i - 1 */
        start = j;
        end = i - 1;
        do
        {
          tmp = path->nuts[start];
          path->nuts[start] = path->nuts[end];
          path->nuts[end] = tmp;
        } while(++start < --end);

        /* check e1 again */
        p1 = path->nuts[i - 1];
        e1 = &edges[p1][p2];
        goto loop_again;
      }
    }

    p4 = path->nuts[i + 1];
    for(j = i + 2; j <= path->nr_nuts; ++j)
    {
      p3 = p4;
      p4 = path->nuts[j];

      e2 = &edges[p3][p4];
      e3 = &edges[p1][p3];
      e4 = &edges[p2][p4];

      /* e2 == edges[path->nuts[j-1]][path->nuts[j]  ] */
      /* e3 == edges[path->nuts[i-1]][path->nuts[j-1]] */
      /* e4 == edges[path->nuts[i]  ][path->nuts[j]  ] */

      /* try to replace edges e1 and e2 by e3 and e4 */

      if(e1->cost + e2->cost > e3->cost + e4->cost)
      {
        path->length += e3->length + e4->length - e1->length - e2->length;

        edges[p3][p1].dont_look = e3->dont_look = 0;
        edges[p4][p2].dont_look = e4->dont_look = 0;

        /* reverse path between i and j - 1 */
        start = i;
        end = j - 1;
        do
        {
          tmp = path->nuts[start];
          path->nuts[start] = path->nuts[end];
          path->nuts[end] = tmp;
        } while(++start < --end);

        /* check e1 again */
        p2 = path->nuts[i];
        e1 = &edges[p1][p2];
        goto loop_again;
      }
    }

    /* no more improvement with e1, set its dont_look bit */
    edges[p2][p1].dont_look = e1->dont_look = 1;
  }
}

/******************************************************************************/

static void update_costs(void)
{
  int nr_max;
  struct square max[MAX_NUTS];

  int i, p1, p2;
  struct edge *e, *max_e;

  p1 = path->nuts[-1];
  p2 = path->nuts[0];
  max_e = &edges[p1][p2];

  nr_max = 1;
  max[0].x = p1;
  max[0].y = p2;

  /* search the current path for the edges with maximum utility... */
  for(i = 0; i < path->nr_nuts; ++i)
  {
    p1 = p2;
    p2 = path->nuts[i];

    e = &edges[p1][p2];

    if(e->util < max_e->util)
      continue;

    if(e->util > max_e->util)
    {
      nr_max = 1;
      max[0].x = p1;
      max[0].y = p2;
      max_e = e;
    }
    else
    {
      max[nr_max].x = p1;
      max[nr_max].y = p2;
      ++nr_max;
    }
  }

  /* ... and increase their penalty */
  for(i = 0; i < nr_max; ++i)
  {
    p1 = max[i].x;
    p2 = max[i].y;

    e = &edges[p1][p2];

    e->util = e->length / (1.0 + ++e->penalty);
    e->cost += LAMBDA;
    e->dont_look = 0;

    memcpy(&edges[p2][p1], e, sizeof(struct edge));
  }
}

/******************************************************************************/

static void search_single_squirrel(void)
{
  int loop;
  int max_loop;

  /* start with a random path */
  path = random_path(path, me);
  best = copy_path(best, path);

  /* run GLS for a fixed number of iterations */
  max_loop = MAX_LOOPS;
  for(loop = 0; loop < max_loop; ++loop)
  {
    improve_2opt();

    if(path->length < best->length)
      copy_path(best, path);

    update_costs();
  }

  /* Write the moves to the tempfile. This grid will not be searched again. */
  write_tempfile();
}

/******************************************************************************/

static int sort_nuts(const struct nut *n1, const struct nut *n2)
{
  int result;

  result = n1->nr_closer - n2->nr_closer;
  if(result == 0)
  {
    result = n1->nr_shares - n2->nr_shares;
    if(result == 0)
    {
      result = n2->delta_d - n1->delta_d;
      if(result == 0)
      {
        result = n2->s_dist - n1->s_dist;
        if(result == 0)
          result = n1->n_dist - n2->n_dist;
      }
    }
  }

  return result;
}

/******************************************************************************/

static void init_nuts(void)
{
  int i, j;
  int d, my_d, delta_d;
  int s;

  nuts = calloc(nr_nuts, sizeof(struct nut));
  if(nuts == NULL)
  {
    printf("init_nuts: out of memory\n");
    exit(EXIT_FAILURE);
  }

  for(i = 0; i < nr_nuts; ++i)
  {
    nuts[i].id = i;
    nuts[i].delta_d = INT_MAX;
    nuts[i].nr_shares = 1;

    my_d = edges[me][i].length;

    for(j = 1; j < nr_squirrels; ++j)
    {
      s = squirrels[j];
      d = edges[s][i].length;

      nuts[i].s_dist += d;

      delta_d = d - my_d;
      if(delta_d < nuts[i].delta_d)
        nuts[i].delta_d = delta_d;

      if(delta_d < 0)
        ++nuts[i].nr_closer;
      else if(delta_d == 0)
        ++nuts[i].nr_shares;
    }

    for(j = 0; j < i; j++)
      nuts[i].n_dist += edges[i][j].length;
    for(j = i+1; j < nr_nuts; j++)
      nuts[i].n_dist += edges[i][j].length;
  }

  qsort(nuts, nr_nuts, sizeof(struct nut), (qsortf)(sort_nuts));

#if 0
  {
    int i;
    printf("\n");
    for(i = 0; i < nr_nuts; i++)
    {
      printf("(%2d,%2d) nr_closer %d, nr_shares %2d, delta_d %2d, s_dist %3d, n_dist %3d\n",
        squares[nuts[i].id].x, squares[nuts[i].id].y, nuts[i].nr_closer, nuts[i].nr_shares,
        nuts[i].delta_d, nuts[i].s_dist, nuts[i].n_dist);
    }
    fgetc(stdin);
  }
#endif
}

/******************************************************************************/

static void search_multi_squirrels(void)
{
  int i, n;
  int extra_squirrels;

  int inc_d, delta_d;

  struct nut *path, *walk;
  float score;
  float new_score;

  int x1, y1, x2, y2, dx, dy;

  init_nuts();

  for(i = 1; i < nr_nuts; i++)
  {
    if(nuts[i].nr_closer != nuts[0].nr_closer ||
       nuts[i].nr_shares != nuts[0].nr_shares ||
       nuts[i].delta_d != nuts[0].delta_d ||
       nuts[i].s_dist != nuts[0].s_dist)
      break;
  }

  /* avoid nuts at the top of the list */
  i = i * 3/4;

  /* move towards nuts[i] */
  path    = nuts + i;
  delta_d = nuts[i].delta_d;

  if(nuts[i].nr_closer == 0)
    score = 1.0 / nuts[i].nr_shares;
  else
    score = 0.0;

  for(i = 0; i < nr_nuts; i++)
  {
    if(nuts + i == path)
      continue;

    n = nuts[i].id;
    inc_d = edges[me][n].length + edges[n][path->id].length - edges[me][path->id].length;

    if(inc_d > delta_d)
      continue;

    if(inc_d <= delta_d)
    {
      /* I can grab nuts[i] for free */
      delta_d -= inc_d;

      if(nuts[i].nr_closer == 0)
        score += 1.0 / nuts[i].nr_shares;

      nuts[i].next = path;
      path = &nuts[i];
    }
    else
    {
      /* I can grab nuts[i] but I have to share it */
      if(nuts[i].nr_closer > 0)
        continue;

      new_score = 1.0 / nuts[i].nr_shares;
      extra_squirrels = nuts[i].nr_shares - 1;

      for(walk = path; walk != NULL; walk = walk->next)
      {
        if(walk->nr_closer == 0)
          new_score += 1.0 / (walk->nr_shares + extra_squirrels);
      }

      if(new_score > score)
      {
        score = new_score;
        delta_d = 0;

        nuts[i].next = path;
        path = &nuts[i];
      }
    }
  }

  x1 = squares[me].x;
  y1 = squares[me].y;

  x2 = squares[path->id].x;
  y2 = squares[path->id].y;

  dx = x1 < x2 ? 1 : x2 < x1 ? -1 : 0;
  dy = y1 < y2 ? 1 : y2 < y1 ? -1 : 0;

  printf("%d,%d\n", x1 + dx, y1 + dy);
}

/******************************************************************************/

static void clean_exit(void)
{
  if(edges != NULL)
  {
    free(edges[0]);
    free(edges);
  }

  free_path(path);
  free_path(best);

  free(nuts);
}

/******************************************************************************/

static int dist(const struct square *p1, const struct square *p2)
{
  int dx = abs(p1->x - p2->x);
  int dy = abs(p1->y - p2->y);

  return dx >= dy ? dx : dy;
}

/******************************************************************************/

static void init_edges(void)
{
  struct edge *e1, *e2;
  int length;
  int i, j;

  edges = malloc(nr_squares * sizeof(struct edge *));
  if(edges == NULL)
  {
    printf("init_edges: out of memory\n");
    exit(EXIT_FAILURE);
  }

  edges[0] = malloc(nr_squares * nr_squares * sizeof(struct edge));
  if(edges[0] == NULL)
  {
    printf("init_edges: out of memory\n");
    exit(EXIT_FAILURE);
  }

  for(i = 1; i < nr_squares; ++i)
    edges[i] = edges[i - 1] + nr_squares;

  for(i = 0; i < nr_nuts; ++i)
  {
    e1 = edges[i];
    e2 = edges[0] + i;

    for(j = 0; j < i; ++j)
    {
      length = dist(squares + i, squares + j);

      e1->penalty = e1->dont_look = 0;
      e1->length = length;
      e1->cost = e1->util = length;

      memcpy(e2, e1, sizeof(struct edge));

      ++e1;
      e2 += nr_squares;
    }
    memset(&edges[i][nr_nuts], 0, sizeof(struct edge));
  }

  for(i = nr_nuts + 1; i < nr_squares; ++i)
  {
    e1 = edges[i];

    for(j = 0; j < nr_nuts; ++j)
    {
      length = dist(squares + i, squares + j);

      e1->penalty = e1->dont_look = 0;
      e1->length = length;
      e1->cost = e1->util = length;

      ++e1;
    }
    memset(e1, 0, sizeof(struct edge));
  }
}

/******************************************************************************/

static void read_datafile(const char *file)
{
  register int i, tmp;
  register FILE *fd;
  int x, y;

  fd = fopen(file, "r");
  if(fd == NULL)
  {
    printf("read_datafile: failed to open file \"%s\"\n", file);
    exit(EXIT_FAILURE);
  }

  if(fscanf(fd, "SIZE=%d,%d\n", &width, &height) != 2)
  {
    fclose(fd);
    printf("read_datafile: failed to read grid size\n");
    exit(EXIT_FAILURE);
  }

  ++width;
  ++height;

  while(fscanf(fd, "NUT=%d,%d\n", &squares[nr_nuts].x, &squares[nr_nuts].y) == 2)
    ++nr_nuts;

  if(nr_nuts == 0)
  {
    fclose(fd);
    printf("read_datafile: failed to read nuts position\n");
    exit(EXIT_FAILURE);
  }

  squares[nr_nuts].x = squares[nr_nuts].y = -1;
  nr_squares = nr_nuts + 1;

  while(fscanf(fd, "SQUIRREL=%d,%d\n", &x, &y) == 2)
  {
    for(i = 0; i < nr_squirrels; ++i)
      if(squares[squirrels[i]].x == x && squares[squirrels[i]].y == y)
        break;

    if(i == nr_squirrels)
    {
      squirrels[nr_squirrels] = nr_squares;

      squares[nr_squares].x = x;
      squares[nr_squares].y = y;

      ++nr_squares;
    }
    else
      squirrels[nr_squirrels] = squirrels[i];

    ++nr_squirrels;
  }

  if(nr_squirrels == 0)
  {
    fclose(fd);
    printf("read_datafile: failed to read nuts position\n");
    exit(EXIT_FAILURE);
  }

  if(fscanf(fd, "YOU=%d,%d\n", &x, &y) != 2)
  {
    fclose(fd);
    printf("read_datafile: failed to read my position\n");
    exit(EXIT_FAILURE);
  }

  for(i = 0; i < nr_squirrels; ++i)
    if(squares[squirrels[i]].x == x && squares[squirrels[i]].y == y)
    {
      tmp = squirrels[i];
      squirrels[i] = squirrels[0];
      squirrels[0] = tmp;
      break;
    }

  if(i == nr_squirrels)
  {
    fclose(fd);
    printf("read_datafile: my position does not match any squirrel\n");
    exit(EXIT_FAILURE);
  }

  me = squirrels[0];

  fclose(fd);
}

/******************************************************************************/

static int read_tempfile(void)
{
  FILE *fd;
  struct square move;
  int offset;

  fd = fopen(TEMP_FILE, "r+b");
  if(fd == NULL)
    return 0;

  if(fread(&offset, sizeof(int), 1, fd) != 1 ||
     fseek(fd, offset, SEEK_CUR) ||
     fread(&move, sizeof(struct square), 1, fd) != 1)
  {
    fclose(fd);
    return 0;
  }

  offset += sizeof(struct square);
  if(fseek(fd, 0, SEEK_SET) ||
     fwrite(&offset, sizeof(int), 1, fd) != 1)
  {
    fclose(fd);
    return 0;
  }

  fclose(fd);

  printf("%d,%d\n", move.x, move.y);
  return 1;
}

/******************************************************************************/

static void write_tempfile(void)
{
  FILE *fd;
  int i, n;
  int p1, p2;
  int x1, y1, x2, y2;
  int dx, dy;

  struct square moves[MAX_WIDTH * MAX_WIDTH];
  int offset;

  i = 0;

  p2 = best->nuts[-1];
  for(n = 0; n < best->nr_nuts; ++n)
  {
    p1 = p2;
    p2 = best->nuts[n];

    x1 = squares[p1].x;
    y1 = squares[p1].y;

    x2 = squares[p2].x;
    y2 = squares[p2].y;

    dx = x1 < x2 ? 1 : x2 < x1 ? -1 : 0;
    dy = y1 < y2 ? 1 : y2 < y1 ? -1 : 0;

    while(x1 != x2 && y1 != y2)
    {
      moves[i].x = (x1 += dx);
      moves[i++].y = (y1 += dy);
    }

    if(x1 == x2)
      while(y1 != y2)
      {
        moves[i].x = x1;
        moves[i++].y = (y1 += dy);
      }
    else if(y1 == y2)
      while(x1 != x2)
      {
        moves[i].x = (x1 += dx);
        moves[i++].y = y1;
      }
  }

  fd = fopen(TEMP_FILE, "wb");
  if(fd == NULL)
    return;

  offset = 0;
  fwrite(&offset, sizeof(int), 1, fd);

  fwrite(moves + 1, sizeof(struct square), best->length - 1, fd);
  fclose(fd);

  printf("%d,%d\n", moves[0].x, moves[0].y);
}

/******************************************************************************/

int main(int argc, char *argv[])
{
  if(read_tempfile())
    return EXIT_SUCCESS;

  if(argc < 2)
  {
    printf("main: missing datafile\n");
    return EXIT_FAILURE;
  }

  atexit(clean_exit);
  srand(time(NULL));

  read_datafile(argv[1]);
  init_edges();

  if(nr_squirrels == 1)
    search_single_squirrel();
  else
    search_multi_squirrels();

#if 0
  {
    display_path(best);
    fgetc(stdin);
  }
#endif

  return EXIT_SUCCESS;
}

/******************************************************************************/