main.c

   1
   2 #include <stdio.h>
   3 #include <stdint.h>
   4 #include <stdlib.h>
   5 #include <inttypes.h>
   6
   7 #include <publib.h>
   8
   9 typedef uint32_t AdjWord;
  10 #define PRADJ "08"PRIx32
  11
  12 static int n, m;
  13 static AdjWord *adjmatrix;
  14 static AdjWord adjall;
  15
  16 static double best;
  17
  18 static void prep(void) {
  19   adjall = ~((~(AdjWord)0) << m);
  20   adjmatrix = xmalloc(sizeof(*adjmatrix)*n);
  21 }
  22
  23 static int count_set_adj_bits(AdjWord w) {
  24   int j, total;
  25   for (j=0, total=0; j<m; j++)
  26     total += !!(w & ((AdjWord)1 << j));
  27   return total;
  28 }
  29
  30 static void optimise(void) {
  31   int i;
  32   for (i=0; i<n; i++) {
  33     printf("%"PRADJ" ", adjmatrix[i]);
  34     double maxminsize = (double)m / count_set_adj_bits(adjmatrix[i]);
  35     if (maxminsize < best) {
  36       printf(" too fine\n");
  37       return;
  38     }
  39   }
  40
  41   printf("nyi\n");
  42 }
  43
  44 static void iterate_recurse(int i, AdjWord min) {
  45   if (i >= n) {
  46     optimise();
  47     return;
  48   }
  49   for (adjmatrix[i] = min;
  50        ;
  51        adjmatrix[i]++) {
  52     iterate_recurse(i+1, adjmatrix[i]);
  53     if (adjmatrix[i] == adjall)
  54       return;
  55   }
  56 }
  57
  58 static void iterate(void) {
  59   iterate_recurse(0, 1);
  60 }
  61
  62 int main(int argc, char **argv) {
  63   n = atoi(argv[1]);
  64   m = atoi(argv[2]);
  65   prep();
  66   iterate();
  67   if (ferror(stdout) || fclose(stdout)) { perror("stdout"); exit(-1); }
  68   return 0;
  69 }