buckets.c

   1 #include <stdio.h>
   2
   3 #define MAX 12          // actually, it's 1 more than max
   4 #define NST (MAX*MAX*MAX)
   5
   6 int status[NST], queue[NST], back[NST], qr, qw;
   7 int capa[3], goal[MAX], gback[MAX];
   8
   9 #define ENCODE(i,j,k) ((i)*MAX*MAX+(j)*MAX+(k))
  10 #define DECODE(i,j,k,x) (i)=(x)/(MAX*MAX), (j)=(x)/MAX%MAX, (k)=(x)%MAX
  11
  12 static void go(int x, int *t)
  13 {
  14   // printf("\t-> %d %d %d\n", t[0], t[1], t[2]);
  15   int y = ENCODE(t[0], t[1], t[2]);
  16   if (status[y] < 0)
  17     {
  18       status[y] = status[x] + 1;
  19       queue[qw++] = y;
  20       back[y] = x;
  21     }
  22 }
  23
  24 static void search(void)
  25 {
  26   for (int i=1; i<NST; i++)
  27     status[i] = -1;
  28   for (int i=0; i<MAX; i++)
  29     goal[i] = -1;
  30   status[0] = 0;
  31   queue[0] = 0;
  32   qr = 0;
  33   qw = 1;
  34   while (qr < qw)
  35     {
  36       int x = queue[qr++];
  37       int t[3];
  38       DECODE(t[0],t[1],t[2],x);
  39       // printf("%5d %d,%d,%d (%d)\n", x, t[0], t[1], t[2], status[x]);
  40       for (int i=0; i<3; i++)
  41         if (goal[t[i]] < 0)
  42           {
  43             goal[t[i]] = status[x];
  44             gback[t[i]] = x;
  45           }
  46       for (int i=0; i<3; i++)
  47         {
  48           int z = t[i];
  49           t[i] = 0;
  50           go(x, t);
  51           t[i] = capa[i];
  52           go(x, t);
  53           t[i] = z;
  54         }
  55       for (int i=0; i<3; i++)
  56         for (int j=0; j<3; j++)
  57           if (i != j)
  58             {
  59               int r = capa[j] - t[j];
  60               if (r > t[i])
  61                 r = t[i];
  62               t[i]-=r; t[j]+=r;
  63               go(x, t);
  64               t[i]+=r; t[j]-=r;
  65             }
  66     }
  67 }
  68
  69 int main(void)
  70 {
  71 #if 1
  72   for (int f=0; f<NST; f++)
  73     {
  74       DECODE(capa[0], capa[1], capa[2], f);
  75       if (!capa[0] || !capa[1] || !capa[2]
  76           || (capa[0] == capa[1] || capa[0] == capa[2] || capa[1] == capa[2]) && 1
  77           || !(capa[0] <= capa[1] && capa[1] <= capa[2])
  78           )
  79         continue;
  80       printf("%d,%d,%d: ", capa[0], capa[1], capa[2]);
  81       search();
  82       int best = 0;
  83       for (int i=0; i<MAX; i++)
  84         if (goal[i] > goal[best])
  85           best = i;
  86       int reach = 0;
  87       for (int i=0; i<NST; i++)
  88         if (status[i] >= 0)
  89           reach++;
  90       printf("%2d (%d) r=%d\n", goal[best], best, reach);
  91     }
  92 #else
  93   capa[0] = 8;
  94   capa[1] = 5;
  95   capa[2] = 3;
  96   search();
  97   int r = gback[4];
  98   while (r > 0)
  99     {
 100       int a,b,c;
 101       DECODE(a,b,c,r);
 102       printf("%d,%d,%d\n", a,b,c);
 103       r = back[r];
 104     }
 105 #endif
 106   return 0;
 107 }