2012-11-07 16:00:00 UTC

# solver25

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 )

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 );
firstpass = true;

%     time0 = cputime;
%     while madechanges && (cputime - time0 < 3)

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...?