| Code: | function W = solver(B)
W = zeros(0,4);
initial_score=grade(B,W);
pin=unique(nonzeros(B));
[W,pinconnection]=mysolver(B,pin);
final_score1=grade(B,W);
%score=[initial_score final_score1]
usedpin=pinconnection(find(pinconnection(:,2)>0),1);
% % pin
% % usedpin
% % pinconnection
% % disp('------------------------')
%
pin=setdiff(pin,usedpin);
if ~isempty(pin)
[W2,pinconnection]=mysolver2(B,pin,W);
% crossconnection=checkcrossconnection2(W,W2);
% if isempty(crossconnection)
% W2=[W;W2];
% %pinconnection(end+1,1:2)=[PIN size(WW,1)];
% end
final_score2=grade(B,W2);
if final_score2<final_score1
final_score1=final_score2;
W=W2;
%else
%disp('1st level')
end
end
% score=[initial_score final_score2]
% score=[initial_score final_score1]
% disp('------------------------------')
%-------------------------------------------------------------------
function [W,pinconnection]=mysolver(B,pin)
W = zeros(0,4);
x=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
%v=pin;
pinconnection=[];
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];
SCORE=grade(x,WW);
for iter=1:2
WWW=zeros(0,4);
if iter==1
in=in; %from front
elseif iter==2
in=flipud(in); %from back
else
in=in(randperm(size(in,1)),:) ; %permute in
end
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]=wiring(fromrow,fromcol,torow,tocol,x,PIN);
if ~isempty(output) & isempty(short)
WWW=[WWW;output];
else
break
end
end
% cross-connection check
%crossconnection=checkcrossconnection2(W,WWW);
%if isempty(crossconnection)
score=grade(x,WWW);
if score<SCORE
SCORE=score;
WW=WWW; %have to check for crossing
end
%end
end
% cross-connection check
crossconnection=checkcrossconnection2(W,WW);
if isempty(crossconnection)
W=[W;WW];
pinconnection(end+1,1:2)=[PIN size(WW,1)];
end
%W=[W;WW];
end
%-------------------------------------------------------------------
function [W,pinconnection]=mysolver2(B,pin,Wold)
W = Wold;
x=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
%v=pin;
pinconnection=[];
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];
SCORE=grade(x,WW);
for iter=3:15
WWW=zeros(0,4);
if iter==1
in=in; %from front
elseif iter==2
in=flipud(in); %from back
else
in=in(randperm(size(in,1)),:) ; %permute in
end
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]=wiring(fromrow,fromcol,torow,tocol,x,PIN);
if ~isempty(output) & isempty(short)
WWW=[WWW;output];
else
break
end
end
% cross-connection check
%crossconnection=checkcrossconnection2(W,WWW);
%if isempty(crossconnection)
score=grade(x,WWW);
if score<SCORE
SCORE=score;
WW=WWW; %have to check for crossing
end
%end
end
% cross-connection check
crossconnection=checkcrossconnection2(W,WW);
if isempty(crossconnection)
W=[W;WW];
pinconnection(end+1,1:2)=[PIN size(WW,1)];
end
%W=[W;WW];
end
%-------------------------------------------------------------------------
function [output,inter]=wiring(fromrow,fromcol,torow,tocol,matrix,element)
output=[];
inter=[-1];
out1=basicconnect(fromrow,fromcol,torow,tocol);
[output1,intersect1]=checkshort(matrix,element,out1);
if ~isempty(output1) & isempty(intersect1)
output=output1;
inter=intersect1;
else
out1=basicuneqcr(fromrow,fromcol,torow,tocol);
[output1,intersect1]=checkshort(matrix,element,out1);
if ~isempty(output1) & isempty(intersect1)
output=output1;
inter=intersect1;
else
out1=basicuneqrc(fromrow,fromcol,torow,tocol);
[output1,intersect1]=checkshort(matrix,element,out1);
if ~isempty(output1) & isempty(intersect1)
output=output1;
inter=intersect1;
else
[output1,intersect1]=advconnectwire2(fromrow,fromcol,torow,tocol,matrix,element,1,0);
if ~isempty(output1) & isempty(intersect1)
output=output1;
inter=intersect1;
else
[output1,intersect1]=advconnectwire2(fromrow,fromcol,torow,tocol,matrix,element,0,1);
if ~isempty(output1) & isempty(intersect1)
output=output1;
inter=intersect1;
else
[output1,intersect1]=advconnectwire2(fromrow,fromcol,torow,tocol,matrix,element,1,1);
if ~isempty(output1) & isempty(intersect1)
output=output1;
inter=intersect1;
else
% [output1,intersect1]=advconnectwire2(fromrow,fromcol,torow,tocol,matrix,element,2,2);
% if ~isempty(output1) & isempty(intersect1)
% output=output1;
% inter=intersect1;
% else
% %no more depth
% end
end
end
end
end
end
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,inter]=advconnectwire2(fromrow,fromcol,torow,tocol,matrix,element,rlevel,clevel)
out=[];
out=basicconnect(fromrow,fromcol,torow,tocol);
[output,inter]=checkshort(matrix,element,out);
block=inter;
pos=[0 -1
0 1
1 0
-1 0];
pos(:,1)=pos(:,1)*rlevel;
pos(:,2)=pos(:,2)*clevel;
[R,C]=size(matrix);
if ~isempty(inter) %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]=checkshort(matrix,element,outrc2);
[output2_cr,intersect2_cr]=checkshort(matrix,element,outcr2);
if isempty(intersect2_rc)
output=[outrc;output2_rc];
inter=intersect2_rc;
break
elseif isempty(intersect2_cr)
output=[outcr;output2_cr];
inter=intersect2_cr;
break
end
end
end
end
%-----------------------------------------------------------------
function [output,inter]=checkshort(matrix,element,connection)
%output=connection;
inter=[];
for i=1:size(connection,1)
r=connection(i,3);
c=connection(i,4);
if matrix(r,c)~=0 & matrix(r,c)~=element
inter(end+1,1:3)=[r c matrix(r,c)];
end
end
if isempty(inter)
output=connection;
else
output=[];
end
%--------------------------------------------------------------------
function cross=checkcrossconnection2(W,Wsub)
cross=[];
for i=1:size(Wsub,1)
temp=[Wsub(i,1) Wsub(i,2)];
cross=intersect(W(:,1:2),temp,'rows');
if ~isempty(cross),return,end
temp=[Wsub(i,1) Wsub(i,2)];
cross=intersect(W(:,3:4),temp,'rows');
if ~isempty(cross),return,end
temp=[Wsub(i,3) Wsub(i,4)];
cross=intersect(W(:,1:2),temp,'rows');
if ~isempty(cross),return,end
temp=[Wsub(i,3) Wsub(i,4)];
cross=intersect(W(:,3:4),temp,'rows');
if ~isempty(cross),return,end
end
|