| Code: |
function W = solver(B)
W=zeros(0,4);
S=grade(B,W);
W1=chainsolver(B);
W2=advsolver(B);
W3=crosschecksolver(B);
S1=grade(B,W1);
S2=grade(B,W2);
S3=grade(B,W3);
if S1<S2 & S1<S3 & S1<S
W=W1;
elseif S2<S1 & S2<S3 & S2<S
W=W2;
elseif S3<S1 & S3<S2 & S3<S
W=W3;
end
function W = crosschecksolver(B)
W = zeros(0,4);
x=B;
pin=unique(nonzeros(B));
v=[];
for i=1:numel(pin)
v(end+1,1:2)=[pin(i) numel(find(x==pin(i)))];
end
v=flipud(sortrows(v,2)); %identify elements
%for count=1:size(v,1)
for count=1:1
WW=zeros(0,4);
%PIN=v(1,1);
PIN=v(count,1);
POS=find(x==PIN);
[I,J]=ind2sub(size(x),POS);
in=[I J];
for i=1:size(in,1)-1
fromrow=in(i,1);
fromcol=in(i,2);
torow=in(i+1,1);
tocol=in(i+1,2);
[output,short]=aAaA(fromrow,fromcol,torow,tocol,x,PIN);
if ~isempty(output) & isempty(short)
WW=[WW;output];
else
break
end
end
crossconnection=intersect(W,WW,'rows');
%crossconnection=checkcrossconnection(W,WW);
if isempty(crossconnection)
W=[W;WW]; %have to check for crossing
end
end
function [output,intersect]=aAaA(fromrow,fromcol,torow,tocol,matrix,element)
output=[];
intersect=[-1];
out1=basicconnect(fromrow,fromcol,torow,tocol);
[output1,intersect1]=cCsH(matrix,element,out1);
out2=basicuneqcr(fromrow,fromcol,torow,tocol);
[output2,intersect2]=cCsH(matrix,element,out2);
out3=basicuneqrc(fromrow,fromcol,torow,tocol);
[output3,intersect3]=cCsH(matrix,element,out3);
[output4,intersect4]=AaAa(fromrow,fromcol,torow,tocol,matrix,element);
if ~isempty(output1) & isempty(intersect1)
output=output1;
intersect=intersect1;
elseif ~isempty(output2) & isempty(intersect2)
output=output2;
intersect=intersect2;
elseif ~isempty(output3) & isempty(intersect3)
output=output3;
intersect=intersect3;
elseif ~isempty(output4) & isempty(intersect4)
output=output4;
intersect=intersect4;
end
function out=basicconnect(fromrow,fromcol,torow,tocol)
out=[];
if fromrow==torow & fromcol<tocol %exactly left
for i=fromcol:tocol-1
out(end+1,1:4)=[fromrow i torow i+1];
end
elseif fromrow==torow & fromcol>tocol %exactly right
for i=fromcol:-1:tocol+1
out(end+1,1:4)=[fromrow i torow i-1];
end
elseif fromrow<torow & fromcol==tocol %exactly up
for i=fromrow:torow-1
out(end+1,1:4)=[i fromcol i+1 tocol];
end
elseif fromrow>torow & fromcol==tocol %exactly down
for i=fromrow:-1:torow+1
out(end+1,1:4)=[i fromcol i-1 tocol];
end
end
function out=basicuneqcr(fromrow,fromcol,torow,tocol)
out=[];
if fromrow<torow & fromcol<tocol %up left
for i=fromcol:tocol-1
out(end+1,1:4)=[fromrow i fromrow i+1];
end
fromrow=out(end,3);
fromcol=out(end,4);
for i=fromrow:torow-1
out(end+1,1:4)=[i fromcol i+1 fromcol];
end
elseif fromrow<torow & fromcol>tocol %up right
for i=fromcol:-1:tocol+1
out(end+1,1:4)=[fromrow i fromrow i-1];
end
fromrow=out(end,3);
fromcol=out(end,4);
for i=fromrow:torow-1
out(end+1,1:4)=[i fromcol i+1 fromcol];
end
elseif fromrow>torow & fromcol<tocol %down left
for i=fromrow:-1:torow+1
out(end+1,1:4)=[i fromcol i-1 fromcol];
end
fromrow=out(end,3);
fromcol=out(end,4);
for i=fromcol:tocol-1
out(end+1,1:4)=[fromrow i fromrow i+1];
end
elseif fromrow>torow & fromcol>tocol %down right
for i=fromrow:-1:torow+1
out(end+1,1:4)=[i fromcol i-1 fromcol];
end
fromrow=out(end,3);
fromcol=out(end,4);
for i=fromcol:-1:tocol+1
out(end+1,1:4)=[fromrow i fromrow i-1];
end
end
function out=basicuneqrc(fromrow,fromcol,torow,tocol)
out=[];
if fromrow<torow & fromcol<tocol %up left
for i=fromrow:torow-1
out(end+1,1:4)=[i fromcol i+1 fromcol];
end
fromrow=out(end,3);
fromcol=out(end,4);
for i=fromcol:tocol-1
out(end+1,1:4)=[fromrow i fromrow i+1];
end
elseif fromrow<torow & fromcol>tocol %up right
for i=fromrow:torow-1
out(end+1,1:4)=[i fromcol i+1 fromcol];
end
fromrow=out(end,3);
fromcol=out(end,4);
for i=fromcol:-1:tocol+1
out(end+1,1:4)=[fromrow i fromrow i-1];
end
elseif fromrow>torow & fromcol<tocol %down left
for i=fromcol:tocol-1
out(end+1,1:4)=[fromrow i fromrow i+1];
end
fromrow=out(end,3);
fromcol=out(end,4);
for i=fromrow:-1:torow+1
out(end+1,1:4)=[i fromcol i-1 fromcol];
end
elseif fromrow>torow & fromcol>tocol %down right
for i=fromcol:-1:tocol+1
out(end+1,1:4)=[fromrow i fromrow i-1];
end
fromrow=out(end,3);
fromcol=out(end,4);
for i=fromrow:-1:torow+1
out(end+1,1:4)=[i fromcol i-1 fromcol];
end
end
function [output,intersect]=AaAa(fromrow,fromcol,torow,tocol,matrix,element)
out=[];
out=basicconnect(fromrow,fromcol,torow,tocol);
[output,intersect]=cCsH(matrix,element,out);
block=intersect;
pos=[0 -1
0 1
1 0
-1 0];
[R,C]=size(matrix);
if ~isempty(intersect) %short possibility
for i=1:4
dR=pos(i,1); dC=pos(i,2);
nR=fromrow+dR; nC=fromcol+dC;
if nR<=R & nR>=1 & nC<=C & nC>=1
outrc=basicconnect(fromrow,fromcol,nR,nC);
outcr=basicconnect(fromrow,fromcol,nR,nC);
outrc2=basicuneqrc(nR,nC,torow,tocol);
outcr2=basicuneqcr(nR,nC,torow,tocol);
[output2_rc,intersect2_rc]=cCsH(matrix,element,outrc2);
[output2_cr,intersect2_cr]=cCsH(matrix,element,outcr2);
if isempty(intersect2_rc)
output=[outrc;output2_rc];
intersect=intersect2_rc;
break
elseif isempty(intersect2_cr)
output=[outcr;output2_cr];
intersect=intersect2_cr;
break
end
end
end
end
function [output,intersect]=cCsH(matrix,element,connection)
%output=connection;
intersect=[];
for i=1:size(connection,1)
r=connection(i,3);
c=connection(i,4);
if matrix(r,c)~=0 & matrix(r,c)~=element
intersect(end+1,1:3)=[r c matrix(r,c)];
end
end
if isempty(intersect)
output=connection;
else
output=[];
end
function cross=checkcrossconnection(W,Wsub)
cross=[];
for i=1:size(Wsub,1)
temp=[Wsub(i,1) Wsub(i,2) Wsub(i,3) Wsub(i,4)];
cross=intersect(W,temp,'rows');
if isempty(cross)
temp=[Wsub(i,3) Wsub(i,4) Wsub(i,1) Wsub(i,2)];
cross=intersect(W,temp,'rows');
if ~isempty(cross)
return
end
else
return
end
end
function W = chainsolver(B)
W = zeros(0,4);
pin=unique(B);
pin=pin(find(pin));
for i=1:numel(pin)
element=pin(i);
optichain=fnaa(B,element);
chain=naaf(B,element);
in=[];
if ~isempty(optichain)
[mv,mi]=max(chain(:,2));
start=mi;
to=start+chain(mi,2)-1;
if size(optichain,1)>to
optichain=optichain(start:to,:);
end
for j=1:size(optichain,1)
[r,c]=ind2sub(size(B),optichain(j,1));
in(end+1,1:2)=[r c];
end
W=[W;connection(in)];
end
end
[ro,co] = size(B);
if any(any(W(:,[1 3])>ro)) || any(any(W(:,[2 4])>co)) || any(any(W<1))
W=zeros(0,4);
end
function chain=fnaa(matrix,element)
chain=[];
ind=find(matrix==element);
count=1;
while count<numel(ind)
base=ind(count);
out=chckn(matrix,base);
if numel(out)>0 & ~isempty(setdiff(out,base)) %thers's matching neighbor
out=setdiff(out,base);
chain(end+1,1:2)=[base numel(out)];
end
count=count+1;
end
function optichain=naaf(matrix,element)
chain=[];
optichain=[];
rowsize=size(matrix,1);
colsize=size(matrix,2);
ind=find(matrix==element);
count=1;
while count<numel(ind)
base=ind(count);
out=chckn(matrix,base);
if numel(out)>0 & ~isempty(setdiff(out,base)) %thers's matching neighbor
out=setdiff(out,base);
chain(end+1,1:2)=[base numel(out)];
end
count=count+1;
end
%create recursive chain upto depth D
value=[];
if ~isempty(chain)
D=6;
for iter=1:10
i=1;
base=chain(i,1);
out=chnta(base,D,rowsize);
[mv,mi]=intersect(chain(:,1),out);
count=chain(i,2)+sum(chain(mi,2))-numel(mi)+1;
value(end+1,1:2)=[base count];
newchainelem=setdiff(1:size(chain,1),[i mi]);
chain=chain(newchainelem,:);
if isempty(chain), break, end
end
end
optichain=value;
%-------------------------------------
function out=chnta(base,D,rowsize)
T=[];
for i=1:D
for j=1:numel(base)
T=[T base(j)+1 base(j)+rowsize];
end
base=T;
end
out=unique(T);
%-------------------------------------
function out=chckn(matrix,index)
out=[];
rowsize=size(matrix,1);
colsize=size(matrix,2);
element=numel(matrix);
% UP
newindex=index-1;
if newindex>=1 & newindex<=element & matrix(newindex)==matrix(index)
out(end+1)=newindex;
end
% DOWN
newindex=index+1;
if newindex>=1 & newindex<=element & matrix(newindex)==matrix(index)
out(end+1)=newindex;
end
% LEFT
newindex=index-rowsize;
if newindex>=1 & newindex<=element & matrix(newindex)==matrix(index)
out(end+1)=newindex;
end
% RIGHT
newindex=index+rowsize;
if newindex>=1 & newindex<=element & matrix(newindex)==matrix(index)
out(end+1)=newindex;
end
function out=connection(in)
out=[];
for i=1:size(in)-1
fromrow=in(i,1);
fromcol=in(i,2);
newin=in(i+1:end,:);
rowmatch=find(fromrow==newin(:,1));
if ~isempty(rowmatch)
torow=newin(rowmatch(1),1);
tocol=newin(rowmatch(1),2);
out(i,1:4)=[fromrow fromcol torow tocol];
else
colmatch=find(fromcol==newin(:,2));
if ~isempty(colmatch)
torow=newin(colmatch(1),1);
tocol=newin(colmatch(1),2);
out(i,1:4)=[fromrow fromcol torow tocol];
end
end
end
function W = advsolver(B)
W = zeros(0,4);
x=B;
swSr=unique(x);
swSr=swSr(find(swSr));
for count=1:numel(swSr)
PIN=swSr(count);
POS=find(x==PIN);
[I,J]=ind2sub(size(x),POS);
in=[I J];
for i=1:size(in,1)-1
tempin=in(i:i+1,:);
out=ili(tempin);
[output,intersect]=sSs(x,PIN,out);
if isempty(intersect)
W=[W;output];
else
break
end
end
end
function out=ili(in)
out=[];
for i=1:size(in)-1
rDr=in(i,1); RdR=in(i,2);
cFG=in(i+1,1); aaa=in(i+1,2);
if rDr==cFG & RdR<aaa %exactly left
for i=RdR:aaa-1
out(end+1,1:4)=[rDr i cFG i+1];
end
elseif rDr==cFG & RdR>aaa %exactly right
for i=RdR:-1:aaa+1
out(end+1,1:4)=[rDr i cFG i-1];
end
elseif rDr<cFG & RdR==aaa %exactly up
for i=rDr:cFG-1
out(end+1,1:4)=[i RdR i+1 aaa];
end
elseif rDr>cFG & RdR==aaa %exactly down
for i=rDr:-1:cFG+1
out(end+1,1:4)=[i RdR i-1 aaa];
end
elseif rDr<cFG & RdR<aaa %up left
for i=RdR:aaa-1
out(end+1,1:4)=[rDr i rDr i+1];
end
rDr=out(end,3);
RdR=out(end,4);
for i=rDr:cFG-1
out(end+1,1:4)=[i RdR i+1 RdR];
end
elseif rDr<cFG & RdR>aaa %up right
for i=RdR:-1:aaa+1
out(end+1,1:4)=[rDr i rDr i-1];
end
rDr=out(end,3);
RdR=out(end,4);
for i=rDr:cFG-1
out(end+1,1:4)=[i RdR i+1 RdR];
end
elseif rDr>cFG & RdR<aaa %down left
for i=rDr:-1:cFG+1
out(end+1,1:4)=[i RdR i-1 RdR];
end
rDr=out(end,3);
RdR=out(end,4);
for i=RdR:aaa-1
out(end+1,1:4)=[rDr i rDr i+1];
end
elseif rDr>cFG & RdR>aaa %down right
for i=rDr:-1:cFG+1
out(end+1,1:4)=[i RdR i-1 RdR];
end
rDr=out(end,3);
RdR=out(end,4);
for i=RdR:-1:aaa+1
out(end+1,1:4)=[rDr i rDr i-1];
end
end
end
function [output,intersect]=sSs(mMm,ll1,nNn)
output=nNn;
intersect=[];
for i=1:size(nNn,1)
r=nNn(i,3);
c=nNn(i,4);
if mMm(r,c)~=0 & mMm(r,c)~=ll1
intersect(end+1,1:3)=[r c mMm(r,c)];
end
end
|