| Code: | function W = solver(B)
tweak = rand(7,1);
maxbridges = 3;
Borig = B;
[U B] = phase1(Borig,1);
BX = B;
% fprintf('U has %3d rows ...', size(U,1));
% [U1 B] = phase2(Borig,BX,U,2,1);
% fprintf('U1 has %3d rows ...', size(U1,1));
W1 = phase2(Borig,B,U,maxbridges,1);
% fprintf('W has %3d rows\n', size(W1,1));
S1 = mygrade(Borig,W1);
S = S1;
W = W1;
% - - -
if S > 0 % 90000 % 300
% [U B] = phase1(Borig,1);
% fprintf('U has %3d rows ...', size(U,1));
% [U1 B] = phase2(Borig,BX,U,2,2);
% fprintf('U1 has %3d rows ...', size(U1,1));
W2 = phase2(Borig,B,U,maxbridges,2);
% fprintf('W has %3d rows\n', size(W1,1));
S2 = mygrade(Borig,W2);
D2 = S2 - S;
if S2 < S
W = W2;
S = S2;
end
else
S2 = 0;
D2 = 0;
end
% - - -
if S > 0 % 300 % 900
[U B] = phase1(Borig,3);
BX = B;
% fprintf('U has %3d rows ...', size(U,1));
% [U1 B] = phase2(Borig,BX,U,2,3);
% fprintf('U1 has %3d rows ...', size(U1,1));
W3 = phase2(Borig,B,U,maxbridges,3);
% fprintf('W has %3d rows\n', size(W1,1));
S3 = mygrade(Borig,W3);
D3 = S3 - S;
if S3 < S
W = W3;
S = S3;
end
else
S3 = 0;
D3 = 0;
end
% - - -
if S > 0 % 9000
% [U B] = phase1(Borig,1);
% fprintf('U has %3d rows ...', size(U,1));
% [U1 B] = phase2(Borig,BX,U,2,4);
% fprintf('U1 has %3d rows ...', size(U1,1));
W4 = phase2(Borig,B,U,maxbridges,4);
% fprintf('W has %3d rows\n', size(W1,1));
S4 = mygrade(Borig,W4);
D4 = S4 - S;
if S4 < S
W = W4;
end
else
S4 = 0;
D4 = 0;
end
% fprintf('scores = %4d, %4d, %4d, %4d, improvement = %4d, %4d, %4d\n', S1, S2, S3, S4, D2, D3, D4);
end
% function score = mygrade(B,W)
% score = myconcom(B,W);
% end
function score = mygrade(B,W)
% function [score W Wlab C B] = myconcom(B,W)
% CONCOM Finds connected components and scores the solution
% Inputs:
% B - Board, a matrix with component ID's, 0's means no component.
% W - Wiring, a matrix (nx4) matrix with wires, invalid wires are
% ignored but charged into the score.
%
% The MATLAB Contest Team
% April, 2008
[ro,co] = size(B);
dW = abs(W(:,[1 2])-W(:,[3 4]));
% Extract bridges from W
Bridges = W(~any(dW,2),[1 2]);
% Calculate the wiring cost: (Bridge cost is 25, but 1 is alredy counted in W
wiringCost = size(W,1) + 24 * size(Bridges,1);
% Keep only valid wires in W
W = W(all(W(:,[1 3])>0 & W(:,[1 3])<=ro & W(:,[2 4])>0 & W(:,[2 4])<=co,2) & (sum(dW,2)==1),:);
% Change wiring coordinates to linear indexing:
V = sort([sub2ind([ro,co],W(:,1),W(:,2)) sub2ind([ro,co],W(:,3),W(:,4))],2);
BridgeIdx = sub2ind([ro,co],Bridges(:,1),Bridges(:,2));
% Create a graph (E (edges)):
E = zeros(size(V));
[node2idx,dummy,E(:)]= unique(V);
nN = numel(node2idx);
idx2node(node2idx) = 1:nN;
% Build an adjacency list for edges:
A = zeros(nN,4); % [v ^ > <]
for i = 1:nN
[j,k] = find(node2idx(i)==V);
A(i,2*(diff(V(j,:),[],2)>1)+k) = sum(E(j,:),2)-i;
end
% Keep bridges that exist over wires and are not over components
BridgeIdx = intersect(BridgeIdx,V(:));
BridgeIdx = BridgeIdx(B(BridgeIdx)==0);
% Remove bridges that do not separate vertical and horizontal wires
BridgeIdx = BridgeIdx(any(A(idx2node(BridgeIdx),[1 2]),2) & any(A(idx2node(BridgeIdx),[3 4]),2));
% Add extra nodes where Bridges exist:
A = [A;zeros(numel(BridgeIdx),4)];
node2idx = [node2idx; BridgeIdx];
j = nN;
for i = idx2node(BridgeIdx)
j = j+1;
A(j,:) = A(i,:);
if A(i,3)
A(A(i,3),4)=j;
end
if A(i,4)
A(A(i,4),3)=j;
end
A(i,[3 4]) = 0;
A(j,[1 2]) = 0;
end
% Label nodes
labels = zeros(size(A,1),1);
tv = find(~labels,1);
cc = 1;
while ~isempty(tv)
while ~isempty(tv)
labels(tv) = cc;
tv = nonzeros(A(tv,:));
tv = tv(labels(tv) == 0);
end
cc = cc+1;
tv = find(~labels,1);
end
% Copy labels to a board
C = zeros(ro,co);
C(node2idx) = labels;
H = ~C & B>0;
C(H) = cc+(0:nnz(H)-1);
C(BridgeIdx)=-1;
% Label wires
Wlab = zeros(size(V,1),1);
for i=1:size(A,1)
for j = 1:4
if A(i,j)
Wlab(V(:,1)==node2idx(i) & V(:,2)==node2idx(A(i,j))) = labels(i);
end
end
end
% find short-circuited components and remove them:
P = unique(nonzeros(B));
for i = 1:cc-1
p = unique(nonzeros(B(C==i)));
if numel(p)>1
P = setdiff(P,p);
end
end
% consider the largest island for every non-short-circuited component and
% remove it from the board:
for i = 1:numel(P)
[sz,ch] = max(sparse(C(B==P(i)),1,1));
if sz>1
B(C==ch)=0;
end
end
score = sum(nonzeros(B)) + wiringCost;
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 - d;
end
end
end
%%
function [W B] = phase1(B,rz)
cutoff = 9;
% - phase 1 - - - -
% fprintf('-- phase 1 --\n');
W = zeros(0,4);
[pincount k] = analyzeboard(B);
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, 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, 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,rz)
% -- phase 2 --
% fprintf('-- phase 2 --\n');
[BH BV] = buildbridges(Borig,B,W);
[pincount k] = analyzeboard(B);
if k < 1
return
end
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)+9,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, 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 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)+9,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, 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 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 = Borig == 0;
BH(:,1) = false;
BH(:,NC) = false;
BV(1,:) = false;
BV(NR,:) = false;
Npath = size(path,1);
for i = 1:Npath
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
% figure(100);
% imagesc(BH & (B < 0)), colormap(gray), axis image, title('Horizontal');
% figure(101);
% imagesc(BV & (B < 0)), colormap(gray), axis image, title('Vertical');
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;
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
if path(i,1) == path(i,3) && path(i,2) == path(i,4)
B(path(i,1),path(i,2)) = -9999;
else
B(path(i,1),path(i,2)) = label;
B(path(i,3),path(i,4)) = label;
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,1),path(i,2)) = label;
B(path(i,3),path(i,4)) = label;
end
% B(path(end,3),path(end,4)) = label;
end
%%
function path = complexpath(B,row,col,label,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
% if dr ~= row(2) || dc ~= col(2)
% fprintf('traceback fails\n');
% path
% fprintf('rowcol\n');
% [row col]
% fprintf('r c\n');
% [dr dc]
% 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);
%
% - cutoff - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
%
% offset = -2 + floor(4*rand);
cutoff = 9;
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
dc = c(i);
if r(i) > 1
dr = r(i)-1;
Z = 1 + (dr-1) + (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) = r(i);
PC(Z) = c(i);
count = count + 1; rnext(count) = dr; cnext(count) = dc;
end
end
if r(i) < NR
dr = r(i) + 1;
Z = 1 + (dr-1) + (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) = r(i);
PC(Z) = c(i);
count = count + 1; rnext(count) = dr; cnext(count) = dc;
end
end
dr = r(i);
if c(i) > 1
dc = c(i) - 1;
Z = 1 + (dr-1) + (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) = r(i);
PC(Z) = c(i);
count = count + 1; rnext(count) = dr; cnext(count) = dc;
end
end
if c(i) < NC
dc = c(i) + 1;
Z = 1 + (dr-1) + (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) = r(i);
PC(Z) = c(i);
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,maxpathlen)
function path = traceback(dr,dc,step)
% fprintf('traceback, dr = %d, dc = %d, step = %d\n', dr, dc, step);
Z = 1 + (dr-1) + (dc-1)*NR;
PR(Z) = r(i);
PC(Z) = c(i);
path = zeros(step,4);
j = 0;
while dr ~= row(2) || dc ~= col(2)
j = j + 1;
path(j,1:2) = [dr dc];
Z = 1 + (dr-1) + (dc-1)*NR;
pr = PR(Z);
pc = PC(Z);
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);
PR = zeros(NR,NC);
PC = 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 = 9;
maxstep = min((maxbridges*25)+kappa,maxpathlen+1);
stepcount = zeros(maxstep+1+25,1);
for step = 0:maxstep
if step == 0
r = row(2);
c = col(2);
elseif stepcount(step) == 0
continue
else
[r c] = find(C == step);
end
N = size(r,1);
% fprintf('step = %d, N = %d\n', step, N);
for i = 1:N
dr = r(i);
if c(i) > 1
dc = c(i) - 1;
Z = 1 + (dr-1) + (dc-1)*NR;
tag = C(Z);
if tag == -2
path = traceback(dr,dc,step+1);
return
elseif tag == -1
if B(Z) == 0
C(Z) = step+1; stepcount(step+1) = 1;
PR(Z) = r(i);
PC(Z) = c(i);
elseif BH(dr,dc)
C(Z) = step+1+25; stepcount(step+1+25) = 1;
PR(Z) = r(i);
PC(Z) = c(i);
BRIDGE(Z) = true;
end
end
end
if c(i) < NC
dc = c(i) + 1;
Z = 1 + (dr-1) + (dc-1)*NR;
tag = C(Z);
if tag == -2
path = traceback(dr,dc,step+1);
return
elseif tag == -1
if B(Z) == 0
C(Z) = step+1; stepcount(step+1) = 1;
PR(Z) = r(i);
PC(Z) = c(i);
elseif BH(dr,dc)
C(Z) = step+1+25; stepcount(step+1+25) = 1;
PR(Z) = r(i);
PC(Z) = c(i);
BRIDGE(Z) = true;
end
end
end
dc = c(i);
if r(i) > 1
dr = r(i)-1;
Z = 1 + (dr-1) + (dc-1)*NR;
tag = C(Z);
if tag == -2
path = traceback(dr,dc,step+1);
return
elseif tag == -1
if B(Z) == 0
C(Z) = step+1; stepcount(step+1) = 1;
PR(Z) = r(i);
PC(Z) = c(i);
elseif BV(dr,dc)
C(Z) = step+1+25; stepcount(step+1+25) = 1;
PR(Z) = r(i);
PC(Z) = c(i);
BRIDGE(Z) = true;
end
end
end
if r(i) < NR
dr = r(i) + 1;
Z = 1 + (dr-1) + (dc-1)*NR;
tag = C(Z);
if tag == -2
path = traceback(dr,dc,step+1);
return
elseif tag == -1
if B(Z) == 0
C(Z) = step+1; stepcount(step+1) = 1;
PR(Z) = r(i);
PC(Z) = c(i);
elseif BV(dr,dc)
C(Z) = step+1+25; stepcount(step+1+25) = 1;
PR(Z) = r(i);
PC(Z) = c(i);
BRIDGE(Z) = true;
end
end
end
end
end
path = zeros(0,4);
end
|