TRI-HEXAGONAL PUZZLE

Description:

"Little Johnny wants to play with his friends today. But his babysitter won't let him go! After a lot of begging, the heartless nanny gives him her brand new electronic puzzle and says: ""If you solve the puzzle then you are free to go"". Not being aware of Little Johnny's IT skills, the nanny leaves the kid alone. Rapidly, Little Johnny sends you an e-mail asking for your help. The puzzle consists of three hexagons as shown in the figure. Each vertex is painted black or white. Some of them belong to just one hexagon and some of them belong to more than one. Exactly four of them are painted black, and the other nine are white. The goal is to make the shared vertexes black by means of allowed moves: rotating a hexagon 60 degrees clockwise or counter-clockwise. Can you help Little Johnny? Input Input starts with an integer T, the number of puzzles to solve (1<=T<=100). T lines follow, each one having 13 binary digits, corresponding to the top-down, left to right labeling of the vertexes in the puzzle. A '0' means the i-th vertex is painted white, while a '1' means it is painted black. Output For each test case output M on a single line, the minimum number of moves required to solve the puzzle. Then print M lines, each one describing a move in the following manner: two space separated integers H and C, the rotated hexagon (upper left is 0, upper right is 1, lower one is 2) and the direction (0 for counter-clockwise, 1 for clockwise). If there is more than one solution, any will suffice. Test Case 1 Input (stdin) 1 0000000101011 Expected Output 3 2 0 2 0 1 1 Test Case 2 Input (stdin) 1 0001000100011 Expected Output 4 2 0 2 0 0 1 1 1

Program :

#include <stdio.h>

#define MX 13

#define NS 715


int se[NS],pi[NS],pm[NS],cu,n;

char pu[MX+1];

const int bi[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096};

const int mo[6][7]={{10,12,9,6,4,7,10},{10,7,4,6,9,12,10},{5,3,6,9,11,8,5},{5,8,11,9,6,3,5},{4,6,3,1,0,2,4},{4,2,0,1,3,6,4}};

const int go=0x258;

int f1(int m,int p)

{

  int c=p,i=0;

  for(;i++<6;c=((p&bi[mo[m][i]]))?(c|bi[mo[m][i-1]]):(c&(~bi[mo[m][i-1]])));

  return c;

}

int f2(int c)

{

  int i;

  for(i=cu-1;i>=0;i--)

    if(c==se[i])

      return i;

  return -1;

}

int f3(char p[])

{

  int i=0,s=0;

  for(;i<MX;s=(p[i]=='1')?(s|bi[MX-i-1]):s,i++);

  return s;

}

void f4(int s)

{

  int i=0,j,p[12],in=f2(s);

  for(;in;p[i++]=pm[in],in=pi[in]);

  for(printf("%d\n",i+(j=0));j++<i;printf("%d %d\n",(p[j-1]>>1),(p[j-1]%2)));

}

int main()

{

  int fall,p=0,m,c;

  for(se[!(cu=1)]=go;p<cu;p++)

    for(m=0;m<6;m++)

      if(f2(c=f1(m,se[p]))==-1)

      {

        se[cu]=c;

        pi[cu]=p;

        pm[cu++]=m^0x1;

      }

  for(scanf("%d",&fall);fall--;)

  {

    scanf("%s",pu);

    f4(f3(pu));

  }


return 0;

}