Open
Description
Johan Engelen asked me to provide the following program as a testcase, because on my computer gdc is about 10% faster on this than ldc.
> gdc -O3 -fomit-frame-pointer -fweb -frelease -finline-functions test.d -o test
> ./test
> 281
> ldc2 -O3 -release test.d
> ./test
> 310
import std.stdio;
import std.datetime;
int X;
int[][] problem;
int[][] attempt;
int[] fullx;
int[] emptyx;
int[] fully;
int[] emptyy;
int count;
void main()
{
int i,j;
X = 10;
problem = new int[][](X,X);
for (i=0;i<X;i++)
for (j=0;j<X;j++)
problem[i][j] = -1;
problem[1][8] = 4;
problem[5][5] = 1;
solve();
}
void solve()
{
int i,j;
attempt = new int[][](X,X);
fullx = new int[](X);
emptyx = new int[](X);
fully = new int[](X);
emptyy = new int[](X);
auto start = Clock.currStdTime()/10000;
searchSolutionAt(0);
auto stop = Clock.currStdTime()/10000;
writeln(stop-start);
}
void searchSolutionAt(int n)
{
if (n==X*X) count++;
if (n==X*X) return;
int x = n%X;
int y = n/X;
attempt[x][y] = 1;
fullx[x]++;
fully[y]++;
if (solvable(x,y))
{
searchSolutionAt(n+1);
if (count>=2) return;
}
fullx[x]--;
fully[y]--;
attempt[x][y] = 2;
emptyx[x]++;
emptyy[y]++;
if (solvable(x,y))
{
searchSolutionAt(n+1);
if (count>=2) return;
}
emptyx[x]--;
emptyy[y]--;
attempt[x][y] = 0;
}
int solvable(int x, int y)
{
int i,j,ii,jj;
if (problem[x][y]!=-1 && attempt[x][y]==1) return 0;
if (attempt[x][y]==1)
{
if (x>0 && attempt[x-1][y]==1) return 0;
if (y>0 && attempt[x][y-1]==1) return 0;
if (x>0 && y>0 && attempt[x-1][y-1]==1) return 0;
if (x<X-1 && y>0 && attempt[x+1][y-1]==1) return 0;
}
if (fullx[x]>2 || X-emptyx[x]<2) return 0;
if (fully[y]>2 || X-emptyy[y]<2) return 0;
for (i=x-1;i<=x+1;i++)
for (j=y-1;j<=y+1;j++)
if (i>=0 && i<X && j>=0 && j<X)
if (problem[i][j]>=0)
{
int az = 0;
int nullaz = 0;
for (ii=-1;ii<=1;ii++)
for (jj=-1;jj<=1;jj++)
if (ii!=0 || jj!=0)
if (ii+i>=0 && ii+i<X && jj+j>=0 && jj+j<X)
{
if (attempt[ii+i][jj+j]==1) az++;
if (attempt[ii+i][jj+j]==0) nullaz++;
}
if (az>problem[i][j] || az+nullaz<problem[i][j]) return 0;
}
return 1;
}