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

2.5step...faster

by Andreas Bonelli

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 )

Comments
Please login or create a profile.
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);
    
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    % CIRCLE (badness)
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
    badness = c.*a;  
    pointbadness = sum(badness, 1);
    %     pointknots = nknots(0);
    
    %     best = sum(pointknots)/4;
    best = sum(sum(badness));
    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, :));
         
        % only look ahead
        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);
        
        badness = c.*a;
        pointbadness = sum(badness, 1);
        totalbadness = sum(pointbadness);
        %         pointknots = nknots(0);
        %         totalknots = sum(pointknots)/4;
         
        if totalbadness < best;
            best = totalbadness;
            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;
%     
%     badness = c.*a;
%     pointbadness = sum(badness, 1);
%     totalbadness = sum(pointbadness);
%     
%     % 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;
%         
%         % only look ahead
%         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);
%         
%         %         badness = c.*a;
%         %         pointbadness = sum(badness, 1);
%         %         totalbadness = sum(pointbadness);
%         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;
    
    badness = c.*a;
    pointbadness = sum(badness, 1);
    totalbadness = sum(pointbadness);
    
    % 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;
        pointbadness = pointbadness ./ max(pointbadness);
        pointknots = pointknots ./ max(pointknots);
        
        if mod(iloop, 2);
            score = pointbadness;
        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;
        badness = c.*a;
        pointbadness = sum(badness, 1);
        totalbadness = sum(pointbadness);
    
        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