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) > 18
    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

%% - 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');
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);
            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 pairwise distances
            % a = already connected, b = not yet connected
            Npairs =  npins * (N - npins);
            dist = zeros(Npairs,3);
            x = 0;
            for a = 1:npins
                for b = (npins+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 closest pair possible
            connected = false;
            for x = 1:Npairs
                a = dist(x,1);
                b = dist(x,2);
                path = simplepath([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 = [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
    if B(path(i,3),path(i,4)) == 0
        B(path(i,3),path(i,4)) = label;
    end
end
end