#include"lib.h"

fc fi, fo;
int mot[1000000], code[1000], mot2[1000000];
int i, j, s, k, size, x, nb, mnb, pos, a_o, a_i, lim, c;

int additive(int *m, int i){
  int a, b, d, l = i+1;
  if(i && m[i] == m[i-1]) return 0;
  for(a = i-1; a >= 0 && i-a <= c; a--) if(m[i] == m[a]) return 0;
  for(b = c+1; 2*b <= l; b++){
    for(d = a = 0; d <= c && a < b; a++) d += m[l-2*b+a] != m[l-b+a];
    if(d <= c) return 0;
  }
  return 1;
}//*/

int ok(){
  if(mnb < nb) {printf("nb=%d", mnb = nb);date("");}
  for(k = 0; k < size; k++)
    if(mot[k+(nb-2)*size] > mot[k+(nb-1)*size]) break;
    else if(mot[k+(nb-2)*size] < mot[k+(nb-1)*size]){ i -= size; return 0;}//*/
  for(*code = x = 0; ;) if(!fi(code, x)){
    ici: while(code[x] == nb-1)if(!x--) return 1;
    code[x]++;
  }else{
    s = nb-1-code[x];//optimized version
    //s = code[x];//old version
    for(k = 0; k < size; k++){
      mot2[pos = k+x*size] = mot[k+s*size];
      if(x && !fo(mot2, pos)) return 0;
    }
    if(x == lim-1) goto ici; else code[++x] = 0;
  }
}

int other(){
 if(i%size <= c+1 && mot[i] != i%size) return 0;// optimization here
 if(i >= size) for(k = i-i%size; k <= i; k++)
   if(mot[k] < mot[k-size]) break; else if(mot[k] > mot[k-size]){
    i -= i%size+1;
    return 0;
   }//*/
  for(k = 0; k <= i%size; k++) mot2[size+k] = mot[i-i%size+k];
  for(k = 0; k < i/size-1; k++){
    for(j = 0; j < size; j++) mot2[j] = mot[k*size+j];
    if(!fo(mot2, size+i%size)) return 0;
  }
  return 1;
}

int A(){
  for(i = 0; i < size; i++) mot[i] = 0;
  mnb = nb = 0;
  printf("a_o=%d c=%d size=%d lim=%d", a_o, c, size, lim); date("");
  for(*mot = i = 0; ;) if(!fo(mot, i) || !other()){
    here: while(mot[i] == a_o-1) if(!--i) return 1;
    if(i <= c+1 && mot[i] > i) return nb; //optimisation au cas par cas
    mot[i]++;
  }else if(!((i+1)%size) && ((nb = (i+1)/size) > 1))
    if(!ok()) goto here; else if(nb == a_i) break; else goto there;
    else there: mot[++i] = 0;
  for(x = 0; x < a_i; x++, printf("\n")) for(k = 0; k < size; k++)
    printf("%c", ((j = mot[k+x*size]) < 10 ? '0'+j : 'A'+j-10));
  printf("OK size=%d lim=%d", size, lim); date("");
  return 0;
}

void usage(){
  printf("Usage: additive a_o c [size [lim]]\n");
  exit(0);
}

int main(int ac, char **av){
  if(ac < 3) usage();
  fo = additive; //property of output word
  fi = sqf; //property of input word
  //fi = rt3; //property of input word
  a_i = 3; //size of input alphabet
  a_o = atoi(av[1]); //size of output alphabet
  c = atoi(av[2]); //avoids c-approx squares
  size = ac > 3 ? atoi(av[3]) : c; //starting size of uniform morphism
  lim  = ac > 4 ? atoi(av[4]) : 10; //length of tested input words
  printf("a_i=%d a_o=%d\n", a_i, a_o);
  for(; A() && size < 1000; size++);
  date("END");
}
/*
a_o=9 size=36 lim=10: 19/01/2007 16/22/16
nb=2: 19/01/2007 16/22/16
nb=3: 19/01/2007 16/22/16
012345607821345062718345670281346578
012345607182346750812347685102346578
012345607182346510872345681702346578
OK size=36 lim=10: 19/01/2007 16/22/18

a_o=11 size=20 lim=10: 19/01/2007 16/21/03
nb=2: 19/01/2007 16/21/03
nb=3: 19/01/2007 16/21/06
012345670A812954768A
0123456709A1843576A9
01234567089A24365798
OK size=20 lim=10: 19/01/2007 16/21/43

a_o=12 size=24 lim=10: 19/01/2007 16/27/36
nb=2: 19/01/2007 16/27/37
nb=3: 19/01/2007 16/27/40
012345678091AB2354687A9B
012345678091A3B4257689AB
012345678091A2B3465798AB
OK size=24 lim=10: 19/01/2007 16/27/47

a_o=13 size=26 lim=10: 19/01/2007 16/47/32
nb=2: 19/01/2007 16/47/32
nb=3: 19/01/2007 16/47/36
01234567890A1BC24635798BAC
01234567890A1B3C4257689ABC
01234567890A1B2C354687A9BC
OK size=26 lim=10: 19/01/2007 16/47/51

a_o=14 size=28 lim=20: 19/01/2007 17/34/33
nb=2: 19/01/2007 17/34/37
nb=3: 19/01/2007 17/34/49
0123456789A0B1DC32465798BDAC
0123456789A0B1DC243576A98DBC
0123456789A0B1CD325468A79CBD
OK size=28 lim=20: 19/01/2007 17/36/00

a_o=15 size=30 lim=10: 19/01/2007 18/08/01
nb=2: 19/01/2007 18/08/16
nb=3: 19/01/2007 18/08/31
0123456789AB0D1CE3246579B8ACDE
0123456789AB0D1CE2435768A9DCBE
0123456789AB0CED32154687BA9DEC
OK size=30 lim=10: 19/01/2007 18/19/49
*/