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

class RandomU32Generator
{
// Based on: http://my.opera.com/metrallik/blog/2013/04/19/c-class-for-random-generation-with-mersenne-twister-method
public:
    RandomU32Generator(unsigned long seed = 10){
        mt[0]=seed;
        for(unsigned long i=1;i<length;i++) mt[i]=(1812433253L*(mt[i-1]^(mt[i-1]>>30))+i)&bitMask_32;
        idx = 0;
    }
    unsigned long get()
    {
        if(idx==0) gen();
        unsigned long y=mt[idx];
        y^= y>>11;
        y^=(y<< 7)&2636928640L;
        y^=(y<<15)&4022730752L;
        y^= y>>18;
        idx=(idx+1)%length;
        return y&bitMask_32;
    }
    void gen()
    {
        for(int i=0;i<length;i++){
            unsigned long y=(mt[i]&bitPow_31)+(mt[(i+1)%length]&(bitPow_31-1));
            mt[i]=mt[(i+397)%length]^(y>>1);
            if(y%2) mt[i]^=2567483615L;
        }
        return;
    }
private:
    static const int length=624;
    static const unsigned long bitMask_32=0xffffffff;
    static const unsigned long bitPow_31=1L<<31;
    unsigned long mt[length];
    unsigned long idx;
};

class RandomBoolGenerator
{
public:
    RandomBoolGenerator() : _randomU32Generator(13), _i(0) { _r = _randomU32Generator.get(); }
    bool get()
    {
        if (++_i > 31)
        {
            _r = _randomU32Generator.get();
            _i = 0;
        }
        return ((_r >> _i) & 1) == 0;
        
    }
private:
    RandomU32Generator _randomU32Generator;
    int _i;
    unsigned long _r;
};

class BooleanMatrix
{
public:
    BooleanMatrix(int n, int m) : _n(n), _m(m)
    {
        _len = (_n * _m + 31)/32;
        _a = new unsigned long[_len];
        reset();
        
    }
    ~BooleanMatrix()
    {
        delete[] _a;
    }
    bool get(int i, int j) { unsigned long p = i + j*_n; return (_a[p/32] & ((unsigned long)1 << (p%32))) != 0; }
    void set(int i, int j) { unsigned long p = i + j*_n; _a[p/32] |= (unsigned long)1 << (p%32); }
    void reset(int i, int j) { unsigned long p = i + j*_n; _a[p/32] &= ~((unsigned long)1 << (p%32)); }
    void reset() { for (int i = 0; i < _len; i++) _a[i] = 0; }
private:
    int _n;
    int _m;
    unsigned long _len;
    unsigned long *_a;
};


int main(int argc, char* argv[])
{
    RandomBoolGenerator randomBoolGenerator;
        
    const int n = 10000;
    const int m = n;
    BooleanMatrix maze(n, m);
    BooleanMatrix visited(n, m);

    const int cn = n * 10;
    double counts[cn];
    double counts100[cn];
    for (int i = 0; i < cn; i++)
        counts[i] = counts100[i] = 0.0;
    double countinf = 0.0;
    double tries = 0.0;
    
    double factor = 100.0 / n / m;
    for (;;)
    {
        for (int t = 0; t < 1; t++)
        {
            maze.reset();
            visited.reset();
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (randomBoolGenerator.get())
                        maze.set(i, j);
                }
            }
        
            int count = 0;
            int max = 0;
            int total = 0;
            
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    if ((i+j)%2 == 1 && !visited.get(i, j))
                    {
                        int verr = 0;
                        int i1 = i;
                        int j1 = j;
                        int i2 = 0;
                        int j2 = 0;
                        char dir = 'd';
                        int len = 0;
                        for (;;)
                        {
                            if (dir == 'd')
                            {
                                visited.set(i1, j1);
                                i1++;
                                if (i1 == n)
                                {
                                    i1 = 0;
                                    i2++;
                                }
                                dir = maze.get(i1, j1) ? 'l' : 'r';
                            }
                            else // dir == 'u'
                            {
                                i1--;
                                if (i1 < 0)
                                {
                                    i1 = n-1;
                                    i2--;
                                }
                                dir = maze.get(i1, j1) ? 'r' : 'l';
                            }
                            
                            if (dir == 'r')
                            {
                                j1++;
                                if (j1 == m)
                                {
                                    j1 = 0;
                                    j2++;
                                }
                                dir = maze.get(i1, j1) ? 'u' : 'd';
                            }
                            else // dir == 'l'
                            {
                                j1--;
                                if (j1 < 0)
                                {
                                    j1 = m-1;
                                    j2--;
                                }
                                dir = maze.get(i1, j1) ? 'd' : 'u';
                            }
                            
                            len++;
    
                            if (i1 == i && j1 == j && dir == 'd')
                                break;
                        }
                        
                        count++;
                        total += len;
                        if (len > max)
                            max = len;
    
                        int lend2 = len/2;
                        if (i2 != 0 || j2 != 0)
                            countinf += factor * len;
                        else if (lend2 < cn)
                        {
                            counts[lend2] += factor * len;
                        }
                        else
                        {
                            lend2 = (lend2 - cn) / 100;
                            if (lend2 < cn)
                                counts100[lend2] += factor * len;
                        }
                    }
            tries += 1;
        }
        fprintf(stderr, "Tried: %10.0lf\n", tries);
        
        FILE *fout = fopen("diagmazecount.txt","wt");
        
        double cum = 0.0;
        for (int i = 1; i < cn; i++)
        {
            cum += counts[i]/tries;
            fprintf(fout, "%8d = %14.10lf %15.11lf", 2*i, counts[i]/tries, cum);
            if (i % 2 == 0 && counts[i/2] > 0.00001)
                fprintf(fout, " %lf", counts[i]/counts[i/2]);
            fprintf(fout, "\n");
        }
        for (int i = 0; i < cn; i++)
        {
            cum += counts100[i]/tries;
            fprintf(fout, "%8d = %14.10lf %15.11lf\n", 2*(cn + i * 100), counts100[i]/tries, cum);
        }
        cum += countinf/tries;
        fprintf(fout, "inf      = %14.10lf %15.11lf\n", countinf/tries, cum);
        fprintf(fout, "\n");
        
        double prevvalue = 0;
        double prevdiff = 0;
        
        int p = 1;
        double value = 0;
        for (int i = 1; i < cn; i++)
        {
            value += counts[i]/tries;
            if (i == p)
            {
                fprintf(fout, "%6d: %10f", i, value);
                double diff = value - prevvalue;
                prevvalue = value;
                if (i > 1)
                {
                    fprintf(fout, " %10f", diff);
                    if (i > 2)
                    {
                        double factor = diff / prevdiff;
                        fprintf(fout, " %10f", factor);
                        if (factor < 1.0)
                        {
                            double end = value + factor * diff / (1 - factor);
                            fprintf(fout, " %10f", end);
                        }
                    }
                }
                fprintf(fout, "\n");
                prevdiff = diff;
                p *= 2;
            }
        }
        
        fclose(fout);
    }
            
    return 0;
}