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


#define NBCODES  4
#define LONGUEUR 8
#define DISTANCE 5

unsigned int codes[NBCODES] = {0};


/*
 * Calcule la distance de Hamming entre deux codes 
 * (chaque code est donné sur un entier non signé)
 */

int distHamming(unsigned a, unsigned b) {
  int i = 0;
  int n = 0;
  int x = a ^ b;
  for( i = 0 ; i < LONGUEUR ; i++ ) {
    if (x & 1)
      n++;
    x >>= 1;
  }
  return n;
}



/* Vérifie que codes[n] soit à une distance suffisante 
 * des codes d'indices inférieurs.
 */

unsigned checkLevel(unsigned n) {
  int i;
  for ( i = 0 ; i < n ; i++ ) { 
    if ( distHamming(codes[i],codes[n]) < DISTANCE ) {
      return 0;
    }
  }
  return 1;
}


/* 
 * fonction récursive de recherche avec retour arrière (backtracking) :
 * cette fonction retourne la valeur 1 si elle trouve une solution au problème
 * (auquel cas elle laisse cette solution dans le tableau codes), 0 sinon.
 */

unsigned searchBackTrack(unsigned level, unsigned codestart) {

  /* a) il y une solution !! : 
   * arrêter le processus de recherche avec retour arrière
   */
  if ( level >= NBCODES )
    return 1;
  
  /* b) sinon recherche classique par retour arrière : 
   *    d'abord énumérer tous les codes possibles ..
   * 	( > codestart plutot que de commencer à 0 )
   */

  codes[level] = codestart;

  while ( codes[level] <  1 << LONGUEUR  ) {
    
    /* si les distances sont valides entre les codes[0], ... ,codes[level-1] 
     * et le code[level],
     */

    if ( checkLevel(level) ) 
      /* alors essayer de trouver les codes[level+1] .. codes[NBCODES-1] */
      if (searchBackTrack( level + 1, codes[level] ))
	return 1; /* si trouvés, alors arrêter la fonction car solution */
    
    /* sinon, c'est qu'il n'y a pas de solutions possibles commençant 
     * par les codes[0] .. codes[level] actuels : on change alors 
     * codes[level] et on réessaye ...
     */
    codes[level]++;
  }
  
  /* jusqu'à ce que l'on epuise tous les codes possibles pour codes[level] :
   * dans ce cas il n'y a pas de solutions possibles commençant par 
   * les codes[0] .. codes[level-1] : il faut donc faut retourner 
   * au niveau "level - 1" en signalant l'abscence de solution
   */
  
  return 0;
}


int main() {
  int i;
  
  printf("recherche de %d codes de longueur fixe %d ayant une distance de Hamming respective d'au moins %d ... ",NBCODES,LONGUEUR,DISTANCE);

  if (searchBackTrack(0 /*level*/, 0 /* recherche à partir d'un code */) ){
        
    printf("la première solution trouvée: \n");
    
    for(i = 0 ; i < NBCODES ; i++)
      printf(" - %x\n",(unsigned)(codes[i]));

  }else{

    printf("pas de solution.\n");

  }
  
  return 0;
}