#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <limits.h>

#define HTFAIL LONG_MAX

/*#define DOHASHSTATISTICS 1*/

/* type for hash tables with value entries of type long */
typedef struct {
  long len;    /* allocated length = max. nr of entries + 1 */
  long nr;     /* number of entries */
  void **els;   /* the elements */
  long *vals;  /* corresponding values */
  long (*hfun)(void *, size_t);  /* the hash function (pointer to element and
				    length of data for element */
  int (*cmp)(void *, void *, size_t); /* compare function of two elements,
					 given by void pointers and length */
} HashType;


#ifdef DOHASHSTATISTICS
long long nraccesses = 0;
long long nrhits = 0;
long long nrsteps = 0;
#endif

HashType *vecs;

/* basic functions for hash tables */

/* initializes new hash table with and w/o space for values 
   input: length l, hash function f (f must give long values) and
   compare function for two elements (given by void pointers and
   their length */
HashType* NewHT( long len, long (*hfun)(void *, size_t), 
		 int (*cmp)(void *, void *, size_t))
{
  HashType * res;
  res = (HashType *)malloc(sizeof(HashType));
  res->len = len;
  res->nr = 0;
  res->els = (void **)calloc(len, sizeof(void *));
  res->vals = (long *)malloc(len * sizeof(long));
  res->hfun = hfun;
  res->cmp = cmp;
  return res;
}

HashType *NewHTNoVals( long len, long (*hfun)(void *, size_t),
		       int (*cmp)(void *, void *, size_t))
{
  HashType *res;
  res = (HashType *)malloc(sizeof(HashType));
  res->len = len;
  res->nr = 0;
  res->els = (void **)calloc(len, sizeof(void *));
  res->vals = NULL;
  res->hfun = hfun;
  res->cmp = cmp;
  return res;
}

/* get a value (always 1 for NoVals table) from hash table or 
`HTFAIL' if not known */
long ValueHT(HashType *ht, void *x, size_t len)
{
  long h;
  /* get hash value */
  h = (unsigned long)(ht->hfun(x, len)) % ht->len;
  for (;ht->els[h] != NULL && ht->cmp(x, ht->els[h], len) != 0; ){
    h++;
    if (h == ht->len) h = 0;
  }
  if (ht->els[h] == NULL){
    return HTFAIL;
  }
  else {
    if (ht->vals == NULL) {
      return 1L;
    }
    else {
      return ht->vals[h];
    }
  }
}

/* add an entry to a hash table */
/* exits the program if no slot available */
long AddHT(HashType *ht, void *x, size_t len, long val)
{
  long h;

#ifdef DOHASHSTATISTICS
  nraccesses++;
#endif

  if (ht->len == ht->nr + 1) /* return HTFAIL; */ {
    printf("Error: Hash table too small, only %ld entries allowed.\n", 
	   ht->len - 1);
    exit(2);
  }
  h = (unsigned long)(ht->hfun(x, len)) % ht->len;
  for (;ht->els[h] != NULL; ){

#ifdef DOHASHSTATISTICS
  nrsteps++;
#endif

    h++;
    if (h == ht->len) h = 0;
  }
  ht->els[h] = x;
  if (ht->vals != NULL)
    ht->vals[h] = val;
  ht->nr++;
  
#ifdef DOHASHSTATISTICS
  if (nraccesses % 100000 == 0)
    printf("Hash statistics: \n%lld stores, %lld steps"
           "\nNumber of vectors in Hash: %ld(of %ld).\n",
           nraccesses, nrsteps, ht->nr, ht->len);
#endif

  return h;
}

/* in case the hash value `hval' is already known */
long AddHTHVal(HashType *ht, void *x, long hval, long val)
{
  long h;

#ifdef DOHASHSTATISTICS
  nraccesses++;
#endif

  if (ht->len == ht->nr + 1) /* return HTFAIL; */ {
    printf("Error: Hash table too small, only %ld entries allowed.\n", 
	   ht->len - 1);
    exit(2);
  }
  h = hval;
  for (;ht->els[h] != NULL; ){

#ifdef DOHASHSTATISTICS
  nrsteps++;
#endif

    h++;
    if (h == ht->len) h = 0;
  }
  ht->els[h] = x;
  if (ht->vals != NULL)
    ht->vals[h] = val;
  ht->nr++;
  
#ifdef DOHASHSTATISTICS
  if (nraccesses % 100000 == 0)
    printf("Hash statistics: \n%lld stores, %lld steps"
           "\nNumber of vectors in Hash: %ld(of %ld).\n",
           nraccesses, nrsteps, ht->nr, ht->len);
#endif

  return h;
}

/* clearing a hash table for reuse */
void ClearHT(HashType *ht) 
{
  long h;
  void **p;
  p = ht->els;
  for (h = 0; h < ht->len; h++) {
    p[h] = NULL;
  }
  ht->nr = 0;
}


char current[25] = "                         ";
int available[6] = {0,5,5,5,5,5};  /* in the beginning 5 of each are allowed */
int counter = 0;

int fus[2298891];

void makevectors(int depth,int min,int used)
{
  /* depth: 1..25 next entry to choose
     min: minimal value of next entry
     used: biggest already used number */
  int i,newused;
  char *p;

  if (depth > 25) {
    /* Tue was mit hash: */
    p = malloc(26);
    strcpy(p,current);
    AddHT(vecs,p,25,fus[counter++]);
    return;
  }
  for (i = min;i <= 5;i++) {
    if (available[i] > 0 && used >= i-1) {
      /* we put an i on position depth and recurse down: */
      if (used < i) 
        newused = i;
      else
        newused = used;
      
      current[depth-1] = i+'0';
      available[i]--;

      if ((depth % 5) == 0) 
        /* we begin a new cluster */
	makevectors(depth+1,1,newused);
      else
        makevectors(depth+1,i,newused);

      available[i]++;
      current[depth-1] = ' ';
    }
  }
}

long hashfunc(void *vv,size_t len)
{
  long res;
  int i;
  char *p;
  char *v = vv;
  res = v[0];
  for (i = 1,p = v+1;i < len;i++,p++) 
    res = res * 6 + *p;
  return res;
} 

int vcmp(void *vv,void *ww,size_t len)
{
  char *v = vv;
  char *w = ww;
  return strcmp(v,w);
}

/* Apply permutation to vector: */

char *apply(char *v,int *p)
{
  /* Please make a copy of the result before you call me again! */
  static char resultbuf[26];
  char *r;
  int i;

  r = resultbuf;
  for (i = 0;i < 25;i++) *r++ = v[p[i]];
  *r = 0;
  return resultbuf;
}

char *Unormalize(char *v)
{
  /* Please make a copy of the result before you call me again! */
  static char resultbuf[26];
  static char tempbuf[26];
  int i,j,k;
  char *r;

  memset(tempbuf,0,26);
  r = v;
  /* Count occurances: */
  for (i = 0;i < 25;i += 5)   /* the clusters of 5 */
    for (j = 0;j < 5;j++,r++) /* within a cluster */
      tempbuf[i + *r - '1']++;
  /* Make result: */
  r = resultbuf;
  for (i = 0;i < 25;i += 5)   /* the clusters of 5 */
    for (j = 0;j < 5;j++)
      for (k = 0;k < tempbuf[i+j];k++)
        *r++ = j+'1';
  return resultbuf;
}

char *Snormalize(char *v)
{
  /* Please make a copy of the result before you call me again! */
  static char resultbuf[26];
  static char tab[5];
  char *r,*w;
  int count;
  int c;
  int i;

  memset(tab,0,5);
  count = 1;
  for (i = 0,r = v,w = resultbuf;i < 25;i++) {
    c = (*r++)-'1';
    if (tab[c] == 0)  /* not yet known */
      tab[c] = '0' + (count++);
    *w++ = tab[c];
  }
  *w++ = 0;
  return resultbuf;
}

int perms[1857][25];

void readperms(void)
{
  FILE *f;
  int i,j;

  f = fopen("perms.txt","r");
  for (i = 1;i <= 1856;i++) {
    for (j = 0;j < 25;j++) {
      fscanf(f,"%d",&(perms[i][j]));
    }
  }
  fclose(f);
}

void readfus(void)
{
  FILE *f;
  int i;

  f = fopen("fus.txt","r");
  for (i = 0;i < 2298891;i++)
    fscanf(f,"%d",&(fus[i]));
}

char loopcur[26] = "12345                    ";
char used[5][5];
void (*worker)(char *v);

void looping(int cluster,int index)
{
  int i;

  if (cluster == 5) {
    worker(loopcur);
    return;
  }
  for (i = 0;i < 5;i++) {
    if (!used[cluster][i]) {
      used[cluster][i] = 1;
      loopcur[cluster*5+index] = i+'1';
      if (index < 4)
        looping(cluster,index+1);
      else
        looping(cluster+1,0);
      loopcur[cluster*5+index] = ' ';
      used[cluster][i] = 0;
    }
  }
}

void doloop(void (*fun)(char *v))
{
  worker = fun;
  strcpy(loopcur,"12345                    ");
  memset(used, 0,25);
  looping(1,0);
}

int zeile[1857];

int permtoapply;

int donecounter = 0;

void aplnormcount(char *v)
{
  char *w;
  int orb;
  w = apply(v,perms[permtoapply]);
  w = Snormalize(w);
  w = Unormalize(w);
  orb = ValueHT(vecs,w,25);
  zeile[orb]++;
  if ((++donecounter) % 10000000 == 0) {
    fprintf(stderr,"%d %d\n",permtoapply,donecounter);
    fflush(stderr);
  }
}

int main(int argc,char *argv[])
{
  int first,last;
  int i,j;

  readperms();
  readfus();
  vecs = NewHT( 6000000,hashfunc,vcmp );
  makevectors(1,1,0);
  /*printf("%ld\n",ValueHT(vecs,"1234512345123451234512345",25));
  sleep(30);*/
  /* Jetzt geht's los: */
  first = atoi(argv[1]);
  last = atoi(argv[2]);
  fprintf(stderr,"Calculation starting...\n");
  fflush(stderr);
  printf("if not(IsBound(M)) then M:=[]; fi\n");
  fflush(stdout);
  for (i = first;i <= last;i++) {
    donecounter = 0;
    memset(zeile,0,sizeof(zeile));
    permtoapply = i;  
    doloop(aplnormcount);
    printf("M[%d] := [",i);
    for (j = 1;j <= 1856;j++) {
      printf("%d,",zeile[j]);
      if (j % 30 == 0) printf("\n");
    }
    printf("],\n");
    fflush(stdout);
  }
  printf("];\n");
  return 0;
}