2×2 Squares on a Randomly Filled m×n Board

June 28, 2010 at 17:03 (algorithm, java, math.PR)

This post, like the last one, is an offshoot of a thread on Math Help Forum. The situation is: Suppose there is an m×n chess-like board and we wish to fill in all the (1×1) squares according to: all squares are either black or white, and the probability that a square is black is p . What is the probability that a randomly filled board will contain at least one 2×2 black square?

Here is my solution, which is relatively fast up to about \min(m,n)=12 . I’m still investigating a few potential issues. The code is undocumented and not written for legibility; I’m going for the “magical” look. :-) Although there is some discussion of its inner workings on the MHF thread.

I think solve() could be optimised somewhat by calling g() within the main loop, but I’m more concerned about other issues at the moment. Since this algorithm has limitations, I’m curious as to how a more scalable algorithm might look.

import java.util.Random;

public class ChessBlackSquare22 {
    static boolean testMode=false,fMemo[][],fMemoV[][],gMemo[],gMemoV[];
    static Random g=new Random();
    static double g1,p,hMemo[];
    static int m,n,n2,memLim,L1=13,L2=16;
    
    public static void main(String[] args) {
        //monteCarlo(0.05,4,4);
        //brute(0.05,4,4);
        solve(0.05,8,8);
    }
    
    static void solve(double p1,int m1,int n1) {
        long t=time();
        int i,j,k;
        double q,r[],s[],x=0,x2,x3,y=1,z;
        p=p1;
        m=m1;
        n=n1;
        if(m<2||n<2) return;
        if(!testMode&&m<n) {
            i=m;
            m=n;
            n=i;
        }
        if(n>L2) return;
        n2=(int)pow(2,n);
        memLim=Math.min((int)pow(2,L1),n2);
        fMemoV=new boolean[memLim][memLim];
        fMemo=new boolean[memLim][memLim];
        gMemoV=new boolean[n2];
        gMemo=new boolean[n2];
        hMemo=new double[n2];
        r=initR();
        for(i=1;i<m;i++) {
            s=new double[n2];
            x2=0;
            for(j=0;j<n2;j++) {
                z=r[j];
                for(k=0;k<n2;k++) {
                    q=z*h(k);
                    if(f(j,k)) x2+=q;
                    else s[k]+=q;
                }
            }
            x3=1-x2;
            for(j=0;j<n2;j++)
                s[j]/=x3;
            x+=y*x2;
            y*=x3;
            r=s;
        }
        System.out.println(x);
        System.out.println("Elapsed: "+(time()-t)/1000.0+" s");
    }
    
    static boolean f(int x,int y) {
        if(x<memLim&&y<memLim&&fMemoV[x][y]) return fMemo[x][y];
        boolean b=false,u[]=toRow(x),v[]=toRow(y);
        int i;
        for(i=1;i<n;i++)
            if(u[i]&&v[i]&&u[i-1]&&v[i-1]) {
                b=true;
                break;
            }
        if(x<memLim&&y<memLim) {
            fMemoV[x][y]=true;
            fMemo[x][y]=b;
        }
        return b;
    }
    
    static boolean g(int x) {
        if(gMemoV[x]) return gMemo[x];
        boolean r[]=toRow(x),b=false;
        int i;
        for(i=1;i<n;i++)
            if(r[i]&&r[i-1]) {
                b=true;
                break;
            }
        gMemoV[x]=true;
        return gMemo[x]=b;
    }
    
    static double h(int x) {
        if(hMemo[x]!=0) return hMemo[x];
        int i,j;
        double q=1;
        for(i=n-1,j=x;i>=0;i--,j/=2)
            q*=(j%2==1)?p:1-p;
        return hMemo[x]=q;
    }
    
    static double[] initR() {
        int i;
        double r[]=new double[n2];
        for(i=0;i<n2;i++)
            r[i]=h(i);
        return r;
    }
    
    static boolean[] toRow(int x) {
        boolean[] r=new boolean[n];
        int i;
        for(i=n-1;i>=0;i--,x/=2)
            r[i]=x%2==1;
        return r;
    }
    
    static void brute(double p1,int m1,int n1) {
        long t=time();
        p=p1;
        m=m1;
        n=n1;
        if(m*n>25||m<2||n<2) return;
        g1=0;
        brute2(0,0,1,new boolean[m][n]);
        System.out.println(g1);
        System.out.println("Elapsed: "+(time()-t)/1000.0+" s");
    }
    
    static void brute2(int a,int b,double q,boolean[][] z) {
        int i,j,a2,b2;
        boolean[][] y;
        if(a==m) {
            outer:
            for(i=0;i<m-1;i++)
            for(j=0;j<n-1;j++)
                if(z[i][j]&&z[i][j+1]&&z[i+1][j]&&z[i+1][j+1]) {
                    g1+=q;
                    break outer;
                }
            return;
        }
        a2=(b<n-1)?a:a+1;
        b2=(b<n-1)?b+1:0;
        brute2(a2,b2,q*(1-p),deepcopy(z));
        y=deepcopy(z);
        y[a][b]=true;
        brute2(a2,b2,q*p,y);
    }
    
    static void monteCarlo(double p,int m,int n) {
        if(m<2||n<2) return;
        long t1=time(),t2=t1,s=0,t;
        int i,j;
        boolean b,c[][];
        for(t=0;;t++) {
            if(time()-t2>=1000) {
                System.out.println("T: "+fill(t,15)+"P: "+
                        fill(s/(double)t,22)+"E: "+(time()-t1)/1000.0);
                t2=time();
            }
            b=false;
            c=new boolean[m][n];
            for(i=0;i<m;i++)
            for(j=0;j<n;j++)
                if(g.nextFloat()<p) c[i][j]=true;
            outer:
            for(i=1;i<m;i++)
            for(j=1;j<n;j++)
                if(c[i][j]&&c[i][j-1]&&c[i-1][j]&&c[i-1][j-1]) {
                    b=true;
                    break outer;
                }
            if(b) s++;
        }
    }
    
    static boolean[][] deepcopy(boolean[][] a) {
        int i;
        boolean[][] b=new boolean[a.length][];
        for(i=0;i<a.length;i++)
            b[i]=a[i].clone();
        return b;
    }
    
    static long pow(int a,int b) {
        int i;
        long c=1;
        for(i=0;i<b;i++)
            c*=a;
        return c;
    }
    
    static String fill(double a,int x) {
        return fill(Double.toString(a),x);
    }
    
    static String fill(long a,int x) {
        return fill(Long.toString(a),x);
    }
    
    static String fill(String s,int x) {
        if(s.length()>=x) return s;
        return fill(s+" ",x);
    }
    
    static long time() {
        return System.currentTimeMillis();
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: