logik1.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4
   5 #define BITS 10
   6 #define NUM (1 << BITS)
   7
   8 static char state[NUM];
   9 static int question;
  10
  11 static void
  12 calc_answer(int secret, int guess, int *black, int *white)
  13 {
  14   int b = 0, w = 0, i;
  15   int s0=0, s1=0, g0=0, g1=0;
  16
  17   for(i=0; i<BITS; i++)
  18     if (!((secret^guess) & (1 << i)))
  19       b++;
  20     else
  21       {
  22         if (secret & (1 << i))
  23           s1++;
  24         else
  25           s0++;
  26         if (guess & (1 << i))
  27           g1++;
  28         else
  29           g0++;
  30       }
  31
  32   w = ((s0 < g0) ? s0 : g0) + ((s1 < g1) ? s1 : g1);
  33
  34   *black = b;
  35   *white = w;
  36 }
  37
  38 static void
  39 find_best(void)
  40 {
  41   int i, j, x, y, best, besti, total, black, white, answer[BITS+1][BITS+1];
  42
  43   total = 0;
  44   best = -1;
  45   for(i=0; i<NUM; i++)
  46     {
  47       if (!state[i])
  48         {
  49           best = i;
  50           total++;
  51         }
  52     }
  53   if (total == 1)
  54     {
  55       printf("Final decision: %02x\n", best);
  56       question = best;
  57       return;
  58     }
  59   best = -1;
  60   besti = NUM+1;
  61   for(i=0; i<NUM; i++)
  62     {
  63       bzero(answer, sizeof(answer));
  64       for(j=0; j<NUM; j++)
  65         if (!state[j])
  66           {
  67             calc_answer(i, j, &black, &white);
  68             answer[black][white]++;
  69           }
  70       j = 0;
  71       for(x=0; x<=BITS; x++)
  72         for(y=0; y<=BITS; y++)
  73           if (answer[x][y] > j)
  74             j = answer[x][y];
  75       if (j <= besti)
  76         {
  77           besti = j;
  78           best = i;
  79         }
  80     }
  81   question = best;
  82   printf("Selected %04x, %d of %d\n", best, besti, total);
  83 }
  84
  85 static void
  86 recalc(int b, int w)
  87 {
  88   int bl, wh, i, red = 0;
  89
  90   for(i=0; i<NUM; i++)
  91     if (!state[i])
  92       {
  93         calc_answer(i, question, &bl, &wh);
  94         if (b != bl || w != wh)
  95           {
  96 //          printf("Throwing out %02x (%d,%d) != (%d,%d)\n", i, b, w, bl, wh);
  97             state[i] = 1;
  98           }
  99         else
 100           red++;
 101       }
 102   printf("Reduced to %d\n", red);
 103   if (!red)
 104     {
 105       puts("ERROR");
 106       exit(1);
 107     }
 108 }
 109
 110 int
 111 main(void)
 112 {
 113   int b, w;
 114   int secr, round, maxr=0;
 115
 116   for(secr=0; secr<NUM; secr++)
 117     {
 118       printf("SECRET=%02x\n", secr);
 119       bzero(state, sizeof(state));
 120       round=0;
 121       for(;;)
 122         {
 123           round++;
 124           find_best();
 125           calc_answer(secr, question, &b, &w);
 126           printf("%d: Answer is %d/%d\n", round, b, w);
 127           if (b == BITS)
 128             break;
 129           recalc(b, w);
 130         }
 131       if (round > maxr)
 132         maxr = round;
 133       puts("------------------------------------------");
 134     }
 135   printf("MAX=%d rounds\n", maxr);
 136
 137   return 0;
 138 }