2012-11-07 16:00:00 UTC

Solver28

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 )

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;
firstpass = true;
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);
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;
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);
if size(linksto,1)>1   % For first attempt only handle one singleton per linksto
single = single(id);
single = single(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...?
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
```