2012-11-07 16:00:00 UTC

# 2.5step...faster

Status: Passed
Results: 84897 (cyc: 17, node: 1058)
CPU Time: 7.822
Score: 85635.7
Submitted at: 2012-11-01 15:27:44 UTC
Scored at: 2012-11-01 20:50:47 UTC

Current Rank: 1682nd (Highest: 44th )

Code
```function xyOut = solver01(a, xyIn, wts)

ps = xyIn;
npoints = size(ps, 1);
if npoints == 1;
xyOut = ps;
return;
end

a = logical(a);

a_orig = a;
permute = 1:npoints;
c = bsxfun(@(x,y) (x-y).^2, 1:npoints, (1:npoints)');
c = min(c, bsxfun(@(x,y) (x-y+npoints).^2, 1:npoints, (1:npoints)'));
c = min(c, bsxfun(@(x,y) (x-y-npoints).^2, 1:npoints, (1:npoints)'));

otp = 1:npoints;
otpflip = fliplr(otp);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%     pointknots = nknots(0);

%     best = sum(pointknots)/4;
bestpermute = otp;

for i = repmat(1:npoints, 1, 1);
if a(i, mod(i,npoints)+1); continue; end;

% all nodes possible
%         candidates = otp(a(i, :));

candidates = otp(i+1:end);
candidates = candidates(a(i, i+1:end));

if isempty(candidates); continue; end

% [~, six] = sort(pointknots(candidates));
candidates = candidates(six);

pa = mod(i,npoints)+1;
pb = candidates(1);

exchangepoints(pa, pb);

%         pointknots = nknots(0);
%         totalknots = sum(pointknots)/4;

bestpermute = permute;
if totalbadness == 0; break; end;
end
end

permute = bestpermute;
a = a_orig(permute, permute);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% CIRCLE 2 (knots)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%     pointknots = nknots(0);
%     totalknots = sum(pointknots)/4;
%
%
%     % rating has been badness so far but should be #knots now.
%     best = totalknots;
%
%     for i = repmat(1:npoints, 1, 1);
%         if a(i, mod(i,npoints)+1); continue; end;
%
%         candidates = otp(i+1:end);
%         candidates = candidates(a(i, i+1:end));
%
%         if isempty(candidates); continue; end
%
% %         [~, six] = sort(pointbadness(candidates));
%         [~, six] = sort(pointknots(candidates));
%         candidates = candidates(six);
%
%         pa = mod(i,npoints)+1;
%         pb = candidates(1);
%
%         exchangepoints(pa, pb);
%
%         pointknots = nknots(0);
%         totalknots = sum(pointknots)/4;
%
%         if totalknots < best;
%             best = totalknots;
%             bestpermute = permute;
%             if totalbadness == 0; break; end;
%         end
%     end
%
%     permute = bestpermute;
%     a = a_orig(permute, permute);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% IMPROVE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

pointknots = nknots(0);
totalknots = sum(pointknots)/4;

% rating has been badness so far but should be #knots now.
best = totalknots;

zeroscore = zeros(1, npoints);
iloop = 0;%ceil(sqrt(npoints));
while iloop > 0 && totalknots > 0;
pointknots = pointknots ./ max(pointknots);

if mod(iloop, 2);
else
score = pointknots;
end

[~, worstix] = sort(score, 'descend');

i = worstix(1);
j = worstix(2);

% DO EXCHANGE
exchangepoints(i, j);

pointknots = nknots(0);
totalknots = sum(pointknots)/4;

if totalknots < best;
best = totalknots;
bestpermute = permute;
if totalknots == 0; break; end;
end

fprintf('| #k %d | %d <-> %d \n', totalknots, i, j);

iloop=iloop-1;
end

permute = bestpermute;
a = a_orig(permute, permute);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% FINALIZE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

xyOut = makecycle(xyIn);
xyOut(bestpermute, :) = xyOut;

for i = 1:npoints;
left = i-1;
right = i+1;
if i == 1; left = npoints; end;
if i == npoints; right = 1; end;

if ~a(i, right) && ~a(i, left);
pull(i);
end
end

% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  FUNCS
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function pull(ii)
neighbors = a(ii, :);
%         xyOut(ii, :) =  round(mean(xyOut(neighbors,:), 1));

newloc = round(mean(xyOut(bestpermute(neighbors),:), 1));

while any(all(bsxfun(@eq, newloc, xyOut([1:ii-1,ii+1:end], :)), 2));
newloc = newloc + round(rand(1,2)*3-1.5);
end
xyOut(bestpermute(ii), :) = newloc;
end

function xy = ix2xy(ix)
xy = [mod(ix-1, npoints)+1, floor((ix-1)/npoints)+1];
end

function exchangepoints(i,j)
assert(i~=j);
if i > j; aid = j; j = i; i = aid; end;

a       = exchh(a      , i, j);
a       = exchv(a      , i, j);
wts     = exchh(wts    , i, j);
permute = exchh(permute, i, j);
%         a = [a(1:i-1,:); a(j,:); a(i+1:j-1,:); a(i,:); a(j+1:end,:)];
%         a = [a(:,1:i-1), a(:,j), a(:,i+1:j-1), a(:,i), a(:,j+1:end)];
%         wts = [wts(1:i-1), wts(j), wts(i+1:j-1), wts(i), wts(j+1:end)];
%         permute = [permute(1:i-1), permute(j), permute(i+1:j-1), permute(i), permute(j+1:end)];
end
function m = exchv(m, i, j)
m = [m(1:i-1,:); m(j,:); m(i+1:j-1,:); m(i,:); m(j+1:end,:)];
end

function m = exchh(m, i, j)
m = [m(:,1:i-1), m(:,j), m(:,i+1:j-1), m(:,i), m(:,j+1:end)];
end

function count = nknots(i_arg)
if i_arg == 0; i_arg = 1:npoints; end;

count = zeros(size(i_arg));
for ix = 1:numel(i_arg);
nn = i_arg(ix);
edgesto = find(a(nn, :));
for jj = edgesto;
if jj > nn; ii = nn;
else        ii = jj; jj = nn; %#ok<FXSET>
end
count(ix) = count(ix) + sum(sum(a(ii+1:jj-1, [1:ii-1, jj+1:end])));
end
end
end

%     function nknots = nknots()
%         nknots = zeros(npoints, 1);
%         for ii = 1:npoints;
%             nknots(ii) = nknotsfrom(ii);
%         end
%     end

end

function ret = makecycle(ps)
npoints = size(ps, 1);

c = round(mean(ps, 1));
r_vis = max(max(ps, [], 1) - min(ps, [], 1), [], 2)/2;

%     r = ceil(npoints/4);
%     r = ceil(npoints/2);
r = ceil(npoints);

% REMOVE FOR SUMBISSION...
r = max(r, r_vis);

is = 2*pi*(0:(npoints-1))/npoints;
%     ret = round(r*[cos(is)', sin(is)']);
ret = out(r*[cos(is)', sin(is)']);

ret = bsxfun(@plus, ret, c);
end

function m = out(m)
pos = m > 0;

m( pos) = ceil (m( pos));
m(~pos) = floor(m(~pos));
end```