Finish 2012-11-07 16:00:00 UTC

solver25

by Robert Macrae

Status: Passed
Results: 30108 (cyc: 21, node: 881)
CPU Time: 30.126
Score: 31240.6
Submitted at: 2012-11-01 15:24:46 UTC
Scored at: 2012-11-01 20:48:29 UTC

Current Rank: 1624th (Highest: 18th )

Comments
Please login or create a profile.
Code
function xyOut = solver(a, xyIn, wts)

% Attempt to arrange points on circle so that at least 2 connections have
% no crossings.  For now just use circle and round but should design so no
% flat sides using integer ratios.  For N<320 need 40 different in [0,1]

% Solver06 tried forcing the next point to be adjacent to last, for a tiny
% net loss!  Surprising; may indicate local minimum?  Or bad circle?

% 10 start at a loose end 44047
% 12 prioritises points that only connect in  43240
% 13 removes singleton postprocess 43270 -- cleaner but not needed yet
% 14 attempts some polishing, of worst points, very marginal pickup 43059
% 15 focus on just points with 1 or 0 local links   4.2759
% 16 debugged backup circle code
% 17 iterative version, 42226.  
% 18 3 second bounce gives 42099, is it legal to use cputime?
% 19 just == on first pass, 42103
% 20 new merit, 42098
% 21 reduced tail to 16, 40934 and use a16 at start, 40811
% 22 pick less connected given equal scores 39529
% 23 applies samelogic to the two conin picks. Does worse, 39627... hmmm.
%    Does not seem to help for nonadjacent points so dropped.
% 24 minor merit tweak to close circle 39489
% 25 repositioning leaves 39487, so turned it back off.
%     0.5^2 merit improved to 39535



% Set up gradients that will draw smooth circles on integer grid
% Should move apart the closer ones to make adjustment safe?
g = repmat(1:11,11,1);
r = g ./ g';
g2 = g';
rm = [g(:),g2(:),r(:)];
rms = sortrows(rm,3);
keep = [true;rms(2:end,3)~=rms(1:end-1,3)];
g11 = [ [0,1]; rms(keep,1:2) ];
g11 = [ g11; [g11(:,2),-g11(:,1)] ];
g11 = [ g11; [-g11(:,1),-g11(:,2)] ];
g11 = cumsum(g11);


% Find a loosely connected point to start.  
% better to use a^logn and start in middle?
% try using this to do whole large-scale ordering job?
a2 = a * a;
a4 = a2 * a2;
a8 = a4 * a4;
a16 = a8 * a8;
[central,loose] = sort(diag(a16));
priority = -diag(a16);            % higher numbers are less well connected


% Set up initial loop through points
n = size(a,1);
done = false(n,1);
list = zeros(n,1);
p = loose(1);       % start somewhere not well connected
done(p) = true;
list(1) = p; 
for i = 2:n
    % choose a point well connected to recent ones; among those
    % prefer poorly connected outside
    tail = max(1,i-16);                    % tend to ignore points placed long ago    
                                           % setting tail = 1 worsens a lot
    conin = sum(a(:,list(tail:i-1)),2);    % # connections to recent points
    conin(done) = 0;
    conout = sum(a(:,~done),2);            % # connections to unplaced
    justin = ~logical(conout);             % if there are nodes with only internal
    if any(conin(justin))                  % connections then ignore others
        conin(~justin) = 0;
    end                
    cand = a(:,p);                         % points adjacent to p    
    aconin = conin;
    aconin(~logical(cand)) = 0;
    [score,p1] = max(aconin);              % Try an adjacent one first
    temp = priority;
    temp(aconin~=score) = -inf;
    [~,p] = max(temp);  % from equal scores take higher priority                    
    if score == 0
        [score,p] = max(conin);           % Try best connected to last few         
        if score == 0
            conin = sum(a(:,list(1:i-1)),2);  % Best connected to any past
            conin(done) = 0;
            [score,p] = max(conin);                                           
            if score == 0                  % should mean disjoint graph?   
                central = diag(a8);        % code not tested on visible set
                central(done) = inf;
                [score,p] = min(central);  % pick another loose one
            end
        end
    end

    % update records
    done(p) = true;
    list(i) = p; 
end

% Now have a list that indexes into a.  I want to move the matrix closer to
% diagonal so that lines are short (and hence have less scope to knot)


% Symrcm could perhaps be adapted but needs different objective to use on
% whole matrix; even when result is better on length metric it worsens
% score.  Better to polish subsets that are already well-behaved?
%{
len = min( [0,0:n-2], [n-2:-1:0,0] );
lenmat = toeplitz( len );
newa1 = a(list,list);
totlen1 = sum(sum(newa1 .* lenmat));      % overall merit for permutation 
list2 = symrcm(a);
newa2 = a(list2,list2)
totlen2 = sum(sum(newa2 .* lenmat));   
if totlen2 < totlen1
    list = list2;
end
%}


len = min( [0,0:n-2], [n-2:-1:0,0] );
lenmat = toeplitz( len );
tried = false(n,1);
newlist = list;
count = 10;
meritv = [0,1,0.5,0.3,0.2,0.1,0.05,0.025,0.01,zeros(1,n)];

meritv = (0.5 * ones(1,n)) .^ (1:n);

meritv = meritv(1:n);  % guard n<6
meritv = max(meritv,fliplr(meritv));
meritv(1) = 0;
meritv(n) = 0;
meritm = toeplitz( meritv );
madechanges = true;
firstpass = true;

%     time0 = cputime;
%     while madechanges && (cputime - time0 < 3)
    
while madechanges
    madechanges = false;
    for j = n:-1:2                              % consider moving this point  
        a2 = a(newlist,newlist);
        a2merit = sum(sum(a2 .* meritm));
        if (j==n) || ~( a2(j,j-1) && a2(j-1,j) )  % not in chain
            targets = find( a2(j,:) );             
            targets = unique([targets,targets+1]);
            besti = NaN;
            bestm = -inf;
            for i = targets                     % try to insert j at i
                % p and j both point into a2, dereference later if used
                if j~=i
                    if j<i
                        map = [1:j-1,j+1:i-1,j,i:n];
                    else
                        map = [1:i-1,j,i:j-1,j+1:n];
                    end
                    a3 = a2(map,map);
                    a3merit = sum(sum(a3 .* meritm));
                    if a3merit > bestm
                        besti = i;
                        bestm = a3merit;
                        bestmap = map;
                    end
                end
            end
            if bestm > a2merit || (firstpass && bestm == a2merit)
                newlist = newlist(bestmap);
                madechanges = true;
            end
        end
    end
    list = newlist;    
    firstpass = false;
end

%{
    a2 = a(newlist,newlist);
    totlen = sum(a2 .* lenmat);            % total incoming length 
    a2merit = sum(totlen);
    totlen(tried) = 0;
    [score,p] = max(totlen);
    tried(p) = true; 
%}




% Arrange points on circle
xyOut = zeros(size(xyIn));   


if n < 337
    for i = 1:n
        xyOut(list(i),:) = g11(i,:);
    end
else
    for i = 1:n                  % Debugged from Solver16
        ang = i * 2 * pi / n;
        rad = 2*(n+1) / pi; 
        x = -round(cos(ang) * rad);
        y = round(sin(ang) * rad);  
        xyOut(list(i),:) = [x,y];
    end
end


%{
% Now clean up singly-connected nodes 
% actually better to implement this during initial phase and put in next
% slots; can handle >1 and more regular makes further moves easier.
single = find(sum(a,2) == 1);
[linksto,~] = find(a(single,:)');
if size(linksto,1)>1   % For first attempt only handle one singleton per linksto
    [linksto, id] = sort(linksto);
    single = single(id);
    keep = [true;linksto(2:end)~=linksto(1:end-1)];
    single = single(keep);
    linksto = linksto(keep);    
end
mid = [490,0];  % Check safe for n>336?
dir = bsxfun( @minus, xyOut(linksto,:), mid );
dir = sign(dir);
if all(sum(abs(dir),2))   % Should always be true...?
    xyOut(single,:) = xyOut(linksto,:) + dir*10;
end
%}


% Centre circle; should reduce average move
wgtin = wts * xyIn ./ sum(wts);
wgtout = wts * xyOut ./ sum(wts);
xyOut = bsxfun( @plus, xyOut, round(wgtin-wgtout));

end