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   /*
  42    * We formulate our problem as an LP problem as follows.
  43    * In this file "n" and "m" are the matchstick numbers.
  44    *
  45    * Each set bit in the adjacency matrix corresponds to taking a
  46    * fragment from old match i and making it part of new match j.
  47    *
  48    * The structural variables (columns) are:
  49    *   x_fragsz_i_j    the size of that fragment
  50    *   x_minimum       minimum size of any fragment
  51    *
  52    * The auxiliary variables (rows, constraints) are:
  53    *   x_total_i       total length for each input match (fixed variable)
  54    *   x_total_j       total length for each output match (fixed variable)
  55    *   x_fragmin_i_j   amount by which fragment is > minimum (lower bound 0)
  56    *
  57    * The objective function is simply to maximise x_minimum
  58    */
  59
  60   printf("nyi\n");
  61 }
  62
  63 static void iterate_recurse(int i, AdjWord min) {
  64   if (i >= n) {
  65     optimise();
  66     return;
  67   }
  68   for (adjmatrix[i] = min;
  69        ;
  70        adjmatrix[i]++) {
  71     iterate_recurse(i+1, adjmatrix[i]);
  72     if (adjmatrix[i] == adjall)
  73       return;
  74   }
  75 }
  76
  77 static void iterate(void) {
  78   iterate_recurse(0, 1);
  79 }
  80
  81 int main(int argc, char **argv) {
  82   n = atoi(argv[1]);
  83   m = atoi(argv[2]);
  84   prep();
  85   iterate();
  86   if (ferror(stdout) || fclose(stdout)) { perror("stdout"); exit(-1); }
  87   return 0;
  88 }