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


struct Edge
{
  int i;
  int j;
};

void pr(int G[9][9], int m[9], int Rx[9][9], char* fname);
void initG(int G[9][9]);
void G2E(int G[9][9], Edge E[18]);
int newp(int p[27], int n);
void set(int m[9], int e[18], int pa);
void init(int p[27], int m[9], int e[18]);
void E2G(int e[18], Edge E[18], int R[9][9]);
void explore(int i, int m[9], int R[9][9]);
int ck(int m[9], int R[9][9]);
void reset(int p[27], int m[9]);
void rateG(int G[9][9], int suc[28], int N, int print_flag);

main()
{
  int ti=time(0);
  //ti=1140087970;
  printf("srand=%d\n",ti);
  srand(ti);

  const int gn = 100;
  const int N = 20000;

  int G[9][9];

  int suc[28];

  int charts[gn][28];

  double maxS=0;

  for(int i=0;i<gn;i++)
  {
    initG(G);
    rateG(G,suc,N,0);

    for(int j=0;j<28;j++)
      charts[i][j]=suc[j];

    double S=0;
    for(int j=0;j<28;j++)
      S+=(double)suc[j]/N;
    printf("%2d %f\r\n",i,S);
    if(S>maxS)
    {
      maxS=S;
      rateG(G,suc,N,1);
      printf("saving the graph\r\n");     
    }

  }

  FILE *f;
  f=fopen("out.csv","w");
  fprintf(f,",P\r\n");
  for(int i=0;i<gn;i++)
  {
    for(int j=9;j<28;j++)
    {
      fprintf(f,"%d,%.10f\r\n",j,(double)charts[i][j]/N);
    }
    fprintf(f,"\r\n");
  }
  fclose(f);
}


void rateG(int G[9][9], int suc[28], int N, int print_flag)
{
  Edge E[18];
  G2E(G,E);

  int p[27];
  int m[9];
  int e[18];

  int R[9][9];

  //const int print_flag = 0;

  if(print_flag)
  {
    system("rm *.eps");
    N=1;
  }

  char fname[100];


  for(int i=0;i<=27;i++) suc[i]=0;

  for(int t=0;t<N;t++)
  {
    init(p,m,e);
  
    int n;
  
    for(n=1;n<=8;n++)
    {
      set(m,e,newp(p,n));
    }

    for(n=9;n<=27;n++)
    {
      set(m,e,newp(p,n));

      E2G(e,E,R);  

      if(print_flag)
      {
        sprintf(fname,"out%da.eps",n);
        pr(G,m,R,fname);  
      }
      int recov=ck(m,R);
      if(print_flag)
      {
        sprintf(fname,"out%db.eps",n);
        pr(G,m,R,fname);
      }

      if(recov)
        break;

      reset(p,m);
    }

    for(int i=n;i<=27;i++)
    {
      suc[i]++;
    }

  }


}


void reset(int p[27], int m[9])
{
  for(int i=0;i<9;i++)
  {
    m[i] = 0;
  }
  for(int pa=0;pa<9;pa++)
    if(p[pa])
      m[pa]=1;
}

void explore(int i, int m[9], int R[9][9])
{
  for(int j=0;j<9;j++)
    if(R[i][j])
      if(!m[j])
      {
        m[j]=1;
        explore(j,m,R);
      }
}

int ck(int m[9], int R[9][9])
{
  for(int i=0;i<9;i++)
    if(m[i])
      explore(i,m,R);

  for(int i=0;i<9;i++)
    if(!m[i])
      return 0;
  return 1;
}

void E2G(int e[18], Edge E[18], int R[9][9])
{
  for(int i=0;i<9;i++)
    for(int j=0;j<9;j++)
      R[i][j]=0;

  for(int k=0;k<18;k++)
    if(e[k])
    {
      R[E[k].i][E[k].j]=1;
      R[E[k].j][E[k].i]=1;
    }
}

void init(int p[27], int m[9], int e[18])
{
  for(int i=0;i<27;i++)
    p[i]=0;
  for(int i=0;i<9;i++)
    m[i] = 0;
  for(int i=0;i<18;i++)
    e[i] = 0;
}

void set(int m[9], int e[18], int pa)
{
  if(pa<9)
    m[pa]=1;
  else
    e[pa-9]=1;
}

int newp(int p[27], int n)
{
  int i = rand()%(27-n+1);
  int j = -1;
  for(;i>=0;i--)
  {
    j++;
    for(;p[j];j++)
      ;
  }
  p[j]=1;
  return j;
}

void G2E(int G[9][9], Edge E[18])
{
  int k=0;
  for(int i=0;i<9-1;i++)
    for(int j=i+1;j<9;j++)
      if(G[i][j])
      {
        E[k].i=i;
        E[k].j=j;
        k++;
      }
}

void initG(int G[9][9])
{
  int g[36];

  for(int i=0;i<36;i++)
    g[i] = 0;

  for(int i=0;i<9;i++)
    for(int j=0;j<9;j++)
      G[i][j]=0;

  for(int n=1; n<=18; n++) //adding 18 random edges
  {
    int i = rand()%(36-n+1);
    int j = -1;
    for(;i>=0;i--)
    {
      j++;
      for(;g[j];j++)
        ;
    }
    g[j]=1;
  }

  for(int k=0;k<36;k++)
    if(g[k])
    {
      int n=k;
      for(int i=0;i<9-1 && n>-1;i++)
        for(int j=i+1;j<9 && n>-1;j++,n--)
        {
          if(n==0)
          {
            G[i][j]=1;
            G[j][i]=1;
          }
        }
    }
}

void pr(int G[9][9], int m[9], int Rx[9][9], char* fname)
{
  const int R = 70;
  const int r = 7;
  const int margin = 1;

  double x[9];
  double y[9];

  for(int i=0;i<9;i++)
  {
    double a=2*M_PI*i/9;
    x[i]=R*cos(a);
    y[i]=R*sin(a);
  }
  
  FILE *f;
  f=fopen(fname,"w");
  fprintf(f,"%%!PS-Adobe-3.0 EPSF-3.0\r\n");
  fprintf(f,"%%%%BoundingBox: 0 0 %d %d\r\n",2*(R+r+margin),2*(R+r+margin));
  fprintf(f,"%d %d translate\r\n",R+r+margin,R+r+margin);
  fprintf(f,"0 setlinecap\r\n");
  fprintf(f,"1 setlinewidth\r\n");
  fprintf(f,"[1.5 3] 0 setdash\r\n");
  for(int i=0;i<9-1;i++)
    for(int j=i+1;j<9;j++)
      if(G[i][j])
      {
        fprintf(f,"%f %f moveto %f %f lineto stroke\r\n",x[i],y[i],x[j],y[j]);   
      }
  fprintf(f,"3 setlinewidth\r\n");
  fprintf(f,"[] 0 setdash\r\n");
  for(int i=0;i<9-1;i++)
    for(int j=i+1;j<9;j++)
      if(Rx[i][j])
      {
        fprintf(f,"%f %f moveto %f %f lineto stroke\r\n",x[i],y[i],x[j],y[j]);   
      }
  fprintf(f,"1 setlinewidth\r\n");
  fprintf(f,"[1.5 3] 0 setdash\r\n");
  fprintf(f,"1 setgray\r\n");
  for(int i=0;i<9;i++)
  {
    fprintf(f,"newpath %f %f %d 0 360 arc fill\r\n",x[i],y[i],r);   
  }
  fprintf(f,"0 setgray\r\n");
  for(int i=0;i<9;i++)
  {
    fprintf(f,"newpath %f %f %d 0 360 arc stroke\r\n",x[i],y[i],r);   
  }
  fprintf(f,"3 setlinewidth\r\n");
  fprintf(f,"[] 0 setdash\r\n");
  for(int i=0;i<9;i++)
    if(m[i])
    {
      fprintf(f,"newpath %f %f %d 0 360 arc stroke\r\n",x[i],y[i],r);   
    }
  fprintf(f,"1 setlinewidth\r\n");
  fprintf(f,"[1.5 3] 0 setdash\r\n");
  fprintf(f,"showpage\r\n");   
  fclose(f);

}