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


const int K = 20;
const int N = K+15;

void randseed();
void packets(int M[N][K]);
void pr(int M[N][K]);
int po(int x, int y);
int independent(int M[N][K], int i);
int recv(int M[N][K]);
double rate(int T, int suc[N+1]);


main()
{
  randseed();

  int suc[N+1];
  int T=1000;

  double S;
  S=rate(T,suc);
  printf("S=%f\r\n",S);

  for(int i=K;i<=N;i++)
    printf("%2d, %f\r\n",i-K,(double)suc[i]/T);

}

double rate(int T, int suc[N+1])
{
  int M[N][K];
  for(int i=0;i<=N;i++)
    suc[i]=0;
  for(int t=0;t<T;t++)
  {
    printf("t=%d\n",t);
    packets(M);
    int n=recv(M);
    for(int i=n;i<=N;i++)
      suc[i]++;
  }
  double S;
  for(int i=0;i<=N;i++)
    S+=(double)suc[i]/T;
  return S;
}

int recv(int M[N][K])
{
  //we could remove the dependent rows from the matrix to speedup the checking
  int r=0;
  int i=0;
  for(;i<N && r<K;i++)
  {
    if(independent(M,i))
      r++;
  }
  return i;
}

int independent(int M[N][K], int i)
{
  int S = po(2,i);
  for(int s=0;s<S;s++)  //all subsets of previous rows
  {
    int ok=0;
    for(int k=0;k<K;k++)
    {
      int a=M[i][k];
      for(int j=0;j<i;j++)
        if(s>>j&1)
          a^=M[j][k];
      if(a)
      {
        ok=1;
        break;
      }
    }
    if(!ok)
      return 0;
  }
  return 1;
}

int po(int x, int y)
{
  int r=1;
  for(int i=0;i<y;i++)
    r*=x;
  return r;
}

void pr(int M[N][K])
{
  printf("M[%d][%d]=\r\n",K,N);
  for(int i=0;i<N;i++)
  {
    printf("%3d:",i);
    for(int j=0;j<K;j++)
      printf("%2d",M[i][j]);
    printf(" %s\r\n",independent(M,i)?"indep":"-");
  }
}

void packets(int M[N][K])
{
  for(int i=0;i<N;i++)
    for(int j=0;j<K;j++)
      M[i][j]=rand()%2;
}

void randseed()
{
  int ti=time(0);
  printf("srand=%d\r\n",ti);
  srand(ti);
}