/* 
 * File:   checkS1.c
 * Author: kouno
 *
 * Created on 2008/04/30, 22:48
 */

#define KNOOUT 0

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

#define EXIT_FALSE 1
#define MAX_VERTEX_SIZE 15
#define MAX_EDGE_SIZE 2*MAX_VERTEX_SIZE
#define MAX_FACE_SIZE MAX_VERTEX_SIZE+1
#define MAX_LINE 1024
#define OUTFILE "S1check"
FILE *fpin,*fpout;
char b[MAX_LINE];
int E[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE];
int E1[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE];
int Type[MAX_VERTEX_SIZE];
int Type1[MAX_VERTEX_SIZE];
int L[MAX_VERTEX_SIZE];
int D[MAX_VERTEX_SIZE];
int DD[MAX_VERTEX_SIZE];
int T[MAX_VERTEX_SIZE];
int L1[MAX_VERTEX_SIZE];
int D1[MAX_VERTEX_SIZE];
int DD1[MAX_VERTEX_SIZE];
int T1[MAX_VERTEX_SIZE];
int s[MAX_VERTEX_SIZE];
int sD[MAX_VERTEX_SIZE];
int sDD[MAX_VERTEX_SIZE];
int sT[MAX_VERTEX_SIZE];
int t[MAX_VERTEX_SIZE];
int Lnum,Dnum,DDnum,Tnum;
int Lnum1,Dnum1,DDnum1,Tnum1;
int f_flag;
int i,i1,wi,p,q,r;
int end_flag=0;

int dlength(int n){
  if(n<=-100) return 4;
  if(n<=-10) return 3;
  if(n<0) return 2;
  if(n<10) return 1;
  if(n<100) return 2;
  return 3;
}

int next_L(void){
  for(i=Lnum;1<i;i--){
    if(s[i-1]<s[i]){break;}
  }
  if(i<=1){return 0;}
  for(i1=Lnum;1<i1;i1--){
    if(s[i-1]<s[i1]){break;}
  }
  t[i-1]=s[i1];
  for(wi=Lnum;i1<wi;wi--){t[Lnum+i-wi]=s[wi];}
  t[i+Lnum-i1]=s[i-1];
  for(wi=i1-1;i<=wi;wi--){t[Lnum+i-wi]=s[wi];}
  for(wi=i-1;wi<=Lnum;wi++){s[wi]=t[wi];}
  for(i=1;i<=Dnum;i++){sD[i]=i;}
  for(i=1;i<=DDnum;i++){sDD[i]=i;}
  for(i=1;i<=Tnum;i++){sT[i]=i;}
  return 1;
}

int next_D(void){
  for(i=Dnum;1<i;i--){
    if(sD[i-1]<sD[i]){break;}
  }
  if(i<=1){return 0;}
  for(i1=Dnum;1<i1;i1--){
    if(sD[i-1]<sD[i1]){break;}
  }
  t[i-1]=sD[i1];
  for(wi=Dnum;i1<wi;wi--){t[Dnum+i-wi]=sD[wi];}
  t[i+Dnum-i1]=sD[i-1];
  for(wi=i1-1;i<=wi;wi--){t[Dnum+i-wi]=sD[wi];}
  for(wi=i-1;wi<=Dnum;wi++){sD[wi]=t[wi];}
  for(i=1;i<=DDnum;i++){sDD[i]=i;}
  for(i=1;i<=Tnum;i++){sT[i]=i;}
  return 1;
}

int next_DD(void){
  for(i=DDnum;1<i;i--){
    if(sDD[i-1]<sDD[i]){break;}
  }
  if(i<=1){return 0;}
  for(i1=DDnum;1<i1;i1--){
    if(sDD[i-1]<sDD[i1]){break;}
  }
  t[i-1]=sDD[i1];
  for(wi=DDnum;i1<wi;wi--){t[DDnum+i-wi]=sDD[wi];}
  t[i+DDnum-i1]=sDD[i-1];
  for(wi=i1-1;i<=wi;wi--){t[DDnum+i-wi]=sDD[wi];}
  for(wi=i-1;wi<=DDnum;wi++){sDD[wi]=t[wi];}
  for(i=1;i<=Tnum;i++){sT[i]=i;}
  return 1;
}

int next_T(void){
  for(i=Tnum;1<i;i--){
    if(sT[i-1]<sT[i]){break;}
  }
  if(i<=1){return 0;}
  for(i1=Tnum;1<i1;i1--){
    if(sT[i-1]<sT[i1]){break;}
  }
  t[i-1]=sT[i1];
  for(wi=Tnum;i1<wi;wi--){t[Tnum+i-wi]=sT[wi];}
  t[i+Tnum-i1]=sT[i-1];
  for(wi=i1-1;i<=wi;wi--){t[Tnum+i-wi]=sT[wi];}
  for(wi=i-1;wi<=Tnum;wi++){sT[wi]=t[wi];}
  return 1;
}

void get_base_S1_data(void){
  int wj,w1,w2,w3,w4;
  char *bb;
  for(w1=1;w1<=MAX_VERTEX_SIZE;w1++){
    Type[w1]=0;
    for(w2=1;w2<=MAX_VERTEX_SIZE;w2++){
      E[w1][w2]=0;
    }
  }
  wj=0;bb=b;
  while(sscanf(bb,"(%d,%d)",&w1,&w2)){wj++;
  bb=bb+4+dlength(w1)+dlength(w2);
  E[w1][w2]++;E[w2][w1]++;
  if(w1==w2){Type[w1]=-1;}
  if(E[w1][w2]==2){if(0<=Type[w1])Type[w1]++;if(0<=Type[w2])Type[w2]++;}
  //  printf("[%d]->(%d,%d)",wj,w1,w2);//debug
  }
  q=wj;p=wj/2;r=p+1;
  Lnum=0;Dnum=0;DDnum=0;Tnum=0;
  w1=1;w2=1;w3=1;w4=1;
  for(i=1;i<=p;i++){
    if(Type[i]==-1){Lnum++;L[w1]=i;w1++;}
    if(Type[i]==1){Dnum++;D[w2]=i;w2++;}
    if(Type[i]==2){DDnum++;DD[w3]=i;w3++;}
    if(Type[i]==0){Tnum++;T[w4]=i;w4++;}
  }
  //printf("Lnum[%d] Dnum[%d] DDnum[%d] Tnum[%d]\n",Lnum,Dnum,DDnum,Tnum);
  //printf("L ");for(i=1;i<=Lnum;i++){printf("%d ",L[i]);}
  //printf("D ");for(i=1;i<=Dnum;i++){printf("%d ",D[i]);}
  //printf("DD ");for(i=1;i<=DDnum;i++){printf("%d ",DD[i]);}
  //printf("T ");for(i=1;i<=Tnum;i++){printf("%d ",T[i]);}printf("\n");
}

void get_S1_data(void){
  int wj,w1,w2,w3,w4;
  char *bb;
  for(w1=1;w1<=MAX_VERTEX_SIZE;w1++){
    Type1[w1]=0;
    for(w2=1;w2<=MAX_VERTEX_SIZE;w2++){
      E1[w1][w2]=0;
    }
  }
  wj=0;bb=b;
  while(sscanf(bb,"(%d,%d)",&w1,&w2)){wj++;
  bb=bb+4+dlength(w1)+dlength(w2);
  E1[w1][w2]++;E1[w2][w1]++;
  if(w1==w2){Type1[w1]=-1;}
  if(E1[w1][w2]==2){if(0<=Type1[w1])Type1[w1]++;if(0<=Type1[w2])Type1[w2]++;}
  //  printf("[%d]->(%d,%d)",wj,w1,w2);//debug
  }
  q=wj;p=wj/2;r=p+1;
  Lnum1=0;Dnum1=0;DDnum1=0;Tnum1=0;
  w1=1;w2=1;w3=1;w4=1;
  for(i=1;i<=p;i++){
    if(Type1[i]==-1){Lnum1++;L1[w1]=i;w1++;}
    if(Type1[i]==1){Dnum1++;D1[w2]=i;w2++;}
    if(Type1[i]==2){DDnum1++;DD1[w3]=i;w3++;}
    if(Type1[i]==0){Tnum1++;T1[w4]=i;w4++;}
  }
  //printf("Lnum1[%d] Dnum1[%d] DDnum1[%d] Tnum1[%d]\n",Lnum1,Dnum1,DDnum1,Tnum1);
  //printf("L1 ");for(i=1;i<=Lnum1;i++){printf("%d ",L1[i]);}
  //printf("D1 ");for(i=1;i<=Dnum1;i++){printf("%d ",D1[i]);}
  //printf("DD1 ");for(i=1;i<=DDnum1;i++){printf("%d ",DD1[i]);}
  //printf("T1 ");for(i=1;i<=Tnum1;i++){printf("%d ",T1[i]);}printf("\n");
}
int check_this_data(void){
  int wi;
  for(i=1;i<=Lnum;i++){
    for(wi=1;wi<=Lnum;wi++){
      if(E[L[i]][L[wi]]!=E1[L1[s[i]]][L1[s[wi]]]&& i!=wi) return 0;
    }
    for(wi=1;wi<=Dnum;wi++){
      if(E[L[i]][D[wi]]!=E1[L1[s[i]]][D1[sD[wi]]]) return 0;
    }
    for(wi=1;wi<=DDnum;wi++){
      if(E[L[i]][DD[wi]]!=E1[L1[s[i]]][DD1[sDD[wi]]]) return 0;
    }
    for(wi=1;wi<=Tnum;wi++){
      if(E[L[i]][T[wi]]!=E1[L1[s[i]]][T1[sT[wi]]]) return 0;
    }
  }
  for(i=1;i<=Dnum;i++){
    for(wi=1;wi<=Lnum;wi++){
      if(E[D[i]][L[wi]]!=E1[D1[sD[i]]][L1[s[wi]]]) return 0;
    }
    for(wi=1;wi<=Dnum;wi++){
      if(E[D[i]][D[wi]]!=E1[D1[sD[i]]][D1[sD[wi]]]&& i!=wi) return 0;
    }
    for(wi=1;wi<=DDnum;wi++){
      if(E[D[i]][DD[wi]]!=E1[D1[sD[i]]][DD1[sDD[wi]]]) return 0;
    }
    for(wi=1;wi<=Tnum;wi++){
      if(E[D[i]][T[wi]]!=E1[D1[sD[i]]][T1[sT[wi]]]) return 0;
    }
  }
  for(i=1;i<=DDnum;i++){
    for(wi=1;wi<=Lnum;wi++){
      if(E[DD[i]][L[wi]]!=E1[DD1[sDD[i]]][L1[s[wi]]]) return 0;
    }
    for(wi=1;wi<=Dnum;wi++){
      if(E[DD[i]][D[wi]]!=E1[DD1[sDD[i]]][D1[sD[wi]]]) return 0;
    }
    for(wi=1;wi<=DDnum;wi++){
      if(E[DD[i]][DD[wi]]!=E1[DD1[sDD[i]]][DD1[sDD[wi]]]&& i!=wi) return 0;
    }
    for(wi=1;wi<=Tnum;wi++){
      if(E[DD[i]][T[wi]]!=E1[DD1[sDD[i]]][T1[sT[wi]]]&& i!=wi) return 0;
    }
  }
  for(i=1;i<=Tnum;i++){
    for(wi=1;wi<=Lnum;wi++){
      if(E[T[i]][L[wi]]!=E1[T1[sT[i]]][L1[s[wi]]]&& i!=wi) return 0;
    }
    for(wi=1;wi<=Dnum;wi++){
      if(E[T[i]][D[wi]]!=E1[T1[sT[i]]][D1[sD[wi]]]) return 0;
    }
    for(wi=1;wi<=DDnum;wi++){
      if(E[T[i]][DD[wi]]!=E1[T1[sT[i]]][DD1[sDD[wi]]]) return 0;
    }
    for(wi=1;wi<=Tnum;wi++){
      if(E[T[i]][T[wi]]!=E1[T1[sT[i]]][T1[sT[wi]]]) return 0;
    }
  }
  return 1; //success
}
int check_data(void){
  int OK_flag=0;
  if(Lnum!=Lnum1){return 1;}
  if(Dnum!=Dnum1){return 1;}
  if(DDnum!=DDnum1){return 1;}
  if(Tnum!=Tnum1){return 1;}
  for(i=1;i<=Lnum;i++){s[i]=i;}
  for(i=1;i<=Dnum;i++){sD[i]=i;}
  for(i=1;i<=DDnum;i++){sDD[i]=i;}
  for(i=1;i<=Tnum;i++){sT[i]=i;}
  while(1){
    while(1){
      while(1){
	while(1){
	  if(check_this_data()){OK_flag=1;}
	  if(OK_flag==1) break;
	  if(next_T()==0) break;
	}
	if(OK_flag==1) break;
	if(next_DD()==0) break;
      }
      if(OK_flag==1) break;
      if(next_D()==0) break;
    }
    if(OK_flag==1) break;
    if(next_L()==0) break;
  }
  if(OK_flag==1) return 0;
  return 1;
}

int read_and_set_data(void){
  int wn,wk;
  int ret;
    wn=fgets(b,MAX_LINE,fpin);
    if(wn==0){return(0);}    
    switch(f_flag){
    case 0: // first
      if(b[0]=='#' || b[0]=='%'){
#if KNOOUT
      printf("%s",b);
#endif
      fprintf(fpout,"%s",b);
      }else{
	get_base_S1_data();
        fprintf(fpout,"%%%s",b);
#if KNOOUT
	printf("%%%s",b);
#endif
	f_flag=1;
      }
      break;
    case 1: // after one data
      if(b[0]=='#'|| b[0]=='%'){
#if KNOOUT
      printf("%s",b);
#endif
      fprintf(fpout,"%s",b);
      }else{
	get_S1_data();
	end_flag=1;
	if(check_data()){
#if KNOOUT
	  printf("%s",b);
#endif
	  fprintf(fpout,"%s",b);
	}
      }
      break;
    }
    return 1;
}

int main(int argc, char** argv) {
  char *infile,*outfile;

  if(argc==1){
    printf("Usage: %s S1DataFile [outfile]\n",argv[0]);
    return EXIT_FALSE;
  }
 // get file name
  infile=argv[1];
  if(argv[2]){outfile=argv[2];}else{outfile=OUTFILE;}
#if KNOOUT
  printf("infile[%s]outfile[%s]\n",infile,outfile);
#endif
  if((fpin=fopen(infile,"r"))==NULL){
    perror("fopen"); exit (EXIT_FALSE);}
  if((fpout=fopen(outfile,"w"))==NULL){
    perror("fopen"); exit (EXIT_FALSE);}

  f_flag=0;
  while(read_and_set_data()){}
  fclose(fpin);fclose(fpout);
  return (end_flag);
}