function W = solver(B)

%%
function path = simplepath(row,col,label)
% fprintf('simple path, r=%d c=%d, r=%d c=%d\n', row(1), col(1), row(2), col(2));
deltar = row(1) - row(2);
deltac = col(1) - col(2);
if abs(deltar)+abs(deltac) > 15
    path = zeros(0,4);
    return
end
dr = sign(deltar);
dc = sign(deltac);


% adjacent
if (abs(deltar) == 1 && dc == 0) || (dr == 0 && abs(deltac) == 1)
    path = [row(1) col(1) row(2) col(2)];
    return
end

% try step to next row
if dr ~= 0
    r = row(2) + dr;
    c = col(2);
    if B(r,c) == label
        path = [r c row(2) col(2)];
%         fprintf('found a wire %d\n', label);
        return
    end
    if B(r,c) == 0
        path = simplepath([row(1) r], [col(1) c], label);
        if size(path,1) > 0
            path = [path; r c row(2) col(2)];
            return
        end
    end
end

% try step to next col
if dc ~= 0
    r = row(2);
    c = col(2) + dc;
    if B(r,c) == label
        path = [r c row(2) col(2)];
%         fprintf('found a wire %d\n', label);
        return
    end
    if B(r,c) == 0
        path = simplepath([row(1) r], [col(1) c], label);
        if size(path,1) > 0
            path = [path; r c row(2) col(2)];
            return
        end
    end
end

path = zeros(0,4);
end

%%
function path = zcomplexpath(row,col,label)

    function path = traceback(r,c,t)
        path = zeros(t,4);
        for jj = 1:t
            path(jj,1:2) = [r c];
            pr = PR(r,c);
            pc = PC(r,c);
            path(jj,3:4) = [pr pc];
            r = pr;
            c = pc;
        end
        if r ~= row(2) || c ~= col(2)
            fprintf('traceback fails\n');
            path
            fprintf('rowcol\n');
            [row col]
            fprintf('r c\n');
            [r c]
        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

for step = 0:10
    [r c] = find(C == step);
    N = size(r,1);
    for ii = 1:N
        dc = c(ii);
        for dr = [(r(ii)-1) (r(ii)+1)]
            if dr < 1 || dr > NR, continue, end
            if (dr == row(1) && dc == col(1)) || B(dr,dc) == label
                PR(dr,dc) = r(ii);
                PC(dr,dc) = c(ii);
                path = traceback(dr,dc,step+1);
                return
            end
            if B(dr,dc) == 0 && C(dr,dc) == -1
                C(dr,dc) = step+1;
                PR(dr,dc) = r(ii);
                PC(dr,dc) = c(ii);
            end
        end
            
        dr = r(ii);
        for dc = [(c(ii)-1)  (c(ii)+1)]
            if dc < 1 || dc > NC, continue, end
            if (dr == row(1) && dc == col(1)) || B(dr,dc) == label
                PR(dr,dc) = r(ii);
                PC(dr,dc) = c(ii);
                path = traceback(dr,dc,step+1);
                return
            end
            if B(dr,dc) == 0 && C(dr,dc) == -1
                C(dr,dc) = step+1;
                PR(dr,dc) = r(ii);
                PC(dr,dc) = c(ii);
            end
        end
        
        
    end
end
path = zeros(0,4);
end

%% - solver - - - -
% size(B)
% fprintf('\nsolver\n');

W = zeros(0,4);

% make a sorted list of all pins
pin = sort(B(B>0),'descend');
npins = size(pin,1);
if npins < 1
    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
[s ix] = sort(pincount(:,3),'descend');
% [s ix] = sort(pincount(:,1),'descend');
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
            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);
            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
                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);
                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
                    break
                end
            end
          
            if ~connected
                break
            end
        end
        
    end
end

% fprintf('soln:\n');
% W
% pause
end

%%



%%
function B = addwirepath(B,path,label)
N = size(path,1);
for i = 1:N
    if B(path(i,1),path(i,2)) == 0
        B(path(i,1),path(i,2)) = label;
    end
    B(path(i,1),path(i,2)) = label;
    if B(path(i,3),path(i,4)) == 0
        B(path(i,3),path(i,4)) = label;
    end
    B(path(i,3),path(i,4)) = label;
end
end

%%
function path = complexpath(B,row,col,label)

    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

    function expand
        if B(dr,dc) == 0 && C(dr,dc) == -1
            C(dr,dc) = step+1;
            PR(dr,dc) = r(i);
            PC(dr,dc) = c(i);
        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

rnext = zeros(NR*NC,1);
cnext = zeros(NR*NC,1);
count = 1;
rnext(1) = row(2);
cnext(1) = col(2);
for step = 0:26
%     [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;
            if (dr == row(1) && dc == col(1)) || B(dr,dc) == label
                path = traceback(dr,dc,step+1);
                return
            end
%             expand();
            if B(dr,dc) == 0 && C(dr,dc) == -1
                C(dr,dc) = step+1;
                PR(dr,dc) = r(i);
                PC(dr,dc) = c(i);
                count = count + 1; rnext(count) = dr; cnext(count) = dc;
            end
        end
        if r(i) < NR
            dr = r(i) + 1;
            if (dr == row(1) && dc == col(1)) || B(dr,dc) == label
                path = traceback(dr,dc,step+1);
                return
            end
%             expand();
            if B(dr,dc) == 0 && C(dr,dc) == -1
                C(dr,dc) = step+1;
                PR(dr,dc) = r(i);
                PC(dr,dc) = c(i);
                count = count + 1; rnext(count) = dr; cnext(count) = dc;
            end
        end
            
        dr = r(i);
        if c(i) > 1
            dc = c(i) - 1;
            if (dr == row(1) && dc == col(1)) || B(dr,dc) == label
                path = traceback(dr,dc,step+1);
                return
            end
%             expand();
            if B(dr,dc) == 0 && C(dr,dc) == -1
                C(dr,dc) = step+1;
                PR(dr,dc) = r(i);
                PC(dr,dc) = c(i);
                count = count + 1; rnext(count) = dr; cnext(count) = dc;
            end
        end
        if c(i) < NC
            dc = c(i) + 1;
            if (dr == row(1) && dc == col(1)) || B(dr,dc) == label
                path = traceback(dr,dc,step+1);
                return
            end
%             expand();
            if B(dr,dc) == 0 && C(dr,dc) == -1
                C(dr,dc) = step+1;
                PR(dr,dc) = r(i);
                PC(dr,dc) = c(i);
                count = count + 1; rnext(count) = dr; cnext(count) = dc;
            end
        end 
    end
end
path = zeros(0,4);
end