/* This file is in the public domain. */

/*
 * Generate representatives and masks for W wells, H hands.  This takes
 *  W and H as command-line arguments and produces, on stdout, a file
 *  suitable for use as INC_FILE for solve.c.  Not well tested above
 *  W=7, though it is willing to try to run up through W=16.
 */

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

extern const char *__progname;

static int w;
static int h;

static unsigned int rotr(unsigned int v)
{
 return((v>>1)|((v&1)<<(w-1)));
}

static unsigned int popcount(unsigned int v)
{
 v = (v & 0x5555) + ((v >> 1) & 0x5555);
 v = (v & 0x3333) + ((v >> 2) & 0x3333);
 v = (v & 0x0f0f) + ((v >> 4) & 0x0f0f);
 v = (v & 0x00ff) + ((v >> 8) & 0x00ff);
 return(v);
}

static const char *type_for_width(int w)
{
 if (w <= 8) return("unsigned char");
 if (w <= 16) return("unsigned short int");
 if (w <= 32) return("unsigned int");
 if (w <= 64) return("unsigned long long int");
 abort();
}

int main(int, char **);
int main(int ac, char **av)
{
 int i;
 int j;
 unsigned int r;
 unsigned int m;
 int n;
 int npatt;
 int nhpat;
 int nrepr;
 int nmask;
 unsigned int *reprfor;
 unsigned char *reprinx;
 unsigned int *reprv;
 unsigned int *maskv;
 const char *masktype;
 unsigned char *maskbits;
 unsigned char *mbp;
 int k;

 if (ac != 3)
  { fprintf(stderr,"Usage: %s wells hands\n",__progname);
    exit(1);
  }
 w = atoi(av[1]);
 h = atoi(av[2]);
 if ((w < 2) || (w > 16))
  { fprintf(stderr,"%s: well count %d out of range 2..16\n",__progname,w);
    exit(1);
  }
 if ((h < 2) || (h > w-1))
  { fprintf(stderr,"%s: hand count %d out of range 2..%d\n",__progname,h,w-1);
    exit(1);
  }
 npatt = 1 << w;
 nhpat = 1 << h;
 masktype = type_for_width(w);
 reprfor = malloc(npatt*sizeof(unsigned int));
 reprinx = malloc(npatt);
 nrepr = 0;
 r = npatt;
 do
  { r --;
    m = 0;
    for (j=w;j>0;j--)
     { r = rotr(r);
       if (r > m) m = r;
     }
    reprfor[r] = m;
    if (r == m) nrepr ++;
  } while (r);
 if (nrepr > 64)
  { fprintf(stderr,"%s: too many representations\n",__progname);
    exit(1);
  }
 reprv = malloc(nrepr*sizeof(unsigned int));
 n = nrepr;
 for (i=npatt-1;i>=0;i--)
  { r = reprfor[i];
    if (r != i) continue;
    if (n < 1) abort();
    reprv[--n] = r;
  }
 if (n != 0) abort();
 for (i=npatt-1;i>=0;i--)
  { r = reprfor[i];
    do <"found">
     { for (j=nrepr-1;j>=0;j--) if (reprv[j] == r) break <"found">;
       abort();
     } while (0);
    reprinx[i] = j;
  }
 nmask = 0;
 for (i=nrepr-1;i>=0;i--)
  { r = reprv[i];
    if (popcount(r) != h) continue;
    nmask ++;
  }
 maskv = malloc(nmask*sizeof(unsigned int));
 n = nmask;
 for (i=nrepr-1;i>=0;i--)
  { r = reprv[i];
    if (popcount(r) != h) continue;
    if (n < 1) abort();
    maskv[--n] = r;
  }
 if (n != 0) abort();
 maskbits = malloc(h*nmask);
 for (i=nmask-1;i>=0;i--)
  { mbp = maskbits + (i * h);
    m = maskv[i];
    n = 0;
    for (j=0;j<h;j++)
     { if (! m) abort();
       while (! (m & 1))
	{ n ++;
	  m >>= 1;
	}
       mbp[j] = n;
       m --;
     }
    if (m) abort();
  }
 printf("unsigned char pops[%d] = {\n"/*}*/,npatt);
 for (i=0;i<npatt;i++) printf("%u,\n",popcount(i));
 printf(/*{*/"};\n");
 printf("%s reprv[%d] = {\n"/*}*/,masktype,nrepr);
 for (i=0;i<nrepr;i++) printf("%u,\n",reprv[i]);
 printf(/*{*/"};\n");
 printf("%s repr_for[%d] = {\n"/*}*/,masktype,npatt);
 for (i=0;i<npatt;i++) printf("%u,\n",reprfor[i]);
 printf(/*{*/"};\n");
 printf("unsigned char repr_inx[%d] = {\n"/*}*/,npatt);
 for (i=0;i<npatt;i++) printf("%u,\n",reprinx[i]);
 printf(/*{*/"};\n");
 printf("%s maskv[%d] = {\n"/*}*/,masktype,nmask);
 for (i=0;i<nmask;i++) printf("%u,\n",maskv[i]);
 printf(/*{*/"};\n");
 printf("%s toggles[%d][%d] = {\n"/*}*/,masktype,nmask,nhpat);
 for (i=0;i<nmask;i++)
  { printf("{"/*}*/);
    for (j=0;j<nhpat;j++)
     { m = 0;
       for (k=h-1;k>=0;k--)
	{ if ((j >> k) & 1) m |= 1 << maskbits[(i*h)+k];
	}
       printf("%u,\n",m);
     }
    printf(/*{*/"},");
  }
 printf(/*{*/"};\n");
 printf("#define NREPR %d\n",nrepr);
 printf("#define NMASK %d\n",nmask);
 printf("#define WELLS %d\n",w);
 printf("#define HANDS %d\n",h);
 printf("typedef %s REPRMASK;\n",type_for_width(nrepr));
 printf("typedef %s MASKTYPE;\n",masktype);
 return(0);
}