Finish 2006-12-06 09:00:00 UTC

Last Hack (really ;-) )

by Hannes Naud

Status: Failed
Results:

Comments
Hannes Naud
06 Dec 2006
I wanted to out the test suite and give the algo guys a fighting chance against the probers but TMW are just too quick at patching up their defences. Done for now. Enjoy the rest and see ya in 6 months.
Please login or create a profile.
Code
function solution = solver(n)
% SOLVER Solver for the Black Box contest.

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

m=graph2dhelper(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);
m2=m();
m2.(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