#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <signal.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/mman.h>

/* "Mars Rescue" Challenge -- solution by Allen Noe.
 * Placed in the public domain, 2004.
 * Marked portions derived from:
 * http://www.frank-buss.de/marsrescue/index.html
 * http://www.frank-buss.de/marsrescue/mars.lisp.txt
 *
 * Original contest page at:
 * http://www.frank-buss.de/marsrescue/index.html
 *
 * The basic idea is that since there are relatively few possible 
 * combinations of x-position, y-position, x-velocity, y-velocity, and 
 * having reached the target point, we can create a large array holding 
 * the distance to the finish for each position and propagate the 
 * distance backward from the end. The same idea is used to solve chess 
 * endgames; it's basically breadth-first search.
 *
 * The original run took an hour or so to design and write, a few hours 
 * to test, and 500MB space and 6 hours time to run. I was trying only 
 * for the shortest path and didn't spend any time thinking about faster 
 * algorithms or optimization on fuel usage. After I saw that ties were 
 * being broken on fuel usage I wrote an additional depth-first searcher 
 * that could use the distance-to-goal tablebase for pruning. It took 
 * only a few seconds to run but its transposition table (another idea 
 * borrowed from chess engines) added another 500MB space requirement. 
 * Thankfully I have 1GB of physical RAM, so I didn't get significant 
 * swap thrashing. The program is all brute force and ignorance, but 
 * the ideas behind it are fairly simple and it gets the job done.
 *
 * Looking at other people's solutions it has become apparent that this 
 * algorithm is comparatively very slow and uses too much RAM. I can 
 * think of several ways it could run faster. I also wasn't able to 
 * adapt it to find the low-fuel solutions. Oh well, it was fun.
 *
 * Usage:
 * Compile mars.c and create two 515,970,000 byte files named mars.tb 
 * and mars-fuel.tb in the current directory. Run the executable with a 
 * command line argument of "wipe" to initialize the tablebases and 
 * compute the solution. After the TBs are initialized running mars 
 * without the wipe option will reuse the old data.
 *
 * The program may be terminated with SIGINT (Ctrl-C) or SIGTERM and it
 * should pick up where it left off, as long as the TBs aren't wiped.
 *
 * Example:
 * $ gcc -W -Wall -O2 -o mars mars.c
 * $ dd if=/dev/zero of=mars.tb bs=10000 count=51597
 * 51597+0 records in
 * 51597+0 records out
 * $ dd if=/dev/zero of=mars-fuel.tb bs=10000 count=51597
 * 51597+0 records in
 * 51597+0 records out
 * $ time ./mars wipe
 * Initializing...done.
 * Wiping tablebases...done.
 * Computing...........................................................
 * ....................................................................
 * ................done: 143 passes.
 * Synchronized.
 * Positions solved: 124112922 Remaining: 133872078
 * Solution: 6444422202022220200000222000222222000000222000022202200220
 * 00000000000011111131332222222202222202200000000000022222020222222222
 * 22220202004104446244440010116662202222222220002222220200000000000222
 * 22022222222323333333332222000000000000002222202000222200000222020220
 * 02200200022202222020
 * Searching for minimum fuel: 6444422202022220200000222000222222000000
 * 22202222200000000000000000000111110113332222202222222202000000000000
 * 22222020222222222202222022610004444660401000004622222222222200022222
 * 20200000000000222202222222222331313131302020000000000000022222222000
 * 00020002222222222022000000000000000000
 * Alternate solution: 644442220202222020000022200022222200000022202222
 * 20000000000000000000011111011333222220222222220200000000000022222020
 * 22222222220222202261000444466040100000462222222222220002222220200000
 * 00000022220222222222233131313130202000000000000002222222200000020002
 * 222222222202000000000000000000
 * 
 * real    372m29.655s
 * user    361m45.620s
 * sys     0m36.070s
 */

/* The map is hardcoded below. XSZ and YSZ are the size in pixels, not 
 * characters. ui16 may need to be redefined on different systems -- it 
 * should be an unsigned integer and 16 bits in size. Various other 
 * changes may be necessary with nonstandard compilers and operating systems.
 */

#define XSZ 750
#define YSZ 390
#define TBSIZE XSZ*YSZ*21*21*2*2

typedef unsigned short ui16;

char *map[] = {
"                                                                           ",
"                                                                           ",
"                                                                           ",
"                                                                           ",
"                                                                           ",
"                                                                           ",
" O                                #       #                                ",
"###             ##########      ###     ##################                 ",
"###    #############################   #######           ####              ",
"##################################### #######      __      #####        ###",
"##################################### #####   ____/~~\\____   ####      ####",
"##################################### #####  /~~~~~  ~~~~~~\\  ####      ###",
"##################################### #####  \\_____________/  #####       #",
"##################################### #####                    ####        ",
"##################################      ########        # ### ####        #",
"######         ####                        ######################        ##",
"#####       #####                                        ##   ###        ##",
"####          ####              #######                        ##         #",
"#####    +       ##########################                     ###        ",
"#############      ###############                   ######      ##        ",
"##############                               #########   ##                ",
"##############     #############################         ####              ",
"###############     #####################                #########         ",
"###############     ###################                   #########        ",
"###############     ##################          ##        ##               ",
"################             #######            ###                        ",
"################                                 ###                       ",
"################                             ###################           ",
"###################                    #########################           ",
"######################          ##############################             ",
"########################             #########################             ",
"##########################                   ##################          ##",
"                       ######                       ########             ##",
"Mars Rescue Mission    ########                                        ####",
"Challenge Map          ##########                                    ######",
"Design by Frank Buss   ##############                              ########",
"                       ###################                          #######",
"###########################################################                ",
"###############################################################            ",
""
};

/* Slop in stone, pickup and map to reduce boundary checking */

char stone[XSZ+10][YSZ+10];  /* This pixel is stone */
char pickup[XSZ+10][YSZ+10]; /* We can pick up the flag at this pixel */
ui16 *tb;                    /* Tablebase storing number of moves to end */
ui16 *tb_fuel;

/* Number of 1 bits */
const int popcnt[8] = { 0, 1, 1, 2, 1, 2, 2, 3 };

/* x in [0..XSZ-1], y in [0..YSZ-1], xv/yv in [-10..+10], f in [0,1] */
#define IDX(x,y,xv,yv,f) (((x*YSZ+y)*441+(xv+10)*21+(yv+10))*2+f)
#define TB(x,y,xv,yv,f) tb[IDX(x,y,xv,yv,f)]
#define TBF(x,y,xv,yv,f) tb_fuel[IDX(x,y,xv,yv,f)]

volatile int die = 0;

void sighandler(int sig) {

  /* Silliness to make gcc not warn about the unused argument. */
  if (sig > 0) {
    die = sig + 1;
  } else {
    die = -sig + 1;
  }
}

/* Converted from the English. */
static inline int collision(int x, int y) {

  if ((x < 0) || (x + 9 >= XSZ)) return 1;
  if ((y < 0) || (y + 9 >= YSZ)) return 1;

  if (stone[x][y] || stone[x + 9][y]
      || stone[x][y + 9] || stone[x + 9][y + 9]) {
    return 1;
  }

  return 0;
}

/* Converted from the CLisp and English. */
static inline void move(int *x, int *y, int *xv, int *yv, int *f, int fire) {

  if (fire & 1) *xv -= 2;
  if (fire & 2) *yv -= 2;
  if (fire & 4) *xv += 2;
  *yv += 1;

  if (*xv >  10) *xv =  10;
  if (*xv < -10) *xv = -10;
  if (*yv >  10) *yv =  10;
  if (*yv < -10) *yv = -10;

  while ((*xv || *yv) && collision(*x + *xv, *y + *yv)) {
    *xv /= 2;
    *yv /= 2;
  }

  *x += *xv;
  *y += *yv;

  if (!*f) {
    if (pickup[*x][*y]) {
      *f = 1;
    }
  }
}

/* Depth-first search for a solution under a fuel limit. */
int search(int *array, int arraysz, int fuelused, int fueltarg,
           int depth, int x, int y, int xv, int yv, int f) {
  int i, t, tf, nx, ny, nxv, nyv, nf, ret, fire, fuel;
  static int printed;
  const int map[6] = { 0, 1, 2, 3, 4, 6 };

  tf = TBF(x,y,xv,yv,f);
  if (tf != 0xFFFF) {
    if (tf <= fuelused) return -1;
  }

  t = TB(x,y,xv,yv,f);
  if (t > depth) return -1;

  if (fuelused > fueltarg) return -1;

  if (t == 0) {
    fuel = 0;
    for (x = 0; x < arraysz; x++) {
      fuel += popcnt[array[x]];
    }
    if (fuel <= fueltarg) {
      if (printed) printf("Alternate solution: ");

      for (x = 0; x < arraysz; x++) {
        printf("%d", array[x]);
      }
      printf("\n");

      printed = 1;
    }
    return 0;
  }

  if (depth == 0) return -1;
  if (die) return -1;

  for (i = 0; i < 6; i++) {
    fire = map[i];

    if ((xv == 0) && (yv == 0) && (fire == 0)) continue;

    nx = x; ny = y; nxv = xv; nyv = yv; nf = f;
    move(&nx, &ny, &nxv, &nyv, &nf, fire);

    array[arraysz - depth] = fire;
    ret = search(array, arraysz, fuelused + popcnt[fire], fueltarg,
                 depth - 1, nx, ny, nxv, nyv, nf);
  }

  tf = TBF(x,y,xv,yv,f);
  if (fuelused < tf) TBF(x,y,xv,yv,f) = fuelused;

  return -1;
}

/* Print out a solution from the tablebase. */
void solution(int x, int y, int xv, int yv, int f) {
  int nx, ny, nxv, nyv, nf, min, fire, minfire;
  int j, t;

  /* Test fire bits in this order to maybe squeeze a bit of fuel out */
  const int bitsort[8] = { 0, 1, 2, 4, 3, 5, 6, 7 };

  t = TB(x,y,xv,yv,f);
  if (t != 0xFFFF) {
    printf("Solution: ");
    fflush(stdout);

    while (TB(x,y,xv,yv,f) != 0) {
      minfire = -1;
      min = TB(x,y,xv,yv,f);

      for (j = 0; j < 8; j++) {
        fire = bitsort[j];

        nx = x; ny = y; nxv = xv; nyv = yv; nf = f;
        move(&nx, &ny, &nxv, &nyv, &nf, fire);

        t = TB(nx,ny,nxv,nyv,nf);

        if (t < min) {
          min = t;
          minfire = fire;
        }
      }

      /* Bug check. */
      if (minfire == -1) {
        printf("x broken idx %d (%d)\n\n",
               IDX(x,y,xv,yv,f), TB(x,y,xv,yv,f));

        for (fire = 0; fire < 8; fire++) {
          nx = x; ny = y; nxv = xv; nyv = yv; nf = f;
          move(&nx, &ny, &nxv, &nyv, &nf, fire);

          t = TB(nx,ny,nxv,nyv,nf);

          printf("%d => %d\n", fire, t);
        }

        break;
      }

      printf("%d", minfire);
      fflush(stdout);

      move(&x, &y, &xv, &yv, &f, minfire);
    }

    printf("\n");
  } else {
    printf("No solution known for (%d,%d,%d,%d,%d).\n",x,y,xv,yv,f);
  }
}

int main(int argc, char **argv) {
  int f, i, t, x, y, xv, yv, nf, nx, ny, fd, fd2, nxv, nyv, min, cnt, rem;
  int fire, flag, pass, startx, starty;
  int array[512];

  printf("Initializing...");
  fflush(stdout);

  signal(SIGINT, sighandler);
  signal(SIGTERM, sighandler);

  fd = open("mars.tb", O_RDWR);
  if (fd == -1) return 1;

  /* Shared so writing to the memory will update the file. */
  tb = mmap(0, TBSIZE, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
  if (tb == NULL) return 1;

  fd2 = open("mars-fuel.tb", O_RDWR);
  if (fd2 == -1) return 1;

  tb_fuel = mmap(0, TBSIZE, PROT_READ|PROT_WRITE, MAP_SHARED, fd2, 0);
  if (tb_fuel == NULL) return 1;

  printf("done.\n");

  if ((argc == 2) && !strcmp(argv[1], "wipe")) {
    printf("Wiping tablebases...");
    fflush(stdout);

    memset(tb, 0xFF, TBSIZE);
    memset(tb_fuel, 0xFF, TBSIZE);

    printf("done.\n");
  }

  startx = starty = -1;

  for (x = 0; x < XSZ+10; x++) {
    for (y = 0; y < YSZ+10; y++) {
      stone[x][y] = 1;
      pickup[x][y] = 0;
    }
  }

  /* Parse the map */
  for (x = 0; x < XSZ; x++) {
    for (y = 0; y < YSZ; y++) {
      if (map[y/10][x/10] == ' ') {
        stone[x][y] = 0;
      } else if (map[y/10][x/10] == 'O') {
        startx = (x/10)*10;
        starty = (y/10)*10;
        stone[x][y] = 0;
      } else if (map[y/10][x/10] == '+') {
        stone[x][y] = 0;
      } else {
        stone[x][y] = 1;
      }

      if ((map[y/10][x/10] == '+')
          || (map[(y+9)/10][x/10] == '+')
          || (map[y/10][(x+9)/10] == '+')
          || (map[(y+9)/10][(x+9)/10] == '+')) {
        pickup[x][y] = 1;
      }

      if ((map[y/10][x/10] == 'O')
          || (map[(y+9)/10][x/10] == 'O')
          || (map[y/10][(x+9)/10] == 'O')
          || (map[(y+9)/10][(x+9)/10] == 'O')) {
        for (xv = -10; xv <= 10; xv++) {
          for (yv = -10; yv <= 10; yv++) {
            TB(x,y,xv,yv,1) = 0;
          }
        }
      }
    }
  }

  if ((startx == -1) || (starty == -1)) {
    printf("Start point not found in map.\n");
    return 1;
  }

  t = TB(startx,starty,0,0,0);
  if (t != 0xFFFF) {
    printf("Solution to (%d,%d,0,0,0) already known in %d steps.\n",
           startx, starty, t);
  } else {
    printf("Computing");
    fflush(stdout);

    pass = 0;
    do {
      flag = 0;

      /* Main loop: iterate over all the possibilities. */
      for (x = 0; x < XSZ; x++) {
        for (y = 0; y < YSZ; y++) {
          for (xv = -10; xv <= 10; xv++) {
            for (yv = -10; yv <= 10; yv++) {
              for (f = 0; f < 2; f++) {
                i = IDX(x,y,xv,yv,f);
                min = TB(x, y, xv, yv, f);

                for (fire = 0; fire < 8; fire++) {
                  nx = x; ny = y; nxv = xv; nyv = yv; nf = f;
                  move(&nx, &ny, &nxv, &nyv, &nf, fire);

                  t = TB(nx,ny,nxv,nyv,nf);
                  t += 1;

                  if (t < min) {
                    min = t;
                  }
                }

                if ((min <= 0xFFFF) && (min < TB(x, y, xv, yv, f))) {
                  TB(x, y, xv, yv, f) = min;
                  flag = 1;
                }
              }
            }
          }
        }
      }

      pass++;
      printf(".");
      fflush(stdout);
    } while (flag && !die);

    printf("done: %d pass%s.\n", pass, pass == 1 ? "" : "es");

    msync(tb, TBSIZE, MS_SYNC);

    printf("Synchronized.\n");
  }

  printf("Positions solved: ");
  fflush(stdout);

  cnt = rem = 0;
  for (x = 0; x < XSZ; x++) {
    for (y = 0; y < YSZ; y++) {
      for (xv = -10; xv <= 10; xv++) {
        for (yv = -10; yv <= 10; yv++) {
          for (f = 0; f < 2; f++) {
            t = TB(x,y,xv,yv,f);

            if (t == 0xFFFF) {
              rem++;
            } else {
              cnt++;
            }
          }
        }
      }
    }
  }

  printf("%d Remaining: %d\n", cnt, rem);

  solution(startx, starty, 0, 0, 0);

  die = 0;

  printf("Searching for minimum fuel: ");
  fflush(stdout);

  search(array, 282, 0, 169, 282, startx, starty, 0, 0, 0);

  munmap(tb_fuel, TBSIZE);
  close(fd2);

  munmap(tb, TBSIZE);
  close(fd);

  return 0;
}