/* BASIC ASSUMTIONS:
	- we are called with exactly *one* parameter: the input file to process.
	- our input file contains patterns created by gencols / makematrix
	- the collions contain exactly *one* object of the collection contained in this file
	- the collions should produce one or more end products from this collection.
	- the input file is rewindable / seekable (i.e.: a normal file)
	- each object is only recognized in one phase!

   Our goal is to summarise all the collions in the input file:
   For example:
	- start with a NE glider at (x, y)
	- after G generation we get an NW glider moved by (dx, dy) from the position of the
	  input glider.
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

// We could easily write a version using malloc an strdup and stuff.
// But probably we'd just be wasting time by for memorymanagment that could better be invested elsewhere.
#define WIDTH  128
#define HEIGHT 128
#define GENS   128	// # of Generations we will look at

#define MAX_RLE	500

#define O_WIDTH 10
#define O_HEIGHT 10

#define DEAD	'.'
#define ALIVE	'*'

// Basic objects we will looking for in our patterns
typedef struct
  {
    char *name;				// Name (abbrv.) of object
    int ySize, xSize; 			// Size of object: note *including* empty cells around the object itself.
    int sy, sx;				// coords of first ALIVE cell in object
    int dt, dy, dx;			// speed an direction of object (dt = 0 -> still life)
    char pat [O_HEIGHT][O_WIDTH];	// '.' -> must be DEAD, '*' -> must be ALIVE, ' ' don't care either way.
  } object;
#define MAX_DT	4			// set to max of objs [i].dt !!

object objs [] =
  {
    {
	"gl_ne", 5, 5, 1, 3, 4, -1, 1,
	{
	  " ....",
	  "..**.",
	  ".*.*.",
	  "...*.",
	  "  ..."
	}
    },
    {
	"gl_nw", 5, 5, 1, 1, 4, -1, -1,
	{
	  ".... ",
	  ".**..",
	  ".*.*.",
	  ".*...",
	  "...  "
	}
    },
    {
	"gl_se", 5, 5, 3, 3, 4, 1, 1,
	{
	  "  ...",
	  "...*.",
	  ".*.*.",
	  "..**.",
	  " ...."
	}
    },
    {
	"gl_sw", 5, 5, 3, 1, 4, 1, -1,
	{
	  "...  ",
	  ".*...",
	  ".*.*.",
	  ".**..",
	  ".... "
	}
    },
    {
	"block", 4, 4, 1, 1, 1, 0, 0,
	{
	  "....",
	  ".**.",
	  ".**.",
	  "...."
	}
    },
    {
	"blinker", 3, 5, 1, 1, 2, 0, 0,
	{
	  ".....",
	  ".***.",
	  "....."
	}
    },
    {
	"tub", 5, 5, 1, 2, 1, 0, 0,
	{
	  " ... ",
	  "..*..",
	  ".*.*.",
	  "..*..",
	  " ... "
	}
    },
    {
	"boat_nw", 5, 5, 1, 1, 1, 0, 0,
	{
	  ".... ",
	  ".**..",
	  ".*.*.",
	  "..*..",
	  " ... "
	}
    },
    {
	"boat_ne", 5, 5, 1, 3, 1, 0, 0,
	{
	  " ....",
	  "..**.",
	  ".*.*.",
	  "..*..",
	  " ... "
	}
    },
    {
	"boat_sw", 5, 5, 3, 1, 1, 0, 0,
	{
	  " ... ",
	  "..*..",
	  ".*.*.",
	  ".**..",
	  ".... "
	}
    },
    {
	"boat_se", 5, 5, 3, 3, 1, 0, 0,
	{
	  " ... ",
	  "..*..",
	  ".*.*.",
	  "..**.",
	  " ...."
	}
    },
    {
	"hive_we", 5, 6, 2, 1, 1, 0, 0,
	{
	  " .... ",
	  "..**..",
	  ".*..*.",
	  "..**..",
	  " .... "
	}
    },
    {
	"hive_ns", 6, 5, 1, 2, 1, 0, 0,
	{
	  " ... ",
	  "..*..",
	  ".*.*.",
	  ".*.*.",
	  "..*..",
	  " ... "
	}
    },
    {
	"loaf1", 6, 6, 1, 2, 1, 0, 0,
	{
	  " .... ",
	  "..**..",
	  ".*..*.",
	  ".*.*..",
	  "..*...",
	  " ...  "
	}
    },
    {
	"loaf2", 6, 6, 1, 2, 1, 0, 0,
	{
	  " ...  ",
	  "..*...",
	  ".*.*..",
	  ".*..*.",
	  "..**..",
	  " .... "
	}
    },
    {
	"loaf3", 6, 6, 1, 2, 1, 0, 0,
	{
	  " .... ",
	  "..**..",
	  ".*..*.",
	  "..*.*.",
	  "...*..",
	  "  ... "
	}
    },
    {
	"loaf4", 6, 6, 1, 3, 1, 0, 0,
	{
	  "  ... ",
	  "...*..",
	  "..*.*.",
	  ".*..*.",
	  "..**..",
	  " .... "
	}
    },
    {
	"EOL", 0, 0, 0, 0
    }
  };

char pattern [GENS][HEIGHT] [WIDTH];	// Note: it's not an array of c-type strings, its a 2-dim array of char.
					// No trailing \0
int top [GENS], bottom [GENS], left [GENS], right [GENS];	// bounding box of each generation

void clear_pattern (void)

{
  int g;

  memset (pattern, DEAD, GENS*HEIGHT*WIDTH);

  for (g = 0; g < GENS; g++)
    {
      top [g]    = HEIGHT;
      bottom [g] = -1;
      left [g]   = WIDTH;
      right [g]  = -1;
    }
}


wp (int g, int t, int b, int l, int r)
{
  int x, y;

  for (y = t; y <= b; y++)
    {
      for (x = l; x <= r; x++)
	 putc (pattern [g][y][x], stdout);
      putc ('\n', stdout);
    }
  putc ('\n', stdout);
}


void shrink_box (int g)
// Shrink bounding box of pattern in generation g.
// prerequisite: The box is assumed to be smaller then (top [g], left [g], bottom [g], right [g])
// result: (top [g], left [g], bottom [g], right [g]) contain the actual bounding box (might be empty!)

{
  int x, y;

  int  ymin = top [g], ymax = bottom [g];
  int  xmin = left [g], xmax = right [g];

  // classical min/max search.
  top [g] = HEIGHT-1; bottom [g] = 0;
  left [g] = WIDTH-1; right [g] = 0;
  for (y = ymin; y <= ymax; y++)
    for (x = xmin; x <= xmax; x++)
      if (pattern [g][y][x] == ALIVE)
	{
	  if (top [g] > y) top [g] = y;
	  if (bottom [g] < y) bottom [g] = y;
	  if (left [g] > x) left [g] = x;
	  if (right [g] < x) right [g] = x;
	}
}


object *search (int g, int *x, int *y, int min_dt)
// Try to find any of our objects in a given generation of our pattern.
// First matching object is returned.
// Coordinates of first "alive" cell are returned in *x and *y

{
  object *obj;

  for (obj = objs; obj->xSize > 0; obj++)
    {
      // Some of our objects have more then one phase. Since we only search for one of theese phases, the result-search
      // has to be repeated for up to MAX_DT generations.
      // On the other: we only have to look at each phase once ...
      if (obj->dt < min_dt)
	continue;

      // Take the following into account:
      //	- both pattern and obj->pat are surronded by a frame of non-ALIVE cells.
      //	- Checking for objects outside of the pattern is pointless and even dangerous (segfault anyone?)
      int t, b, l, r;
      t = top [g] + (obj->sy-1);
      l = left [g] + (obj->sx-1);
      b = bottom [g] - (obj->ySize - 2 - obj->sy);
      r = right [g] - (obj->xSize - 2 - obj->sx);
      for (*y = t; *y <= b; (*y)++)
	for (*x = l; *x <= r; (*x)++)
	  if (pattern [g][*y][*x] == ALIVE)
	    {
	      int dx, dy, OK = 1;
	      for (dy = 0; OK && dy < obj->ySize; dy++)
		for (dx = 0; OK && dx < obj->xSize; dx++)
		  if (obj->pat [dy][dx] != ' ' && obj->pat [dy][dx] != pattern [g][*y-obj->sy+dy][*x-obj->sx+dx])
		    OK = 0;
	      if (OK)
		return obj;
	    }
    }

  // We didn't find nothing ... oh, well ...
  return NULL;
}


int match_at (object *o, int g, int y, int x)
// At some generation g' we did find *o in our pattern at (x', y').
// Try to find out whether we can find it in generation g - for a spaceship (x,y) have been adjusted according to the speed of the object.

{
  int dx, dy, OK = 1;

  // Don't run off screen
/*
  if (y - o->sy < top || y - o->sy + o->ySize >= HEIGHT)
    return 0;
  if (x - o->sx < left || x - o->sx + o->xSize >= WIDTH)
    return 0;
*/

  for (dy = 0; OK && dy < o->ySize; dy++)
    for (dx = 0; OK && dx < o->xSize; dx++)
      if (o->pat [dy][dx] != ' ' && o->pat [dy][dx] != pattern [g][y-o->sy+dy][x-o->sx+dx])
	OK = 0;
  return OK;
}


int remove_at (object *o, int g, int y, int x)
// pattern [g] contains *o at location (x,y)
// replace it by dead cells

{
  int dx, dy;

  // Don't run off screen
  for (dy = 0; dy < o->ySize; dy++)
    for (dx = 0; dx < o->xSize; dx++)
      if (o->pat [dy][dx] != ' ')
	pattern [g][y-o->sy+dy][x-o->sx+dx] = DEAD;

  // bounding box might shrink.
  shrink_box (g);
}


int generate (int g)
// stupid, straight forward version
// Calculate generation g from g-1
// returns 0 if resulting pattern is empty.

{
  int x, y;
  int  neighbors [HEIGHT] [WIDTH];

  // We can not grow our bounding box faster then one cell per turn ...
  // And we have to stay off the border!
  top [g]    = (top [g-1] > 1)           ? top [g-1]-1    : 1;
  bottom [g] = (bottom [g-1] < HEIGHT-2) ? bottom [g-1]+1 : HEIGHT-2;
  left [g]   = (left [g-1] > 1)          ? left [g-1]-1   : 1;
  right [g]  = (right [g-1] < WIDTH-2)   ? right [g-1]+1  : WIDTH-2;

  for (y = top [g]; y <= bottom [g];  y++)
    for (x = left [g]; x <= right [g];  x++)
      {
	neighbors [y][x] = (pattern [g-1][y-1][x-1] == ALIVE) + (pattern [g-1][y-1][x  ] == ALIVE) + (pattern [g-1][y-1][x+1] == ALIVE) +
			   (pattern [g-1][y  ][x-1] == ALIVE) +					     (pattern [g-1][y  ][x+1] == ALIVE) +
			   (pattern [g-1][y+1][x-1] == ALIVE) + (pattern [g-1][y+1][x  ] == ALIVE) + (pattern [g-1][y+1][x+1] == ALIVE);
      }

  for (y = top [g]; y <= bottom [g];  y++)
    for (x = left [g]; x <= right [g];  x++)
       pattern  [g][y][x] = ((neighbors [y][x] == 3) || (neighbors [y][x] == 2 && pattern  [g-1][y][x] == ALIVE)) ? ALIVE : DEAD;

  // update bounding box
  shrink_box (g);

  // "Todos muertos"?
  return (top [g] <= bottom [g]);
}


void write_pattern (int g)

{
  int x, y;

  for (y = top [g]; y <= bottom [g]; y++)
    {
      for (x = left [g]; x <= right [g]; x++)
	 putc (pattern [g][y][x], stdout);
      putc ('\n', stdout);
    }
  putc ('\n', stdout);
}


void rle_append (char *tgt, int size, int *pos, int nr, char c)
// Helper fun for rle_encode ():
// Append c (optinally preceeded by a number nr) to tgt starting at pos.
// Make sure we do not exceed the given size!

{
  if (nr <= 0)
    return;

  // Check if we will probably fit ...
  // NOTE: maybe we won't fit if nr is way larger then 10 ... but since we're using snprintf in this case, at least we won't crash
  if (*pos >= size || (nr > 1 && *pos >= size-1))
    {
      fprintf (stderr, "RLE too large - fix program\n");
      exit (2);
    }

  // do we have to output nr?
  if (nr > 1)
    {
      snprintf (tgt+*pos, size-*pos, "%d%c", nr, c);
      *pos += strlen (tgt+*pos);
    }
  else
    {
      // Just write out the char
      tgt [(*pos)++] = c;
    }
}


void rle_encode (int g, char *tgt, int size)
// rle encode generation g of our pattern into buf; we may not exceed the given size
// result: 0 terminated rle string - without the header!
/*
  Example: If we saved our object gl_ne in an .rle file it would look like:

x = 3, y = 3, rule = B3/S23
b2o$obo$2bo!

*/

{
  int x, y, run, pos = 0, nr_lf = 0;
  char current;

  for (y = top [g]; y <= bottom [g]; y++)
    {
      run = 0;
      current = DEAD;

      for (x = left [g]; x <= right [g]; x++)
	{
	  if (pattern [g][y][x] == current)
	    run++;
	  else
	    { 
	      if (nr_lf)
		{
		  rle_append (tgt, size, &pos, nr_lf, '$');
		  nr_lf = 0;
		}
	      rle_append (tgt, size, &pos, run, (current == ALIVE) ? 'o' : 'b');
	      current = pattern [g][y][x];
	      run = 1;
	    }
	}

      if (current == ALIVE)
	rle_append (tgt, size, &pos, run, 'o');
      nr_lf++;
    }

  rle_append (tgt, size, &pos, 1, '!');
  rle_append (tgt, size, &pos, 1, '\0');
}


void write_rle (int g)

{
  char rle [MAX_RLE];

  rle_encode (g, rle, MAX_RLE);
  printf ("x = %d, y = %d, rule = B3/S23\n%s\n\n", right [g] - left [g] + 1, bottom [g] - top [g] + 1, rle);
}


void load_life (FILE *in)

{
  char buffer [1024], *lf;

  int  len, height = 0, width = 0, Xoff, Yoff, i;
  fpos_t pos;

  // calculate size of pattern.
  fgetpos (in, &pos);
  while (!feof (in))
    {
      if (!fgets (buffer, 1024, in))
	break;

      lf = strrchr (buffer, '\n');
      if (lf)
	{
	  len = lf-buffer;
	  *lf = '\0';
	}
      else
	len = strlen (buffer);
      if (len > WIDTH)
	{
	  fprintf (stderr, "Line '%s' too long, rewrite program!\n", buffer);
	  exit (1);
	}
      if (len > width)
	width = len;

      // Three cases: buffer == "#...."	-> ignore for now
      //	      buffer == ""	-> end-of-pattern
      //	      else: current line is just another part of current pattern.
      // We will not too picky 'bout anything ... garbage in means garbage out!
      if (buffer [0] == '#')
	/* no op */;
      else if (!buffer [0])
	break;
      else if (height < HEIGHT)
	height++;
      else
	{
	  fprintf (stderr, "pattern too high, rewrite program!\n", buffer);
	  exit (1);
	}
    }
  fsetpos (in, &pos);

  // OK. height and width contain the size of our pattern.
  // Load it to the center of pattern [][]
  Yoff = (HEIGHT-height) / 2;
  Xoff = (WIDTH-width) / 2;
  top [0]    = Yoff;
  bottom [0] = Yoff+height-1;
  left [0]   = Xoff;
  right [0]  = Xoff+width-1;

  while (!feof (in))
    {
      if (!fgets (buffer, 1024, in))
	break;

      lf = strrchr (buffer, '\n');
      if (lf)
	{
	  len = lf-buffer;
	  *lf = '\0';
	}
      else
	len = strlen (buffer);

      // Three cases: buffer == "#...."	-> ignore for now
      //	      buffer == ""	-> end-of-pattern
      //	      else: current line is just another part of current pattern.
      // We will not too picky 'bout anything ... garbage in means garbage out!
      if (buffer [0] == '#')
	/* no op */;
      else if (!buffer [0])
	break;
      else
	{
	  for (i = 0; i < len; i++)
	    pattern [0][Yoff][Xoff+i] = buffer [i];
	  Yoff++;
	}
    }
}


main (int argc, char **argv)

{
  FILE *in = stdin;
  object *o1, *o2;
  int x1, y1, x2, y2;
  int g1, g2, nrRes;
  unsigned long nrPat = 0;
  int dies;
  char rle [MAX_RLE];

  if (argc == 2)
    {
      in = fopen (argv [1], "rt");
      if (!in)
        {
          perror (argv [1]);
          exit (1);
        }
    }

// TO DO: nicht nur das erste (temporäre Objekt finden, sondern auf die endgültige Stabilisierung erkennen.
  while (!feof (in))
    {
      // Load next pattern - skip if empty
      clear_pattern ();
      load_life (in);
      if (top [0] >= bottom [0] || left [0] >= right [0])
	continue;

      // Find start object (see comment at top of this source)
      // Skip pattern if nothing matched
      o1 = search (0, &x1, &y1, 0);
      if (!o1)
	{
	  rle_encode (0, rle, MAX_RLE);
	  printf ("-- I dont grok the starting pattern: %s\n", rle);
	  continue;
	}

      // let the pattern evolve and keep every generation
      dies = 0;
      for (g1 = 1; !dies && g1 < GENS; g1++)
	dies = !generate (g1);

      // Find out how long the starting object will survive
      // CAUTION: sometimes gencoll emits close fly-bys ...
      g1 = 0;
      do
	{
	  g1 += o1->dt;
	  y1 += o1->dy;
	  x1 += o1->dx;
	}
      while (g1 < GENS && match_at (o1, g1, y1, x1));
      if (g1 >= GENS)
	{
	  rle_encode (0, rle, MAX_RLE);
	  printf ("-- fly-by detected: %s\n", rle);
	  continue;
	}
      g1 -= o1->dt;
      y1 -= o1->dy;
      x1 -= o1->dx;

      // Describe where we come from
      // printf ("#P %lu %lu\n", (nrPat / 1000) * 1000, (nrPat % 1000) * 1000);
      nrPat++;
      rle_encode (g1, rle, MAX_RLE);
      printf ("insert into pattern values (NULL, '%s', %d, %d, '%s', %d, %d, NULL);\n", rle, right [g1] - left [g1] + 1, bottom [g1] - top [g1] + 1, o1->name, x1-left [g1], y1-top [g1]);

      // If pattern died of, we don't have to search for a result.
      if (dies)
	{
	  printf ("-- pattern dies off: %s\n", rle);
	  continue;
	}

      // Try to find a result pattern in the last few generations
      nrRes = 0;
      for (g2 = GENS-MAX_DT; g2 < GENS; )
	{
	  int g3, x3, y3;

	  o2 = search (g2, &x2, &y2, GENS-g2);
	  if (!o2)
	    {
	      g2++;
	      continue;
	    }

	  // We found something: try to trace it back to it's first appearance
	  g3 = g2;
	  y3 = y2;
	  x3 = x2;
	  do
	    {
	      g3 -= o2->dt;
	      y3 -= o2->dy;
	      x3 -= o2->dx;
	    }
	  while (g3 >= 0 && match_at (o2, g3, y3, x3));
	  g3 += o2->dt;
	  y3 += o2->dy;
	  x3 += o2->dx;

	  // Tell all about it!
	  printf ("insert into result select pId, %d, '%s', %d, %d, %d from pattern where rle = '%s';\n", ++nrRes, o2->name, g3-g1, x3-x1, y3-y1, rle);

	  // Remove current object so we can search some more.
	  remove_at (o2, g2, y2, x2);
	  if (top [g2] > bottom [g2])
	    g2++;	// no more obj's - at least in this gen.
	}

      if (!nrRes)
	printf ("-- no identifiable output found\n");
      printf ("update pattern set nrResults = %d where rle = '%s';\n", nrRes, rle);
    }
}