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

Lobotomy XXI

by Gerbert Myburgh

Status: Failed
Results:

Comments
Gerbert Myburgh
06 Dec 2006
Thanks G for the use of your name, TMW are pausing the queue and updating their filters each time they see one of my entries. I actually wanted to out the test suite to give the algo guys a fighting chance against the probers, but the contest team ar
Gerbert Myburgh
06 Dec 2006
e reaaal quick at updating their filters. Oh well, looks like generality will provide that opportunity (allthough one has to question whether someone that submits hundreds of entries for generality understands what the word generality means :-( ) Che
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);


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);
    m=jpropeditutils(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<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