2006-12-06 09:00:00 UTC

# seek_n_destroy_generality_7b

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

Rajiv Narayan
06 Dec 2006
Slight strategy change
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
idx=find(oldvals > newvals);
if (idx & ectr>1)
for  ii=idx
if (uk(czd,ii))
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
```