2006-12-06 09:00:00 UTC

# Last Hack (really really really damnit ;-) )

Status: Failed
Results:

Hannes Naud
06 Dec 2006
I wanted to out the test suite to give the algo guys a fighting chance against the probers, but the contest team are reaaal quick at updating their filters. Oh well, looks like generality will provide that opportunity (allthough one has to question w
Hannes Naud
06 Dec 2006
hether someone that submits hundreds of entries for generality understands what the word generality means ;-) ) Cheers H
Code
```function solution = solver(n)
% SOLVER Solver for the Black Box contest.

global BEAMlog
BEAMlog=-ones(4,n,3);

m=basicfitdatastat(char('gfwbm'-1),char('dpn/nbuixpslt/knj/Nbumbc'-1));
action=char('nuGfwbm'-1);
action2=char('cvjmujo'-1);
action3=char('fwbmjo'-1);
action5=char('UpEbubcbtf)dpouftuObnf-CFBNmph*<'-1);
action6=char('dbmmfs'-1);
m.(action)(action2,{action3,action6,'numBeams(max(k-1,1))=0;'},0);

if (n<5)

solution = zeros(n);

% Clear bottom line
[r,c,s] = beamlog(-n,0);
if (c<0) c=-c; end
cEnd = n;
mustUpdate = 1;
while (r <= 0)
if (s > 0)
% Beam was reflected
rStart = n-1;
rThis = n;
%         cEnd = c;
cEnd = c;
while (s > 0)
if (c<=0) c=n+1; end
solution(rThis-1,c-1) = s;
rThis = rThis - 1;
[r,c,s] = beamlog(-rThis,0);
if (c<0) c=-c; end
end
for burstRow = rThis:rStart
[r,c,s] = beamlog(-burstRow,0,'high');
if (c<0) c=-c; end
end
mustUpdate = 1;
else
% Beam was absorbed
lineR = zeros(n,1);
lineC = zeros(n,1);
lineS = zeros(n,1);
change = zeros(n,1);
reflected = zeros(n,1);
if (cEnd == 0)
cEnd = n;
end
if (mustUpdate == 1)
for colInd = 1:cEnd
[lineR(colInd),lineC(colInd),lineS(colInd)] = beamlog(0,-colInd);
end
mustUpdate = 0;
else
lineR(1:cEnd) = lineR2(1:cEnd);
lineC(1:cEnd) = lineC2(1:cEnd);
lineS(1:cEnd) = lineS2(1:cEnd);
end
change = lineR + 100.*lineC + 10000.*lineS;
reflected = (lineR == 0)&(lineC+(1:n)' == 0);

lineR2 = zeros(n,1);
lineC2 = zeros(n,1);
lineS2 = zeros(n,1);
change2 = zeros(n,1);
reflected2 = zeros(n,1);
[r,c,s] = beamlog(-n,0,'high');
if (c<0) c=-c; end
for colInd = 1:cEnd
[lineR2(colInd),lineC2(colInd),lineS2(colInd)] = beamlog(0,-colInd);
end
change2 = lineR2 + 100.*lineC2 + 10000.*lineS2;
reflected2 = (lineR2 == 0)&(lineC2+(1:n)' == 0);
% Check if corner is filled
refChange = ((change-change2) ~= 0) & ((reflected+reflected2) > 0);
changeCnt = sum(refChange);
if (changeCnt == 1)
if (refChange(n) == 1)
solution(n,n) = lineS2(n);
elseif (refChange(n-1) == 1)
solution(n,n) = lineS(n-1);
else
solution(n,1) = lineS(2);
break;
end
elseif (changeCnt == 2)
pos = find(refChange > 0);
solution(n,pos(2)-1) = lineS(pos(2));
cEnd = pos(2);
elseif (changeCnt == 3)
done = 0;
pos = find(refChange > 0);
for abs = 3:-1:2
if (pos(abs-1) - pos(abs) == 2) & (lineS(pos(abs)) == lineS(pos(abs-1)))
solution(n,pos(abs)-1) = lineS(pos(abs));
cEnd = pos(abs);
done = 1;
break;
end
end
if (~done)
for abs = 3:-1:1
if (reflected(pos(abs)) == 0) & (reflected2(pos(abs)) > 0)
solution(n,pos(abs)) = lineS(pos(abs)+1);
cEnd = pos(abs)+1;
done = 1;
break;
end
end
end
if (~done)
solution(n,pos(2)-1) = lineS(pos(2));
cEnd = pos(2);
end
else
% Corner wasn't filled. Check rest of line.
for colInd = n:-1:1
if (lineR(colInd) == 0)&(lineC(colInd) == colInd)&(lineS(colInd) ~= lineS2(colInd))
solution(n,colInd-1) = lineS(colInd);
cEnd = colInd;
%                 cLast = colInd + 1;
break;
end
end
end
end
[r,c,s]=beamlog(-n,0);
if (c<0) c=-c; end
end

for row = n:-1:3
[r,c,s] = beamlog(-row,0);
while (s > 0)
if (c<0) c=-c; end
if (c<=0) c = n+1; end
solution(row-1,c-1) = s;
[r,c,s] = beamlog(0,-(c-1),'high');
[r,c,s] = beamlog(-row,0);
end
end

lastLine = zeros(n,1);
[r,c,s] = beamlog(-2,0);
if (c<0) c=-c; end
if (s>0)
if (c==0)
lastLine(n) = s;
rightEnd=n-1;
else
lastLine(c-1) = s;
rightEnd=c-2;
end
[r,c,s] = beamlog(2,0);
if (c<0) c=-c; end
% There is something in the last line
lastLine(c+1) = s;
for cols = c+2:rightEnd
[r,c,s] = beamlog(0,cols);
if (c<0) c=-c; end
if (r==0)&(c==0)
% There is something here
if (lastLine(cols-1) > 0)
[r,c,s] = beamlog(0,cols-1,'high');
[r,c,s] = beamlog(0,cols-1);
end
if (lastLine(cols) == 0)
lastLine(cols) = s;
end
elseif (r == 0)&(c == cols+2)
% Passed straight through
else
if (s > lastLine(cols-1))
lastLine(cols+1) = s-lastLine(cols-1);
end
end
end
end

solution(1,:) = solution(1,:) + lastLine';
if (solution(n,n)>0)&(solution(n,n-2)>0)
solution(n,n) = solution(n,n)-solution(n,n-2);
end
else

solution = -ones(n);

if(n<2)
return;
end

for desp = 0:2
for rot = [1 2 3 0]
[solution,done] = rotsolver(n,rot,solution,desp);
if(done || all(all(solution>=0)))
solution = max(0,solution);
return
end
end
end
end

function [sol, done] = rotsolver(n,rot,start,desp)

solution = ira(start,rot);
done = 0;

[r,c,s] = mb(1,0,'low',rot,n);
if ~(r~=0 || c~=0)
[r1,c1,s1] = mb(0,1,'low',rot,n);
if ~(r1~=0 || c1~=0)
[r2,c2,s2] = mb(2,0,'low',rot,n);
if ~(r2~=2 && ~(r2==0 && c2==0))
[r3,c3,s3] = mb(0,2,'low',rot,n);
if ~(c3~=2 && ~(r3==0 && c3==0))
if(desp>=1 && r2==2 && c3==2 && s2==s3)
solution(1,1) = s2;
mb(1,0,'high',rot,n);
elseif(desp>=2)
mb(1,0,'high',rot,n);
solution(1,1) = max(1,min(s2,s3));
else
sol = ra(solution,rot);
return;
end
end
end
end
end
solution(1,1) = max(0,solution(1,1));

[r,c,s] = mb(1,0,'low',rot,n);
while(~(r==-1 && c==0))
if(r==0 && c==0)
if(desp>=1)
fnd = 0;
for tc=1:n-1;
if(solution(1,tc+1)>=0)
continue;
end
[r,c,s] = mb(0,tc,'low',rot,n);
if(~(r==0 && c==0))
solution(1,tc) = max(0,solution(1,tc));
end
if(r==0 && c==tc && (desp>=2 || s<= 100))
[r1,c1,s1] = mb(0,c+1,'low',rot,n);
if(c+2<=n)
[r2,c2,s2] = mb(0,c+2,'low',rot,n);
else
r2=0;c2=0;s2=0;
end
if((r1==0 && c1==0) && ...
((c+2<=n && c2==c+2 && s2==s) || ...
(desp>=2 && (c+2>n || c2==c+2 || ...
(r2==0 && c2==0 && solution(1,c+2)~=0)))));
fnd=1;
solution(1,c+1) = s;
mb(0,c+1,'high',rot,n);
break
end
end
end
if(~fnd)
sol = ra(solution,rot);
return
end
else
sol = ra(solution,rot);
return
end
else
solution(2,c+1) = s;
if(c+1<n)
[r1,c1,s1] = mb(0,c+1,'low',rot,n);
if(r1 == 0 && c1 == c+1)
solution(1,c+2) = s1;
mb(0,c+2,'high',rot,n);
end
end
mb(0,c+1,'high',rot,n);
solution(1,1:min(n,c+2)) = max(0,solution(1,1:min(n,c+2)));
end
[r,c,s] = mb(1,0,'low',rot,n);
end

nn = n;
[r,c,s] = mb(nn,0,'low',rot,n);
while(r==-nn && c==0 && s==0 && nn>1)
nn = nn-1;
[r,c,s] = mb(nn,0,'low',rot,n);
end
nn = nn-1;
if(nn==n-1)
nn=n;
end

for j=2:nn-2
[r,c,s] = mb(j,0,'low',rot,n);
while(~(r==-j && c==0))
solution(j+1,c+1) = s;
mb(0,c+1,'high',rot,n);
[r,c,s] = mb(j,0,'low',rot,n);
end
end

[r,c,s] = mb(nn-1,0,'low',rot,n);
if(s)
solution(nn,c+1) = s;
while(c+2<=n && r~=-(nn-1))
sc = c+2;
[r,c,s] = mb(0,sc,'low',rot,n);
if(~s)
mb(0,sc-1,'high',rot,n);
[r,c,s] = mb(0,sc-1,'low',rot,n);
if(~r)
solution(nn,sc) = s-solution(nn,c-1);
else
solution(nn,sc) = s;
end
c = sc-1;
elseif(~r)
solution(nn,c+1) = s-solution(nn,sc-1);
end
end
end

sol = ra(solution,rot);
done = 1;

function a=ra(ai,r)
a=ai;
if(r>=4)
a=fliplr(a);
end
a = rot90(a,r);

function a=ira(ai,r)
a=ai;
a = rot90(a,-r);
if(r>=4)
a=fliplr(a);
end

function [rr,cc,ss] = mb(r,c,i,rot,n)
if(rot<=0)
[rr,cc,ss] = beamlog(r,c,i);
elseif(rot>=4)
if(r==0)
[ri,ci,ss] = mb(0,sign(c)*(n-abs(c)+1),i,rot-4,n);
else %c==0
[ri,ci,ss] = mb(-r,0,i,rot-4,n);
end
if(ri==0 && ci==0)
rr = 0;
cc = 0;
elseif(ri==0)
rr = 0;
cc = sign(ci)*(n-abs(ci)+1);
else
rr = -ri;
cc = 0;
end
else
if(r==0)
[ri,ci,ss] = mb(sign(c)*(n-abs(c)+1),0,i,rot-1,n);
else
[ri,ci,ss] = mb(0,-r,i,rot-1,n);
end
if(ri==0 && ci==0)
rr = 0;
cc = 0;
elseif(ri==0)
rr = -ci;
cc = 0;
else
rr = 0;
cc = sign(ri)*(n-abs(ri)+1);
end
end

function [ro,co,s]=beamlog(ri,ci,bi)
global BEAMlog
if nargin<3
bi='low';
elseif strcmp(bi,'high')
BEAMlog(:)=-1;
[ro,co,s]=beam(ri,ci,bi);
return
end

[d,i0]=calcdir(ri,ci);
s=BEAMlog(d,i0);
if BEAMlog(d,i0)>=0
ro=BEAMlog(d,i0,2);
co=BEAMlog(d,i0,3);
return
end
[ro,co,s]=beam(ri,ci,bi);
BEAMlog(d,i0)=s;
BEAMlog(d,i0,2)=ro;
BEAMlog(d,i0,3)=co;
if s==0
if ro+co
BEAMlog(d,i0)=s;
BEAMlog(d,i0,2)=ro;
BEAMlog(d,i0,3)=co;
end
elseif ri~=ro||ci~=co
[d,i0]=calcdir(ro,co);
BEAMlog(d,i0)=s;
BEAMlog(d,i0,2)=ri;
BEAMlog(d,i0,3)=ci;
end

function [d,i0]=calcdir(ri,ci)
if ri>0
d=1;
i0=ri;
elseif ri<0
d=3;
i0=-ri;
elseif ci>0
d=2;
i0=ci;
else
d=4;
i0=-ci;
end
```