/* Last edited on 2009-02-10 10:03:08 by stolfi */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int compute_K(int COLS, int ROWS);
void print_piece(int TEX, int p, int r);
void print_output(int TEX, int i, int j, int p, int r);
void print_input(int TEX, int p, int r, int q, int s);
void print_all(int COLS, int ROWS, int **pid, int **rot, int TEX);
int main(int argc, char **argv);

int compute_K(int COLS, int ROWS)
{
  return ((COLS * (ROWS-1)) + (COLS/2)*((ROWS+1)/2) + ((COLS-1)/2)*(ROWS/2));
}

void print_piece(int TEX, int p, int r)
{
  int a = r % 4, b = (a+1)%4, c = (b+1)%4, d = (c+1)%4;
  printf("1pm      \\piece{%d}{%d}{%d}{%d}{%d}%%\n",p,a,b,c,d);
}

void print_output(int TEX, int i, int j, int p, int r)
{
  if(TEX) 
    { printf("1om      %4d & %4d & %4d:%d \\\\\n", i, j, p, r); }
  else
    { printf("0om %4d %4d  %4d:%d\n", i, j, p, r); }
}

void print_input(int TEX, int p, int r, int q, int s)
{
  if (p > q) { int t;  t = p; p = q; q = t;  t = r; r = s; s = t; }
  if (TEX)
    { printf("1im    %3d:%d & %3d:%d \\\\\n", p, r, q, s); }
  else
    { printf("0im %3d:%d  %3d:%d\n", p, r, q, s); }
}

void print_all(int COLS, int ROWS, int **pid, int **rot, int TEX)
{
  int i, j, np;
  
  int N = (ROWS * COLS);
  int K = compute_K(COLS, ROWS);

  /* Print desired output: */
  printf("output (unsorted):\n");
  if (TEX) { printf("%doa  \\begin{array}{rrr}\n", TEX); }
  for (i = 0; i < ROWS; i++)
    for (j = 0; j < COLS; j++)
      { print_output(TEX, i, j, pid[i][j],rot[i][j]); }
  if (TEX) { printf("%doy  \\end{array}\n", TEX); }

  if (TEX) { 
    /* Print puzzle picture: */
    printf("picture:\n");
    printf("1pa  \\vbox{%%\n");
    for (i = 0; i < ROWS; i++)
      { printf("1pm    \\hbox{%%\n");
        for (j = 0; j < COLS; j++)
          { print_piece(TEX, pid[i][j], rot[i][j]); }
        printf("1pm    }%%\n");
      }
    printf("1py  }\n");
  }
  
  /* Print input: */
  printf("input (unsorted):\n");
  np = 0;
  if (TEX) 
    { 
      printf("1ia  \\begin{array}{rr}\n");
      printf("1ib    %4d & %4d \\\\[5pt]\n", N, K);
    }
  else
    { printf("0ia %4d %4d\n", N, K); }
  for (i = 0; i < ROWS; i++)
    for (j = 0; j < COLS; j++)
      { int p, q, r, s;
        /* Vertical pair: */
        if (i > 0)
          { p = pid[i][j];   r = (rot[i][j] + 2) % 4;
            q = pid[i-1][j]; s = rot[i][j];
            print_input(TEX, p,r,q,s); np++;
          }
        /* Horizontal pair: */
        if ((j > 0) && ((i + j) % 2 == 1))
          { p = pid[i][j];   r = (rot[i][j] + 3) %4;
            q = pid[i][j-1]; s = (rot[i][j-1] + 1) % 4;
            print_input(TEX, p,r,q,s); np++;
          }
      }
  if (TEX) { printf("1iy  \\end{array}\n"); }
  if (np != K) { printf("%diz *** OOPS - K is wrong, should be %d ***\n", TEX, np); }
  fflush(stdout);
}

int main(int argc, char **argv)
{
  if (argc != 2) 
    { fprintf(stderr, "usage: %s {ROWS} {COLS}\n", argv[0]); assert(0); }
    
  int ROWS = atoi(argv[1]);
  int COLS = atoi(argv[2]);
  
  int N = (ROWS * COLS);

  int perm[N];
  
  int i, j, k;
  
  int *pid[ROWS]; for (i = 0; i < ROWS; i++) { pid[i] = malloc(COLS*sizeof(int)); }
  int *rot[ROWS]; for (i = 0; i < ROWS; i++) { rot[i] = malloc(COLS*sizeof(int)); }

  int ok;
  
  for (k = 0; k < N; k++)
    { int v = (7*k*k + 3) % N;
      do {
        ok = 1;
        for(i = 0; i < k; i++) 
          { if (v == perm[i]) { v = (v + 1) % N; ok = 0; }}
      } while(! ok);
      perm[k] = v;
    }
      
  /* Fill puzzle: */
  for (i = 0; i < ROWS; i++)
    for (j = 0; j < COLS; j++)
      { pid[i][j] = perm[i*COLS+j];
        rot[i][j] = ((i+1)*(j+3) % 4);
        if (pid[i][j] == 0) { rot[i][j] = 0; }
      }
      
  print_all(COLS, ROWS, pid, rot, 0);
  print_all(COLS, ROWS, pid, rot, 1);
  return 0;
}