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

seek_n_destroy_generality_7b

by Rajiv Narayan

Status: Passed
Results: 24263.7
CPU Time: 19.2991
Score: 242.648
Submitted at: 2006-12-06 15:13:02 UTC
Scored at: 2006-12-06 15:30:30 UTC

Current Rank: 3240th

Comments
Rajiv Narayan
06 Dec 2006
Slight strategy change
Please login or create a profile.
Code
function solution = solver(n)
global h solution 
solution = zeros(n);
h=ones(4,n,3)*-1;
cm=zeros(n);
nenter = 4*n;
enter=zeros(nenter,2);
r=(1:n)';
signr=[0,-1,0,1];
signc=[-1,0,1,0];
cw=[4,1,2,3,4,1];
for ii=1:4;
  enter([1:n]+(ii-1)*n,:)=([r*signr(ii),r*signc(ii)]);
end
ed(1,:) = (n-1)+[1:n:n^2-n+1];
ed(2,:) = [1:n]+(n^2-n);
ed(3,:) = [1:n:n^2-n+1];
ed(4,:) = [1:n];
sgn = [-1, -1 , 1, 1];
for pass=1:2
    for ii=1:nenter
        mir = abs(enter(ii,1))+n*(enter(ii,2)<0)+(enter(ii,2)>0);
        mic = abs(enter(ii,2))+n*(enter(ii,1)<0)+(enter(ii,1)>0);
        inface = whichface(enter(ii,1),enter(ii,2));
        inpos = abs(enter(ii,1)+enter(ii,2));
        if (isequal(pass,1)) check = ~cm(mir,mic); else check = isequal(solution(mir,mic),0);end
        if (check)
            [or,oc,os] = flash(inpos,inface);
            outface = whichface(or,oc);
            outpos=abs(or+oc);
            if (outface)
                mor = abs(or)+n*(oc<0)+(oc>0);
                moc = abs(oc)+n*(or<0)+(or>0);
                solution(mor,moc)=0;
                solution(mir,mic)=0;
                cm(mor,moc)=1;
                cm(mir,mic)=1;
                h(outface, abs(or+oc), :) = [enter(ii,:), os];
                switch(abs(inface-outface))
                    case 0
                        if ((mor-mir) || (moc-mic))
                        else
                            x=abs(or+oc);
                            if (isequal(x,1) || isequal(x,n))
                                x=x+[1 -1];
                                x=(x(x>0 & x<n));
                                y=1+(n-1)*(inface<3);
                                if (or)
                                    solution(x,y)=os;
                                    cm(x,y)=1;
                                else
                                    solution(y,x)=os;
                                    cm(y,x)=1;
                                end
                            else
                                x=x+[1 -1];
                                y=(1+(n-1)*(inface<3))*[1 1];
                                if (mod(inface,2))
                                    X=[y;x];
                                else
                                    X=[x;y];
                                end
                                for jj=1:2
                                    if (isequal(cm(X(1,jj),X(2,jj)),0))
                                        [tor,toc,v ] = flash(x(jj),inface);
                                        tos(jj) = v;
                                    else
                                        tos(jj) = solution(X(1,jj),X(2,jj));
                                    end
                                end
                                isvalid=any(tos);
                                if (isvalid)
                                    if (solution(X(1,1),X(2,1))>0)
                                        solution(X(1,2),X(2,2))=os-tos(1);
                                        cm(X(1,2),X(2,2)) = 1;
                                    elseif (solution(X(1,2),X(2,2))>0 )
                                        solution(X(1,1),X(2,1))= os - tos(2);
                                        cm(X(1,1),X(2,1)) = 1;
                                    else
                                    end
                                end
                            end
                        end
                    case 2
                        if isequal(enter(ii,1)+or+enter(ii,2)+oc+os,0)
                            p=abs(or+oc);
                            d = mod(outface,2)>0;
                            r = sort([mir,mor]);
                            c = sort([mic,moc]);
                            if (d)
                                rrng = r(1):r(2);
                                crng = [c(1)-1*(c(1)>1):c(1)+1*(c(1)<n)];
                            else
                                rrng = [r(1)-1*(r(1)>1):r(1)+1*(r(1)<n)];
                                crng = c(1):c(2);
                            end
                            for ri =rrng
                                for ci=crng
                                    solution(ri,ci)= 0;
                                    cm(ri,ci)=1;
                                end
                            end
                        else
                        end
                    otherwise
                        inr = [-1, 0, 1, 0];
                        inc = [ 0, -1, 0,1];
                        objr=abs(enter(ii,1)+or) + inr(inface)+inr(outface);
                        objc=abs(enter(ii,2)+oc) + inc(inface)+inc(outface);
                        solution(objr,objc)=os;
                        do = mod(outface,2)>0;
                        di = mod(inface,2)>0;
                        if (di)
                            if (mir-1>0 )
                                if (~solution(mir-1,mic))
                                    solution(mir-1,mic)= 0;
                                    cm(mir-1,mic) = 1;
                                end
                            end
                            if (mir+1 < n+1)
                                if (~solution(mir+1,mic))
                                    solution(mir+1,mic)=0;
                                    cm(mir+1,mic) = 1;
                                end
                            end
                        else
                            if (mic-1>0)
                                if (~solution(mir,mic-1))
                                    solution(mir,mic-1)= 0;
                                    cm(mir,mic-1) = 1;
                                end
                            end
                            if (mic+1 < n+1)
                                if (~solution(mir,mic+1))
                                    solution(mir,mic+1)= 0;
                                    cm(mir,mic+1) = 1;
                                end
                            end
                        end
                        if (do)
                            if (mor-1>0)
                                solution(mor-1,moc)= 0;
                                cm(mor-1,moc) = 1;
                            end
                            if (mor+1 < n+1)
                                solution(mor+1,moc)=0;
                                cm(mor+1,moc) = 1;
                            end
                        else
                            if (moc-1>0)
                                solution(mor,moc-1)= 0;
                                cm(mor,moc-1) = 1;
                            end
                            if (moc+1 < n+1)
                                solution(mor,moc+1)= 0;
                                cm(mor,moc+1) = 1;
                            end
                        end
                end
            else
                pos=abs(enter(ii,1)+enter(ii,2));
                if (mod(pos,n) <2)
                    pface = perp_beam(pos,inface);
                    spos = 2+(n-3)*(pface<3);
                    ppos = 2+(n-3)*(inface<3);
                    [mi,mj] = pos2ij(spos,inface,n);
                    [mpi,mpj] = pos2ij(ppos,pface,n);
                    if ( isequal(cm(mi,mj) + cm(mpi,mpj),2) && isequal(h(inface,spos,3),h(pface,ppos,3)))                                            
                        [oi,oj] = pos2ij(pos,inface,n);
                        solution(oi,oj)=h(inface,spos,3);
                        cm(mi,mj)=1;
                    end
                end
            end
        else
        end
    end
end
unknown = length(cm(~cm));
h=ones(4,n,3)*-1;
zv = cm(ed) & ~solution(ed);
zd = find(all(zv,2));
uk = ~cm(ed);
if (~isempty(zd))
    czd =zd(1);
    ectr =1;
else
    kd = find(all(cm(ed),2));
    if (~isempty(kd))
        [zs, zind] = max(sum(zv,2));
        if (max(zs)>0)
            czd = zind(1);
        else
            [kv,kind] = max(sum(zv(kd,:),2));
            czd = kind(1);
        end
    else
        for ii=1:4; s(ii)=((sum(solution(ed(ii,find(cm(ed(ii,:))))))));end
        [v,ind] = min(s);
        if(ind)
            czd = ind(1);
        else
            czd = round((rand*3)+1);
        end
    end
kzap = find(cm(ed(czd,:)).*logical(solution(ed(czd,:))));
for ii=kzap
    flash(ii,czd,'high');
    h(czd,ii,:) = -1;
end
ukzap = find(uk(czd,:));
id = cw(czd+2*(czd>2));
if (czd >2) pos=1;
else
    pos = n;
end
h(id,pos,:)=-1;
[or,oc,os] = flash (pos,id);
pte = isequal(abs(pos-abs(or+oc))+os, 0);
if (~pte)
    for ii=ukzap
        flash(ii,czd,'high');
        h(id,pos,:) = -1;
        [or,oc,os] = flash (pos,id);
        [pi,pj] = pos2ij(abs(or+os),id,n);
        [sr, sc] = ij2rc(pi,pj,czd);
        opos = abs(sr+sc);
        solution(ed(czd,1:opos))=0;
        cm(ed(czd,1:opos))=1;
        pte = all(cm(ed(czd,:)) & ~solution(ed(czd,:)));
        pte = isequal(abs(pos-abs(or+oc))+os, 0);
        if (pte) break; end
    end
end
end
    ced = ed(czd,:);
    ectr=1;
    inr = [-1, 0, 1, 0];
    inc = [ 0, -1, 0,1];
    while (unknown && ectr<n)
        id = cw(czd);
        if (czd >2) pos=ectr;
        else
            pos = n-ectr+1;
        end
        [or,oc,os] = flash (pos,id);
        pte = isequal(abs(pos-abs(or+oc))+os, 0);
        newvals = zeros(1,n);
        while (~pte)
            if (isequal(id-whichface(or,oc),0))
                obpos = -1*(czd<3)+abs(or+oc)+1*(czd>2);
                [obi,obj] = pos2ij(obpos,id,n);
            else
                [ir,ic] = pos2rc(pos,id);
                obi=abs(ir+or) + inr(czd)+inr(id);
                obj=abs(ic+oc) + inc(czd)+inc(id);
            end
            [obr,obc]=ij2rc(obi,obj,czd);
            beam (obr,obc,'high');
            h(id,pos,:)=-1;
            newvals(abs(obr+obc)) = os;
            [or,oc,os] = flash (pos,id);
            pte = isequal(abs(pos-abs(or+oc))+os, 0);
        end
        readidx = ced+sgn(czd)*(1+(n-1)*(mod(czd,2)<1));
        oldvals = solution(readidx);
        idx=find(oldvals > newvals);
        solution(readidx) = newvals;
        if (idx & ectr>1)
            for  ii=idx
                if (uk(czd,ii))
                    solution(readidx(ii)) = 0;
                end
            end
        end
        cm(ced)=1;
        unknown = length(cm(~cm));
        ectr=ectr+1;
        ced =ced + sgn(czd)*(1+(n-1)*(mod(czd,2)<1));
    end
function pface =  perp_beam(inpos,inface)
cw=[4,1,2,3,4,1];
q=mod(inface,4)<2;
if (q)
    if (inpos>2)
        pface=cw(inface+2);
    else
        pface=cw(inface);
    end
else
    if (inpos>2)
        pface=cw(inface);
    else
        pface=cw(inface+2);
    end
end
function [r,c] = pos2rc(pos,face)
  switch face
   case 1
    r = 0; c = -pos; 
   case 2
    r = -pos; c = 0;
   case 3
    r = 0; c = pos;
   case 4
    r = pos; c = 0;
  end
function [ii,jj] = pos2ij(pos,face,n)
switch face
 case 1
  jj = pos; ii = n; 
 case 2
  jj = n; ii = pos;
 case 3
  ii = 1; jj = pos;
 case 4
  ii = pos; jj = 1;
end
function [r,c] = ij2rc(ii,jj,face)
  switch face
   case 1
    r = 0; c = -jj; 
   case 2
    r = -ii; c = 0;
   case 3
    r = 0; c = jj;
   case 4
    r = ii; c = 0;
  end
function face = whichface(r,c)
 face = (c<0)+3*(c>0)+2*(r<0)+4*(r>0);
function [or,oc,os] = flash(pos,inface,mode)
global h
switch inface
        case 1
           ir = 0; ic = -pos; 
        case 2
           ir = -pos; ic = 0;
        case 3
            ir = 0; ic = pos;
        case 4
            ir = pos; ic = 0;
end
switch(nargin)
 case 2
  or = h(inface,abs(ir+ic),1);
  oc = h(inface,abs(ir+ic),2);
  os = h(inface,abs(ir+ic),3);
  if (os < 0)
    [or,oc,os] = beam(ir,ic);  
  else
  end
  h(inface,abs(ir+ic),:) = [or,oc,os];
 otherwise
  [or,oc,os] = beam(ir,ic,'high');
end
function flag = write_solution(r,c,val)
global solution 
flag=0;
if (~isequal(solution(r,c),val))
  solution(r,c)=val;
  flag=1;
end