logik2.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4
   5 #define ORDER 5
   6 #define COLORS 8
   7 #define SHOTS 4
   8
   9 int states;
  10 char *flags;
  11 int secret;
  12
  13 int
  14 pack(int *z)
  15 {
  16   int k = 0;
  17   int i;
  18
  19   for(i=0; i<ORDER; i++)
  20     k = k*COLORS + *z++;
  21   return k;
  22 }
  23
  24 void
  25 unpack(int k, int *z)
  26 {
  27   int i;
  28
  29   for(i=ORDER-1; i >= 0; i--)
  30     {
  31       z[i] = k % COLORS;
  32       k /= COLORS;
  33     }
  34 }
  35
  36 void
  37 eval(int *sec, int *guess, int *black, int *white)
  38 {
  39   int b, w, i, sc[COLORS], gc[COLORS];
  40
  41   b = 0;
  42   bzero(sc, sizeof(sc));
  43   bzero(gc, sizeof(gc));
  44   for(i=0; i<ORDER; i++)
  45     if (sec[i] == guess[i])
  46       b++;
  47     else
  48       {
  49         sc[sec[i]]++;
  50         gc[guess[i]]++;
  51       }
  52   w = 0;
  53   for(i=0; i<COLORS; i++)
  54     if (gc[i] <= sc[i])
  55       w += gc[i];
  56     else
  57       w += sc[i];
  58   *black = b;
  59   *white = w;
  60 }
  61
  62 void
  63 show(int i)
  64 {
  65   int j, z[ORDER];
  66
  67   unpack(i, z);
  68   for(j=0; j<ORDER; j++)
  69     printf(" %d", z[j]);
  70 }
  71
  72 int
  73 xrand(int sz)
  74 {
  75   unsigned int i, ramax, RMX;
  76
  77   RMX = RAND_MAX + 1U;
  78   ramax = RMX - (RMX % sz);
  79   do
  80     i = random();
  81   while (i >= ramax);
  82   i %= sz;
  83   return i;
  84 }
  85
  86 #if 1
  87
  88 int sec[ORDER];
  89
  90 #if 0
  91
  92 void
  93 pl_init(void)
  94 {
  95   int i;
  96
  97   printf("Secret: ");
  98   for(i=0; i<ORDER; i++)
  99     scanf("%d", &sec[i]);
 100   secret = pack(sec);
 101   printf("Check:");
 102   show(secret);
 103   putchar('\n');
 104 }
 105
 106 #else
 107
 108 void
 109 pl_init(void)
 110 {
 111   secret = xrand(states);
 112   printf("Secret: ");
 113   unpack(secret, sec);
 114   show(secret);
 115   putchar('\n');
 116 }
 117
 118 #endif
 119
 120 void
 121 pl_eval(int *guess, int *b, int *w)
 122 {
 123   eval(sec, guess, b, w);
 124 }
 125
 126 #else
 127
 128 void
 129 pl_init(void)
 130 {
 131 }
 132
 133 void
 134 pl_eval(int *guess, int *b, int *w)
 135 {
 136   printf(" ...? ");
 137   fflush(stdout);
 138   scanf("%d%d", b, w);
 139 }
 140
 141 #endif
 142
 143 int
 144 reduce(int *gue, int b0, int w0)
 145 {
 146   int i,b,w,z[ORDER],c=0;
 147
 148   for(i=0; i<states; i++)
 149     if (!flags[i])
 150       {
 151         unpack(i, z);
 152         eval(z, gue, &b, &w);
 153         if (b != b0 || w != w0)
 154           flags[i] = 1;
 155         else
 156           c++;
 157       }
 158   if (!c)
 159     {
 160       puts("THIS CANNOT HAPPEN!");
 161       exit(1);
 162     }
 163   return c;
 164 }
 165
 166 int
 167 gen(int sz)
 168 {
 169   int i,j;
 170
 171   i = xrand(sz);
 172   for(j=0;;j++)
 173     if (!flags[j])
 174       if (!i--)
 175         return j;
 176 }
 177
 178 int
 179 howbad(int *z)
 180 {
 181   int G = 0;
 182   int i,b,w;
 183   int cc[ORDER+1][ORDER+1], g[ORDER];
 184
 185   bzero(cc, sizeof(cc));
 186   for(i=0; i<states; i++)
 187     if (!flags[i])
 188       {
 189         unpack(i, g);
 190         eval(g, z, &b, &w);
 191         cc[b][w]++;
 192       }
 193   for(b=0; b<=ORDER; b++)
 194     for(w=0; w<=ORDER; w++)
 195       if (cc[b][w] > G)
 196         G = cc[b][w];
 197   return G;
 198 }
 199
 200 int
 201 find_best(void)
 202 {
 203   int shot[SHOTS], badness[SHOTS], i, z[ORDER], sz, whe, besti, best, worsti;
 204
 205   sz = 0; whe = 0;
 206   for(i=0; i<states; i++)
 207     if (!flags[i])
 208       {
 209         sz++;
 210         whe = i;
 211       }
 212   if (sz == 1)
 213     {
 214       printf("SAFE ");
 215       return whe;
 216     }
 217   best = 0;
 218   besti = sz+1;
 219   worsti = 0;
 220   for(i=0; i<SHOTS; i++)
 221     {
 222       shot[i] = gen(sz);
 223       unpack(shot[i], z);
 224       badness[i] = howbad(z);
 225 //      printf("Try:");
 226 //      show(shot[i]);
 227 //      printf(" (%d/%d)\n", badness[i], sz);
 228       if (badness[i] < besti)
 229         {
 230           best = i;
 231           besti = badness[i];
 232         }
 233       if (badness[i] > worsti)
 234         worsti = badness[i];
 235     }
 236 //  printf("Best: %d (%d)\n", best, besti);
 237   printf("(%7d-%7d/%7d) ", worsti, besti, sz);
 238   return shot[best];
 239 }
 240
 241 int
 242 main(void)
 243 {
 244   int i,gue[ORDER],round,b,w,wc=0,N=0,sum=0;
 245
 246   states = 1;
 247   for(i=0; i<ORDER; i++)
 248     states *= COLORS;
 249   printf("%d positions, %d colors, %d states\n", ORDER, COLORS, states);
 250   flags = malloc(sizeof(char) * states);
 251
 252   for(;;)
 253     {
 254       N++;
 255       bzero(flags, sizeof(char) * states);
 256       pl_init();
 257       round = 0;
 258       for(;;)
 259         {
 260           i = find_best();
 261           printf("Q%d:", ++round);
 262           show(i);
 263           unpack(i,gue);
 264           pl_eval(gue, &b, &w);
 265           printf(" -> %d/%d -> %d states\n", b, w, reduce(gue,b,w));
 266           if (b == ORDER)
 267             break;
 268         }
 269       if (round > wc)
 270         wc = round;
 271       sum += round;
 272       printf("--- DONE --- (try=%d, worst case=%d, avg=%d) ---\n", N, wc, (sum+N-1)/N);
 273     }
 274
 275   return 0;
 276 }
 277