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

Solver28

by Robert Macrae

Status: Passed
Results: 29867 (cyc: 18, node: 985)
CPU Time: 50.491
Score: 30721.7
Submitted at: 2012-11-01 16:13:05 UTC
Scored at: 2012-11-01 21:14:00 UTC

Current Rank: 1623rd (Highest: 19th )

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
% 25 repositioning leaves 39487, so turned it back off.
%     0.5^2 merit improved to 39535
% 27 go for multiple starts; so far just put code in function, no changes
% 28 first stab at multirun code, 39661 in 21s.  Seems poor?


% 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
n = size(a,1);

% set up some scoring matrices
len = min( [0,0:n-2], [n-2:-1:0,0] );
lenmat = toeplitz( len );
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 );



% prepare to try several startpoints
scattering = [1,n-5,n-10,n-15,n-30,n:-20:10];
scattering(scattering<1)=[];
npaths = size(scattering,2);
bestlist = zeros(n,1);

% Run an initial loop through points,
bestlist = findpath( loose(1) );
more = bestlist(scattering);   % use it identify a spread of points to start from

% Now start at all the selected scattering and pick best result
a2 = a(bestlist,bestlist);
bestm = sum(sum(a2 .* meritm));
for i = 2:npaths
    list2 = findpath(more(i));
    a2 = a(list2,list2); 
    m2 = sum(sum(a2 .* meritm));
    if m2 > bestm 
        bestlist = list2;
    end
end


% Give it a polish
tried = false(n,1);
newlist = bestlist;
count = 10;
madechanges = true;
firstpass = true;  
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));



    function list = findpath( start );
    p = start;
    done = false(n,1);
    list = zeros(n,1);
    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)
    end % function


end