/*
 * tile.c
 * File revision 0
 * Solve the three-tile problem.
 * (c) 2000 Jacob Lundberg, jacob@chaos2.org
 */


#include <sys/time.h>
#include <unistd.h>
#include <stdio.h>


/* Are we in profiling mode (timer output only)? */
#define  PROFILE                0


/* Compute integer 2^k for indexing. */
#define  pk(a)                  (1 << (a))
#define  stod(x, y, w)          ((x) + (y) * (w))


int _tile(int *board, int sx, int sy, int k, int x, int y);
int _out(int *board, int w);


int main(int argc, char **argv) {
/*
 * main()
 * Set up to solve a three-tile problem.
 */

   int k, x, y;
   int *blocks;
   struct timeval before, after;

   /* Get the parameters. */
   if(argc < 3) {
      printf("useage: tile k x y\n");
      printf("\tk : sides are length 2^k\n");
      printf("\tx : x location [0, 2^k - 1] of removed block\n");
      printf("\ty : y location [0, 2^k - 1] of removed block\n");
      return(-1);
   }
   k = atoi(argv[1]);
   x = atoi(argv[2]);
   y = atoi(argv[3]);

   /* Allocate the rather large array we need to compute with. */
   blocks = (int *)malloc(sizeof(int) * pk(k) * pk(k));
   if(blocks == NULL) {
      printf("Unable to allocate a large enough chunk of memory!\n");
      return(-1);
   }
   memset(blocks, 0, sizeof(int) * pk(k) * pk(k));

   /* Run the calculation. */
   gettimeofday(&before, NULL);
   _tile(blocks, 0, 0, k, x, y);
   gettimeofday(&after, NULL);
   blocks[stod(x, y, pk(k))] = -1;

   /* Print the results. */
   if(PROFILE)
      printf("Size %i tiled in %li microseconds.\n", k,
            1000000 * (after.tv_sec - before.tv_sec) + after.tv_usec - before.tv_usec);
   else
      _out(blocks, pk(k));

   free(blocks);
   return(0);

}


int _tile(int *board, int sx, int sy, int k, int x, int y) {
/*
 * _tile()
 * Iteratively tile the board.
 */

   /* Useful calculations. */
   int n = pk(k - 1);
   int w = pk(k);

   /* Static data. */
   static int sw = 0;
   static int gcount = 0;

   /* On the first run, sw will be set to mirror the parent w. */
   if(!sw) sw = w;

   if(k == 1) {
      /* Base case.  Fill the current tile out. */
      ++gcount;
      if(sx != x || sy != y)
         board[stod(sx, sy, sw)] = gcount;
      if(sx + 1 != x || sy != y)
         board[stod(sx + 1, sy, sw)] = gcount;
      if(sx != x || sy + 1 != y)
         board[stod(sx, sy + 1, sw)] = gcount;
      if(sx + 1 != x || sy + 1 != y)
         board[stod(sx + 1, sy + 1, sw)] = gcount;
   } else {
      /* Reduce the problem further. */
      /* our own tile */
      _tile(board, sx + n - 1, sy + n - 1, 1, x, y);
      /* top left */
      if(x >= sx + n || y >= sy + n)
         _tile(board, sx, sy, k - 1, sx + n - 1, sy + n - 1);
      else
         _tile(board, sx, sy, k - 1, x, y);
      /* top right */
      if(x < sx + n || y >= sy + n)
         _tile(board, sx + n, sy, k - 1, sx + n, sy + n - 1);
      else
         _tile(board, sx + n, sy, k - 1, x, y);
      /* bottom left */
      if(x >= sx + n || y < sy + n)
         _tile(board, sx, sy + n, k - 1, sx + n - 1, sy + n);
      else
         _tile(board, sx, sy + n, k - 1, x, y);
      /* bottom right */
      if(x < sx + n || y < sy + n)
         _tile(board, sx + n, sy + n, k - 1, sx + n, sy + n);
      else
         _tile(board, sx + n, sy + n, k - 1, x, y);
   }

   return(0);

}


int _out(int *board, int w) {
/*
 * _out()
 * Display the board in ascii.
 */

   int i, wd = w * w;

   for(i = 0; i < wd; ++i) {
      if(i && !(i % w))
         printf("\n");
      printf("%3i ", board[i]);
   }
   printf("\n");

   return(0);

}