| Code: | function W = clean(B0)
[nR,nC]=size(B0);
B=nan(nR+2,nC+2);
B(2:end-1,2:end-1)=B0;
% tweak = rand(7,1);
Borig = B;
maxbridges = 5;
%
%
cutfirst = 4;
cutoff = 10;
% 9, 10, 11, 12, 13
Wzero = zeros(0,4);
W = Wzero;
S = inf;
% fprintf('\n');
for x = [1 3]
[U BU] = phase1(Borig,Wzero,cutfirst,x);
[V BX] = phase3(Borig,BU,U,0,cutoff,x);
for y = [3 1]
if x == 3 && y == 1 && S > 1500
return
end
W1 = phase2(Borig,BX,V,maxbridges,cutoff,y)-1;
S1 = mygrade(B0,W1);
if S1 <= S
% if isfinite(S), fprintf(', %4d\n', S1 - S), else
% fprintf('\n'), end
S = S1;
W = W1;
else
% fprintf('\n');
end
end
end
end
function score = mygrade(B,W)
nR=size(B,1);
B(W(:,1)+(W(:,2)-1)*nR)=0;
B(W(:,3)+(W(:,4)-1)*nR)=0;
score=sum(B(:))+size(W,1)+sum(W(:,1)==W(:,3)&W(:,2)==W(:,4))*24;
end
%%
function [pincount k] = analyzeboard(B)
% make a sorted list of all pins
pin = sort(B(B>0),'descend');
npins = size(pin,1);
if npins < 1
pincount = [];
k = 0;
return
end
% pin, count, benefit
pincount = zeros(npins,3);
pincount(1,1) = pin(1);
k = 1;
count = 1;
for i = 2:npins
if pin(i) == pincount(k,1)
count = count + 1;
else
pincount(k,2) = count;
k = k + 1;
count = 1;
pincount(k,1) = pin(i);
end
end
pincount(k,2) = count;
pincount = pincount(1:k,:);
% calculate the benefit of a path
for i = 1:k
if pincount(i,2) >= 2
p = pincount(i,1);
[row col] = find(B == p);
d = 0;
for j = 2:size(row,1);
d = d + abs(row(j)-row(j-1)) + abs(col(j)-col(j-1));
end
pincount(i,3) = pincount(i,2)*p - 0.85*d;
end
end
end
%%
function [W B] = phase1(B,W,cutoff,rz)
% - phase 1 - - - -
% fprintf('-- phase 1 --\n');
% W = zeros(0,4);
[pincount k] = analyzeboard(B);
if k < 1
return
end
[s ix] = sort(pincount(:,rz),'descend');
% if rz <= 2
% Y = 2 + floor(rand*2);
% [s ix] = sort(pincount(:,Y),'descend');
% else
% [s ix] = sort(pincount(:,1),'descend');
% end
pincount = pincount(ix,:);
% fprintf('pincount ...\n');
% pincount
% pause
for i = 1:k
if pincount(i,2) >= 2
p = pincount(i,1);
[row col] = find(B == p);
N = size(row,1);
% find all pairwise distances
Npairs = N*(N-1)/2;
dist = zeros(Npairs,3);
x = 0;
for a = 1:N
for b = (a+1):N
x = x + 1;
dist(x,1) = a;
dist(x,2) = b;
dist(x,3) = abs(row(a)-row(b)) + abs(col(a)-col(b));
end
end
% sort by distance
[d ix] = sort(dist(:,3));
dist = dist(ix,:);
% try to connect the closest pair possible
npins = 0;
for x = 1:Npairs
if dist(x,3) > cutoff+1
% fprintf('warning: dist = %2d\n', dist(x,3));
break
end
a = dist(x,1);
b = dist(x,2);
% path = simplepath([row(a); row(b)], [col(a); col(b)], -p);
path = complexpath(B,[row(a); row(b)], [col(a); col(b)], -p, cutoff, 2*p);
if size(path,1) > 0
% fprintf('p = %d, connect a=%d, b=%d, dist = %d\n', p, a, b, dist(x,3));
% fprintf('\nFound path, p = %d, r=%d c=%d, r=%d, c=%d\n', p, row(a), col(a), row(b), col(b));
W = [W; path];
B = addwirepath(B,path,-p);
% pinlist = [row(a) col(a); row(b) col(b)];
npins = 2;
edit = [1:(a-1) (a+1):(b-1) (b+1):N];
row = [row(a); row(b); row(edit)];
col = [col(a); col(b); col(edit)];
break
else
% fprintf('p = %d, cannot connect a=%d, b=%d, dist = %d\n', p, a, b, dist(x,3));
end
end
if npins < 2
continue
end
for j = 3:N
% find all pins and wires
[row2 col2] = find(B == -p);
Npinwires = size(row2,1);
% fprintf('npins = %d, nwires = %d\n', npins, Npinwires - npins);
% find all pairwise distances
% a = already connected (pin or wire), b = not yet connected
Npairs = Npinwires * (N - npins);
dist = zeros(Npairs,3);
x = 0;
for a = 1:Npinwires
for b = (npins+1):N
x = x + 1;
dist(x,1) = a;
dist(x,2) = b;
dist(x,3) = abs(row2(a)-row(b)) + abs(col2(a)-col(b));
end
end
% sort by distance
[d ix] = sort(dist(:,3));
dist = dist(ix,:);
% try to connect closest pair possible
connected = false;
for x = 1:Npairs
if dist(x,3) > cutoff+1
% fprintf('warning: dist = %2d\n', dist(x,3));
break
end
a = dist(x,1);
b = dist(x,2);
% path = simplepath([row2(a); row(b)], [col2(a); col(b)], -p);
path = complexpath(B,[row2(a); row(b)], [col2(a); col(b)], -p, cutoff, p);
if size(path,1) > 0
% fprintf('\nfound path, p = %d, r=%d c=%d, r=%d, c=%d\n', p, row2(a), col2(a), row(b), col(b));
% if size(path,1) > p
% % fprintf('warning: pathlen = %d, pin = %d\n', size(path,1), p);
% break
% end
W = [W; path];
B = addwirepath(B,path,-p);
% pinlist = [pinlist; row(b) col(b)];
npins = npins + 1;
connected = true;
% if b ~= j
% t = row(j); row(j) = row(b); row(b) = t;
% t = col(j); col(j) = col(b); col(b) = t;
% end
row([j b]) = row([b j]);
col([j b]) = col([b j]);
break
end
end
if ~connected
break
end
end
end
end
end
%%
function [W B] = phase2(Borig,B,W,maxbridges,kappa,rz)
% -- phase 2 --
% fprintf('-- phase 2 --\n');
% kappa = 11;
[BH BV] = buildbridges(Borig,B,W);
[pincount k] = analyzeboard(B);
if k < 1
return
end
[s ix] = sort(pincount(:,rz),'descend');
% if mod(rz,2) == 1
% Y = 2 + floor(rand*2);
% [s ix] = sort(pincount(:,Y),'descend');
% else
% [s ix] = sort(pincount(:,1),'descend');
% end
pincount = pincount(ix,:);
% fprintf('\nphase2 pincount ...\n');
% pincount
% pause
for i = 1:k
p = pincount(i,1);
[row2 col2] = find(B == -p);
Npinwires = size(row2,1);
if Npinwires == 0
% fprintf('p = %d, no previous pinwires\n', p);
if pincount(i,2) >= 2
[row col] = find(B == p);
N = size(row,1);
% find all pairwise distances
Npairs = N*(N-1)/2;
dist = zeros(Npairs,3);
x = 0;
for a = 1:N
for b = (a+1):N
x = x + 1;
dist(x,1) = a;
dist(x,2) = b;
dist(x,3) = abs(row(a)-row(b)) + abs(col(a)-col(b));
end
end
% sort by distance
[d ix] = sort(dist(:,3));
dist = dist(ix,:);
maxstep = min((maxbridges*25)+kappa,2*p+1);
% try to connect the closest pair possible
connected = false;
for x = 1:Npairs
if dist(x,3) > maxstep+1
% fprintf('warning: dist = %2d\n', dist(x,3));
break
end
a = dist(x,1);
b = dist(x,2);
path = bridgepath(B,BH,BV,[row(a); row(b)], [col(a); col(b)], -p, maxbridges, kappa, 2*p);
if size(path,1) > 0
% fprintf('\nBRIDGE path, p = %d, r=%d c=%d, r=%d, c=%d\n', p, row(a), col(a), row(b), col(b));
W = [W; path];
B = addwirepath(B,path,-p);
[B BH BV] = addbridgewirepath(B,BH,BV,path,-p);
connected = true;
break
end
end
if ~connected
continue
end
end
end
[row col] = find(B == p);
Npins = size(row,1);
maxstep = min((maxbridges*25)+kappa,p+1);
for j = 1:Npins
[row2 col2] = find(B == -p);
Npinwires = size(row2,1);
% find all pairwise distances
% a = already connected (pin or wire), b = not yet connected
Npairs = Npinwires * (Npins-j+1);
dist = zeros(Npairs,3);
x = 0;
for a = 1:Npinwires
for b = j:Npins
x = x + 1;
dist(x,1) = a;
dist(x,2) = b;
dist(x,3) = abs(row2(a)-row(b)) + abs(col2(a)-col(b));
end
end
% sort by distance
[d ix] = sort(dist(:,3));
dist = dist(ix,:);
% try to connect closest pair possible
connected = false;
for x = 1:Npairs
if dist(x,3) > maxstep+1
% fprintf('warning: dist = %2d\n', dist(x,3));
break
end
a = dist(x,1);
b = dist(x,2);
path = bridgepath(B,BH,BV,[row2(a); row(b)], [col2(a); col(b)], -p, maxbridges, kappa, p);
if size(path,1) > 0
% fprintf('\nEXTRA BRIDGE path, p = %d, r=%d c=%d, r=%d, c=%d\n', p, row2(a), col2(a), row(b), col(b));
W = [W; path];
B = addwirepath(B,path,-p);
[B BH BV] = addbridgewirepath(B,BH,BV,path,-p);
connected = true;
% if b ~= j
% t = row(j); row(j) = row(b); row(b) = t;
% t = col(j); col(j) = col(b); col(b) = t;
% end
row([j b]) = row([b j]);
col([j b]) = col([b j]);
break
end
end
if ~connected
break
end
end
end
end
%%
function [W B] = phase3(Borig,B,W,maxbridges,kappa,rz)
% -- phase 2 --
% fprintf('-- phase 2 --\n');
% kappa = 11;
% [BH BV] = buildbridges(Borig,B,W);
[pincount k] = analyzeboard(B);
if k < 1
return
end
[s ix] = sort(pincount(:,rz),'descend');
% if mod(rz,2) == 1
% Y = 2 + floor(rand*2);
% [s ix] = sort(pincount(:,Y),'descend');
% else
% [s ix] = sort(pincount(:,1),'descend');
% end
pincount = pincount(ix,:);
% fprintf('\nphase2 pincount ...\n');
% pincount
% pause
for i = 1:k
p = pincount(i,1);
[row2 col2] = find(B == -p);
Npinwires = size(row2,1);
if Npinwires == 0
% fprintf('p = %d, no previous pinwires\n', p);
if pincount(i,2) >= 2
[row col] = find(B == p);
N = size(row,1);
% find all pairwise distances
Npairs = N*(N-1)/2;
dist = zeros(Npairs,3);
x = 0;
for a = 1:N
for b = (a+1):N
x = x + 1;
dist(x,1) = a;
dist(x,2) = b;
dist(x,3) = abs(row(a)-row(b)) + abs(col(a)-col(b));
end
end
% sort by distance
[d ix] = sort(dist(:,3));
dist = dist(ix,:);
maxstep = min((maxbridges*25)+kappa,2*p+1);
% try to connect the closest pair possible
connected = false;
for x = 1:Npairs
if dist(x,3) > maxstep+1
% fprintf('warning: dist = %2d\n', dist(x,3));
break
end
a = dist(x,1);
b = dist(x,2);
% path = bridgepath(B,BH,BV,[row(a); row(b)], [col(a); col(b)], -p, maxbridges, kappa, 2*p);
path = complexpath(B,[row(a); row(b)], [col(a); col(b)], -p, kappa, 2*p);
if size(path,1) > 0
% fprintf('\nBRIDGE path, p = %d, r=%d c=%d, r=%d, c=%d\n', p, row(a), col(a), row(b), col(b));
W = [W; path];
B = addwirepath(B,path,-p);
% [B BH BV] = addbridgewirepath(B,BH,BV,path,-p);
connected = true;
break
end
end
if ~connected
continue
end
end
end
[row col] = find(B == p);
Npins = size(row,1);
maxstep = min((maxbridges*25)+kappa,p+1);
for j = 1:Npins
[row2 col2] = find(B == -p);
Npinwires = size(row2,1);
% find all pairwise distances
% a = already connected (pin or wire), b = not yet connected
Npairs = Npinwires * (Npins-j+1);
dist = zeros(Npairs,3);
x = 0;
for a = 1:Npinwires
for b = j:Npins
x = x + 1;
dist(x,1) = a;
dist(x,2) = b;
dist(x,3) = abs(row2(a)-row(b)) + abs(col2(a)-col(b));
end
end
% sort by distance
[d ix] = sort(dist(:,3));
dist = dist(ix,:);
% try to connect closest pair possible
connected = false;
for x = 1:Npairs
if dist(x,3) > maxstep+1
% fprintf('warning: dist = %2d\n', dist(x,3));
break
end
a = dist(x,1);
b = dist(x,2);
% path = bridgepath(B,BH,BV,[row2(a); row(b)], [col2(a); col(b)], -p, maxbridges, kappa, p);
path = complexpath(B,[row2(a); row(b)], [col2(a); col(b)], -p, kappa, 2*p);
if size(path,1) > 0
% fprintf('\nEXTRA BRIDGE path, p = %d, r=%d c=%d, r=%d, c=%d\n', p, row2(a), col2(a), row(b), col(b));
W = [W; path];
B = addwirepath(B,path,-p);
% [B BH BV] = addbridgewirepath(B,BH,BV,path,-p);
connected = true;
% if b ~= j
% t = row(j); row(j) = row(b); row(b) = t;
% t = col(j); col(j) = col(b); col(b) = t;
% end
row([j b]) = row([b j]);
col([j b]) = col([b j]);
break
end
end
if ~connected
break
end
end
end
end
%%
function [BH BV] = buildbridges(Borig,B,path)
[NR NC] = size(B);
BH = Borig == 0;
BV = BH;
BH(:,[1 NC]) = false;
BV([1 NR],:) = false;
for i = 1:size(path,1)
if path(i,1) == path(i,3) % horizontal
BH(path(i,1),path(i,2)) = false;
BH(path(i,3),path(i,4)) = false;
end
if path(i,2) == path(i,4) % vertical
BV(path(i,1),path(i,2)) = false;
BV(path(i,3),path(i,4)) = false;
end
end
end
%%
function [B BH BV] = addbridgewirepath(B,BH,BV,path,label)
for i = 1:size(path,1);
if path(i,1) == path(i,3) % horizontal
BH(path(i,1),path(i,2)) = false;
BH(path(i,3),path(i,4)) = false;
if path(i,2) == path(i,4)
B(path(i,1),path(i,2)) = -9999;
end
end
if path(i,2) == path(i,4) % vertical
BV(path(i,1),path(i,2)) = false;
BV(path(i,3),path(i,4)) = false;
end
end
end
%%
function B = addwirepath(B,path,label)
B(path(1,1),path(1,2)) = label;
for i = 1:size(path,1);
B(path(i,3),path(i,4)) = label;
end
end
%%
function path = complexpath(B,row,col,label,cutoff,maxpathlen)
function path = traceback(dr,dc,t)
PR(dr,dc) = r(i);
PC(dr,dc) = c(i);
path = zeros(t,4);
for j = 1:t
path(j,1:2) = [dr dc];
pr = PR(dr,dc);
pc = PC(dr,dc);
path(j,3:4) = [pr pc];
dr = pr;
dc = pc;
end
end
% - complexpath -
[NR NC] = size(B);
PR = zeros(NR,NC);
PC = zeros(NR,NC);
C = -ones(NR,NC);
C(row(2),col(2)) = 0; % source
% tag the targets
C(row(1),col(1)) = -2;
C( B == label ) = -2;
rnext = zeros(NR*NC,1);
cnext = zeros(NR*NC,1);
count = 1;
rnext(1) = row(2);
cnext(1) = col(2);
for step = 0:min(cutoff,maxpathlen)
% [r c] = find(C == step);
if count < 1, break, end
N = count;
r = rnext(1:N);
c = cnext(1:N);
count = 0;
for i = 1:N
ci = c(i);
ri = r(i);
dc = ci;
dr = ri-1;
Z = dr + (dc-1)*NR;
tag = C(Z);
if tag == -2
path = traceback(dr,dc,step+1);
return
elseif tag == -1 && B(Z) == 0
C(Z) = step+1;
PR(Z) = ri;
PC(Z) = ci;
count = count + 1; rnext(count) = dr; cnext(count) = dc;
end
dr = ri + 1;
Z = dr + (dc-1)*NR;
tag = C(Z);
if tag == -2
path = traceback(dr,dc,step+1);
return
elseif tag == -1 && B(Z) == 0
C(Z) = step+1;
PR(Z) = ri;
PC(Z) = ci;
count = count + 1; rnext(count) = dr; cnext(count) = dc;
end
dr = ri;
dc = ci - 1;
Z = dr + (dc-1)*NR;
tag = C(Z);
if tag == -2
path = traceback(dr,dc,step+1);
return
elseif tag == -1 && B(Z) == 0
C(Z) = step+1;
PR(Z) = ri;
PC(Z) = ci;
count = count + 1; rnext(count) = dr; cnext(count) = dc;
end
dc = ci + 1;
Z = dr + (dc-1)*NR;
tag = C(Z);
if tag == -2
path = traceback(dr,dc,step+1);
return
elseif tag == -1 && B(Z) == 0
C(Z) = step+1;
PR(Z) = ri;
PC(Z) = ci;
count = count + 1; rnext(count) = dr; cnext(count) = dc;
end
% end
end
end
path = zeros(0,4);
end
%%
function path = bridgepath(B,BH,BV,row,col,label,maxbridges,kappa,maxpathlen)
function path = traceback(Z,step)
PZ(Z) = zi;
dr=mod(Z,NR);
dc=ceil(Z/NR);
path = zeros(step,4);
j = 0;
while dr ~= row(2) || dc ~= col(2)
j = j + 1;
path(j,1:2) = [dr dc];
Z = dr + (dc-1)*NR;
pz = PZ(Z);
pr=mod(pz,NR);
pc=ceil(pz/NR);
path(j,3:4) = [pr pc];
dr = pr;
dc = pc;
if BRIDGE(dr,dc)
j = j + 1;
path(j,:) = [dr dc dr dc];
end
end
path = path(1:j,:);
end
% - bridgepath -
% fprintf('bridgepath ...\n');
[NR NC] = size(B);
BRIDGE = false(NR,NC);
PZ = zeros(NR,NC);
C = -ones(NR,NC);
C(row(2),col(2)) = 0; % source
% tag targets
C(row(1),col(1)) = -2;
C( B == label ) = -2;
% maxstep = min(75+26,maxpathlen+1);
%
% -- kappa = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
%
% kappa = 11;
maxstep = min((maxbridges*25)+kappa,maxpathlen+1);
stepcount = zeros(maxstep+26,1);
for step = 0:maxstep
if step == 0
z = row(2) + (col(2)-1)*NR;
% r = row(2);
% c = col(2);
elseif stepcount(step) == 0
continue
else
z = find(C == step);
% [r c] = find(C == step);
end
N = numel(z);
% fprintf('step = %d, N = %d\n', step, N);
for i = 1:N
zi = z(i);
Z = zi - NR;
tag = C(Z);
if tag == -2
path = traceback(Z,step+1);
return
elseif tag == -1
if B(Z) == 0
C(Z) = step+1; stepcount(step+1) = 1;
PZ(Z) = zi;
elseif BH(Z)
C(Z) = step+26; stepcount(step+26) = 1;
PZ(Z) = zi;
BRIDGE(Z) = true;
end
end
Z = zi + NR;
tag = C(Z);
if tag == -2
path = traceback(Z,step+1);
return
elseif tag == -1
if B(Z) == 0
C(Z) = step+1; stepcount(step+1) = 1;
PZ(Z) = zi;
elseif BH(Z)
C(Z) = step+26; stepcount(step+26) = 1;
PZ(Z) = zi;
BRIDGE(Z) = true;
end
end
Z = zi - 1;
tag = C(Z);
if tag == -2
path = traceback(Z,step+1);
return
elseif tag == -1
if B(Z) == 0
C(Z) = step+1; stepcount(step+1) = 1;
PZ(Z) = zi;
elseif BV(Z)
C(Z) = step+26; stepcount(step+26) = 1;
PZ(Z) = zi;
BRIDGE(Z) = true;
end
end
Z = zi + 1;
tag = C(Z);
if tag == -2
path = traceback(Z,step+1);
return
elseif tag == -1
if B(Z) == 0
C(Z) = step+1; stepcount(step+1) = 1;
PZ(Z) = zi;
elseif BV(Z)
C(Z) = step+26; stepcount(step+26) = 1;
PZ(Z) = zi;
BRIDGE(Z) = true;
end
end
end
end
path = zeros(0,4);
end |