#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct {
   int u1, u2, u3;
} triple;

typedef struct _node {
   int nbr;
   struct _node *next;
} alnode;

typedef struct {
   int n;
   int *p;
   alnode **N;
} digraph;

int *genparams ( )
{
   int *params, T, done, g1, g2, g3;

   params = (int *)malloc(9 * sizeof(int));
   done = 0;
   do {
      T = params[6] = 15 + rand() % 16;
      T += params[7] = 15 + rand() % 16;
      T += params[8] = 15 + rand() % 16;
      params[2] = T = (T / 4) + rand() % (T / 2);
      params[2] -= params[0] = 1 + rand() % params[6];
      params[2] -= params[1] = 1 + rand() % params[7];
      if ((params[2] < 0) || (params[2] > params[8])) continue;
      g1 = 3 + rand() % 3;
      if (g1 == 3) {
         if (rand() % 2) { g2 = 4; g3 = 5; } else { g2 = 5; g3 = 4; }
      } else if (g1 == 4) {
         if (rand() % 2) { g2 = 3; g3 = 5; } else { g2 = 5; g3 = 3; }
      } else if (g1 == 5) {
         if (rand() % 2) { g2 = 3; g3 = 4; } else { g2 = 4; g3 = 3; }
      }
      if (rand() % 2) params[g1] = 0; else T -= params[g1] = params[3+g1];
      params[g3] = T -= params[g2] = 1 + rand() % params[3+g2];
      if ((params[g3] < 0) || (params[g3] > params[3+g3])) continue;
      done = 1;
   } while (!done);
   return params;
}

int tplcmp ( triple x, triple y )
{
   if (x.u1 > y.u1) return 1;
   if (x.u1 < y.u1) return -1;
   if (x.u2 > y.u2) return 1;
   if (x.u2 < y.u2) return -1;
   if (x.u3 > y.u3) return 1;
   if (x.u3 < y.u3) return -1;
   return 0;
}

int tplsrc ( triple x, triple *V, int n )
{
   int L, R, M, r;

   L = 0; R = n-1;
   while (L <= R) {
      M = (L + R) / 2;
      r = tplcmp(x,V[M]);
      if (r == 0) return M;
      if (r < 0) R = M - 1; else L = M + 1;
   }
   return -1;
}

triple *gennodes ( int a1, int a2, int a3, int c1, int c2, int c3, int *n, int *sidx )
{
   triple *V, s;
   int T, k, l, u1, u2, u3;

   V = (triple *)malloc((c1 + 1) * (c2 + 1) * (c3 + 1) * sizeof(triple));
   T = a1 + a2 + a3;
   k = 0;
   for (u1=0; u1<=c1; ++u1) {
      for (u2=0; u2<=c2; ++u2) {
         u3 = T - (u1 + u2);
         if ((u3 >= 0) && (u3 <= c3)) {
            if ((u1 == 0) || (u2 == 0) || (u3 == 0) || (u1 == c1) || (u2 == c2) || (u3 == c3))
               V[k++] = (triple){u1,u2,u3};
         }
      }
   }
   s = (triple){a1,a2,a3};
   *sidx = tplsrc(s,V,k);
   if (*sidx < 0) {
      l = k++;
      while ((l > 0) && (tplcmp(s,V[l-1]) < 0)) {
         V[l] = V[l-1];
         --l;
      }
      V[l] = s;
      *sidx = l;
   }
   V = (triple *)realloc(V,k*sizeof(triple));
   *n = k;
   return V;
}

void addnode ( digraph G, triple *V, int n, int u, int t1, int t2, int t3 )
{
   int v;
   alnode *p;

   v = tplsrc((triple){t1,t2,t3},V,n);
   p = (alnode *)malloc(sizeof(alnode));
   p -> nbr = v;
   p -> next = G.N[u];
   G.N[u] = p;
}

digraph gengph ( triple *V, int n, int c1, int c2, int c3 )
{
   digraph G;
   int u, s1, s2, s3, t, t1, t2;

   G.n = n;
   G.p = (int *)malloc(n * sizeof(int));
   G.N = (alnode **)malloc(n * sizeof(alnode *));
   for (u=0; u<n; ++u) {
      G.p[u] = -1;
      G.N[u] = NULL;
   }
   for (u=0; u<n; ++u) {
      s1 = V[u].u1; s2 = V[u].u2; s3 = V[u].u3;

      t1 = 0;
      if ((s3) && (s1 < c1)) t1 = ((c1 - s1) <= s3) ? c1 - s1 : s3;
      t2 = 0;
      if ((s2) && (s1 < c1)) t2 = ((c1 - s1) <= s2) ? c1 - s1 : s2;
      if ((t1 > 0) && (t2 > 0)) {
         if (t1 >= t2) {
            addnode(G,V,n,u,s1+t1,s2,s3-t1);
            addnode(G,V,n,u,s1+t2,s2-t2,s3);
         } else {
            addnode(G,V,n,u,s1+t2,s2-t2,s3);
            addnode(G,V,n,u,s1+t1,s2,s3-t1);
         }
      } else {
         if (t1 > 0) addnode(G,V,n,u,s1+t1,s2,s3-t1);
         if (t2 > 0) addnode(G,V,n,u,s1+t2,s2-t2,s3);
      }

      if ((s3) && (s2 < c2)) {
         t = ((c2 - s2) <= s3) ? c2 - s2 : s3;
         addnode(G,V,n,u,s1,s2+t,s3-t);
      }
      if ((s2) && (s3 < c3)) {
         t = ((c3 - s3) <= s2) ? c3 - s3 : s2;
         addnode(G,V,n,u,s1,s2-t,s3+t);
      }

      t1 = 0;
      if ((s1) && (s3 < c3)) t1 = ((c3 - s3) <= s1) ? c3 - s3 : s1;
      t2 = 0;
      if ((s1) && (s2 < c2)) t2 = ((c2 - s2) <= s1) ? c2 - s2 : s1;
      if ((t1 > 0) && (t2 > 0)) {
         if (t1 >= t2) {
            addnode(G,V,n,u,s1-t2,s2+t2,s3);
            addnode(G,V,n,u,s1-t1,s2,s3+t1);
         } else {
            addnode(G,V,n,u,s1-t1,s2,s3+t1);
            addnode(G,V,n,u,s1-t2,s2+t2,s3);
         }
      } else {
         if (t1 > 0) addnode(G,V,n,u,s1-t1,s2,s3+t1);
         if (t2 > 0) addnode(G,V,n,u,s1-t2,s2+t2,s3);
      }
   }
   return G;
}

void prntpl ( triple x )
{
   printf("(%2d,%2d,%2d)", x.u1, x.u2, x.u3);
}

void prngph ( digraph G, triple *V )
{
   int u;
   alnode *p;

   for (u=0; u<G.n; ++u) {
      printf("    "); prntpl(V[u]); printf(" ->");
      p = G.N[u];
      while (p) {
         printf(" "); prntpl(V[p->nbr]);
         p = p -> next;
      }
      printf("\n");
   }
}

void BFS ( digraph G, int s )
{
   alnode *p;
   int u, v;
   int *Q, F, B;

   G.p[s] = s;

   Q = (int *)malloc((G.n) * sizeof(int));
   Q[F = B = 0] = s;

   while (F <= B ) {
      u = Q[F++];
      p = G.N[u];
      while (p) {
         v = p -> nbr;
         if (G.p[v] == -1) {
            G.p[v] = u;
            Q[++B] = v;
         }
         p = p -> next;
      }
   }
}

void prnpath ( digraph G, int s, int u, int v, triple *V )
{
   int r;

   r = G.p[u];
   if (u != s) prnpath(G,s,r,u,V);
   printf("    "); prntpl(V[u]);
   if (v != -1) {
      printf(" ==> ");
      if (V[u].u1 == V[v].u1) {
         if (V[v].u2 < V[u].u2)
            printf("Transfer %2d ml from Glass 2 to Glass 3 ==>", V[u].u2 - V[v].u2);
         else
            printf("Transfer %2d ml from Glass 3 to Glass 2 ==>", V[u].u3 - V[v].u3);
      } else if (V[u].u2 == V[v].u2) {
         if (V[v].u1 < V[u].u1)
            printf("Transfer %2d ml from Glass 1 to Glass 3 ==>", V[u].u1 - V[v].u1);
         else
            printf("Transfer %2d ml from Glass 3 to Glass 1 ==>", V[u].u3 - V[v].u3);
      } else if (V[u].u3 == V[v].u3) {
         if (V[v].u1 < V[u].u1)
            printf("Transfer %2d ml from Glass 1 to Glass 2 ==>", V[u].u1 - V[v].u1);
         else
            printf("Transfer %2d ml from Glass 2 to Glass 1 ==>", V[u].u2 - V[v].u2);
      }
   }
   printf("\n");
}

int main ( )
{
   int a1, a2, a3, b1, b2, b3, c1, c2, c3;
   int *params, n, s, t, i;
   triple *V;
   digraph G;

   srand((unsigned int)time(NULL));

   params = genparams();
   a1 = params[0]; a2 = params[1]; a3 = params[2];
   b1 = params[3]; b2 = params[4]; b3 = params[5];
   c1 = params[6]; c2 = params[7]; c3 = params[8];
   free(params);
   printf("Glass capacities : %2d %2d %2d\n", c1, c2, c3);
   printf("Initial contents : %2d %2d %2d\n", a1, a2, a3);
   printf("Final contents   : %2d %2d %2d\n", b1, b2, b3);

   V = gennodes(a1,a2,a3,c1,c2,c3,&n,&s);
   printf("\n+++ The vertices are");
   for (i=0; i<n; ++i) {
      if (i % 7 == 0) printf("\n   ");
      printf(" (%2d,%2d,%2d)", V[i].u1, V[i].u2, V[i].u3);
   }
   printf("\n");

   G = gengph(V,n,c1,c2,c3);
   printf("\n+++ Graph generated\n");
   prngph(G,V);

   t = tplsrc((triple){b1,b2,b3},V,n);
   BFS(G,s);
   if (G.p[t] == -1) {
      printf("\n+++ No solution\n");
   } else {
      printf("\n+++ Make the following moves\n");
      printf("--- [%2d,%2d,%2d] : Capacities\n\n", c1, c2, c3);
      prnpath(G,s,t,-1,V);
   }

   exit(0);
}