/* This program outputs a matrix whose determinant is the number
 * of domino tilings of the input region.  The matrix should be fed
 * to Maple.  This input format allows for computing the number of
 * matchings of any bipartite planar graph.
 *
 * The region should be given as a pattern of V's, A's, <'s, >'s, and X's.
 * All characters after a percent are ignored.  Currently, the input must 
 * fit in a rectangle with 500 rows and 200 columns.
 *
 * A useful command line format for this program is:
 *
 * vaxmaple < region | maple -q
 *
 * Greg Kuperberg, Jim Propp, and David Wilson
 */ 

#include <stdio.h>

#define WIDTH 202
#define LENGTH 502
#define FREE -1

char pict[LENGTH][WIDTH];
int p[LENGTH][WIDTH];
char gap[LENGTH][WIDTH];

main()
{
  int i,j,k;
  int rows,columns;
  
  for (i=0; i<LENGTH;i++) for(j=0;j<WIDTH;j++) pict[i][j] = ' ';
  
  for (i=1; i<LENGTH-1 && gets(&(pict[i][1])) != NULL; ++i);
  
  for (i=0;i<LENGTH;i++) {
    int pflag = 0;
    for(j=0;j<WIDTH;j++) {
      if(pict[i][j] == 0) pflag = 1;
      if(pict[i][j] == '%') pflag = 1;
      if(pflag) pict[i][j] = ' ';
    }
  }
  
  rows = columns = 0;
  for(i=0;i<LENGTH;i++) {
    int gaps=1;
    for(j=0;j<WIDTH;j++) {
      if (pict[i][j] == ' ') gaps *= -1;
      gap[i][j] = gaps;
      if((i+j)&1)
	p[i][j] = (pict[i][j] == ' '?FREE:columns++);
      else
	p[i][j] = (pict[i][j] == ' '?FREE:rows++);
    }
  }
  
  printf("with(linalg,det):\nx := -1:\n");
  printf("a := array([\n");
  
  for(i=1;i<LENGTH-1;i++) for(j= i&1;j<WIDTH-1;j+=2)
    if(p[i][j] != FREE) {
      printf("[");
      for(k=0;k<columns;k++) {
	char *entries = "x01";
	int entry=0;
	if (k == p[i+1][j] && pict[i][j] != 'V' && pict[i+1][j] != 'A')
	  entry = gap[i][j];
	if (k == p[i-1][j] && pict[i][j] != 'A' && pict[i-1][j] != 'V')
	  entry = gap[i-1][j];
	if (k == p[i][j+1] && pict[i][j] != '>' && pict[i][j+1] != '<')
	  entry = 1;
	if (k == p[i][j-1] && pict[i][j] != '<' && pict[i][j-1] != '>')
	  entry = -1;
	putchar(entries[entry+1]);
	if(k<columns-1) putchar(',');
      }
      if(p[i][j] < rows-1) printf("],\n");
    }
  printf("]]):\nabs(det(a));\nquit;\n");
}