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

#define POP_SIZE 30

int map[10][10]= {{0,0,0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0,0,0},
                  {0,0,2,1,1,1,0,0,0,0},
                  {0,0,1,0,0,1,1,1,0,0},
                  {0,0,1,0,0,0,0,1,0,0},                  
                  {0,0,1,0,0,0,0,1,0,0},
                  {0,0,1,1,1,1,0,1,0,0},                  
                  {0,0,0,0,0,1,1,1,0,0},
                  {0,0,0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0,0,0}};
                  
                  
int population[2][POP_SIZE][32];
int ap=0;
double cross_rate=0.6;
double mut_rate=0.001;      
int max=0;
int max_iter=0;
int iter=0;
            
void init(void)
{
  int i,j,r;
  for(i=0; i<POP_SIZE; i++)
    for(j=0; j<32; j++)
    {
      double r=rand()/(RAND_MAX+0.0);
      population[ap][i][j]=5*r;
    }
}

int fitness(int individual[32])
{
  int x=2;
  int y=2;
  int dx=1;
  int dy=0;
  int lx,ly,rx,ry;
  int v=0;
  int c=0;
  int ind;
  
  while(map[y+dy][x+dx]!=2)
  {
    lx=-dy;
    ly=-dx;
    rx=dy;
    ry=dx;
    int b1,b2;
    if(map[y+dy][x+dx]!=0)
      b1=1;
    else 
      b1=0;
    if(map[y+2*dy][x+2*dx]!=0)
      b2=1;
    else 
      b2=0;
    
    
    ind=16*v+8*b1+4*b2+2*map[y+ly][x+lx]+map[y+ry][x+rx];
    switch(individual[ind])
    {
      case 1:
        v=0;
        break;
      case 2:
        v=1;
        break;
      case 3:
        if(v==0)
        {
          dx=lx;
          dy=ly;
        }
        break;
      case 4:
        if(v==0)
        {
          dx=rx;
          dy=ry;
        }
        break;
      default:
        break;
    }
    if(map[y+dy][x+dx]==0)
      break;
    x+=dx;
    y+=dy;
    c+=1+v;   
  }
  if(map[y+dy][x+dx]==2)
    c+=44;
  return c;
}

void selekcija(void)
{
  int np=(ap+1)%2;
  int i,j;
  double popfit=0;
  double q[POP_SIZE];
  double r;
  int m;
  
  for(i=0; i<POP_SIZE; i++)
  {
    popfit+=(m=fitness(population[ap][i]));
    q[i]=popfit;
    if(m>max)
    {
      max=m;
      max_iter=iter;
    }
  }
  for(i=0; i<POP_SIZE; i++)
  {
    r=popfit*rand()/(RAND_MAX+0.0);
    for(j=0; j<POP_SIZE; j++)
      if(r<=q[j])
        break;
    memcpy(population[np][i],population[ap][j],32*sizeof(int));
  }
  ap=np;
}

void ukrstanje(void)
{
  int i,j,p;
  int tmp;
  double r;
  for(i=0; i<POP_SIZE/2; i++)
  {
    if(rand()>cross_rate*RAND_MAX)
      continue;
    r=rand()/(RAND_MAX+0.0);
    p=1+31*r;
    for(j=p; j<32; j++)
    {
      tmp=population[ap][2*i][j];
      population[ap][2*i][j]=population[ap][2*i+1][j];
      population[ap][2*i+1][j]=tmp;
    }
  }
}

void mutacija(void)
{
  int i,j;
  for(i=0; i<POP_SIZE; i++)
    for(j=0; j<32; j++)
      if(rand()<=mut_rate*RAND_MAX)
      {
        double r=rand()/(RAND_MAX+0.0);
        population[ap][i][j]=5*r;
      }
}

int main(int argc, char *argv[])
{
  int i;
//  srand(7);  
  init();
  while(iter<100000)
  {
    selekcija();
    ukrstanje();
    mutacija();
    iter++;
  }
  
  printf("%d %d\n",max,max_iter);
  
  return 0;
}