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

Lobotomy II

by Gerbert Myburgh

Status: Passed
Results: 217496 (cyc: 8, node: 614)
CPU Time: 3.929
Score: 217516.0
Submitted at: 2012-11-02 13:49:59 UTC
Scored at: 2012-11-02 13:53:01 UTC

Current Rank: 1715th (Highest: 115th )

Comments
Please login or create a profile.
Code
function xyOut = solver(a, xyIn, wts)

% Sample solver

% Copyright 2012 The MathWorks, Inc.
rand('seed',1);

xyOut = xyIn;

connectionsPerNode = sum(a);
numN = size(xyIn,1) ;         %Number of points 
maxD = max_distMAT(xyIn);     %Maximum distance between nodes

%{
numLines = sum(connectionsPerNode)/2;
[numK,p1,p2,intersectCount] = numKnotsMAT(xyIn,a);   %Number of knots (using Matlab counter)
startKnotCount = numK
%}

easyNodeToMove = wts .*connectionsPerNode;





%FIRST PLAN
%Find node with most connections
%Put in 0,0
%Add its connections around it in a big cicle.
%Then add remaining points one by one in remaining areas.



aOriginal = a;

sortedCPN = sort(connectionsPerNode,'descend');

maxCPN = max(connectionsPerNode);
%pause

allNodes = 1:numN;
%Plan
nodesPlaced = 0;
indexesOfNodesPlaced = [];

%Put the first node at 0,0
maxConnectionNodes = find(connectionsPerNode == sortedCPN(1));
indexOfCentreNode = maxConnectionNodes(1);
indexesOfNodesPlaced = [indexesOfNodesPlaced indexOfCentreNode];
xyOut(indexOfCentreNode,1) = 0;
xyOut(indexOfCentreNode,2) = 0;
nodesPlaced = nodesPlaced + 1;

%a(indexOfCentreNode,:)


xyOut = xyIn;
[a,xyOut,nodesPlaced] = down(a,xyOut,indexOfCentreNode,maxD,indexOfCentreNode);

intOut = round(xyOut);

attemptCounter = 1;
while((length(unique(intOut,'rows')) < length(xyOut)) && (attemptCounter < 100))
    
    intOut  = round(xyOut.*2.*attemptCounter);
    
    %Randomly move around overlapping units
    %Find overlapping nodes.
    for(i=1:numN)
        for(j=1:numN)
            if( (intOut(i,1) == intOut(j,1)) && (intOut(i,2) == intOut(j,2)) )
                intOut(i,1) = intOut(i,1)+round(rand(1)*attemptCounter*3);
                intOut(i,2) = intOut(i,2)+round(rand(1)*attemptCounter*3);
                intOut(j,1) = intOut(j,1)-round(rand(1)*attemptCounter*3);
                intOut(j,2) = intOut(j,2)-round(rand(1)*attemptCounter*3);
            end
        end
    end

    attemptCounter = attemptCounter+1;
end

if(attemptCounter < 100)
    xyOut = intOut;
else
    xyOut = xyIn;
end


%[N1,p1,p2,intersects] = numKnotsMAT(xyOut,aOriginal);



end




function [aOut,xyOut,indexOfNodesPlacedOUT] = down(aIn,xyIn,index,radius,indexOfNodesPlaced)
    xyWork = xyIn;
    %index
    aWork  = aIn;
    indexOfNodesPlacedWork = indexOfNodesPlaced;
    
    %aIn(index,:);
    indexOfConnectingNodes = find(aWork(index,:) == 1);
    origIndex = indexOfConnectingNodes;
    numIndexInThisIteration = length(origIndex);
    
    if(length(indexOfConnectingNodes) > 0)

        angle = 360/length(indexOfConnectingNodes);
        angleRad = angle/180*pi;

        connectionNum = 0;
        while (length(indexOfConnectingNodes) > 0)
            
           if(length(find(indexOfNodesPlacedWork == indexOfConnectingNodes(1))) < 1)               
               indexOfNodesPlacedWork = [indexOfNodesPlacedWork indexOfConnectingNodes(1)];
               xyWork(indexOfConnectingNodes(1),1) = (cos(angleRad*(connectionNum-1))*radius) + xyWork(index,1); %round(cos(angleRad*(connectionNum-1))*radius) + xyWork(index,1); %
               xyWork(indexOfConnectingNodes(1),2) = (sin(angleRad*(connectionNum-1))*radius) + xyWork(index,2); %round(sin(angleRad*(connectionNum-1))*radius) + xyWork(index,2); %
           end
           aWork(indexOfConnectingNodes(1),index) = 0;
           aWork(index,indexOfConnectingNodes(1)) = 0;    
           connectionNum = connectionNum+1;

           %[aWork,xyWork] = down(aWork,xyWork,indexOfConnectingNodes(1),radius/2);
           indexOfConnectingNodes = find(aWork(index,:) == 1);

        end

        for(i=1:length(origIndex))
           [aWork,xyWork,indexOfNodesPlacedWork] = down(aWork,xyWork,origIndex(i),radius/2,indexOfNodesPlacedWork);
        end
    end;
    
    
    xyOut = xyWork;
    aOut  = aWork;
    indexOfNodesPlacedOUT = indexOfNodesPlacedWork;
end



















%-------------------------------------------------------------------
%-------------------------------------------------------------------
%-------------------------------------------------------------------
% Contest functions used directly from grade.m
%-------------------------------------------------------------------
%-------------------------------------------------------------------
%-------------------------------------------------------------------


function D = max_distMAT(XY)

% This function finds the maximum distance (D) between two points in the
% point set given for the contest.

x = XY(:,1);
y = XY(:,2);

% D = max(pdist(XY(k,:))); % <--Only works if you have Stats Toolbox
D = sqrt(max(max( sqdistanceMAT(XY') )));
end

function D = sqdistanceMAT(A)
% Adapted from the File Exchange function here:
% http://www.mathworks.com/matlabcentral/fileexchange/24599-pairwise-distance-matrix

% Compute square Euclidean distances between all pair of vectors.
%   A: d x n1 data matrix
%   D: n1 x n2 pairwise square distance matrix
% Written by Michael Chen (sth4nth@gmail.com).
A = bsxfun(@minus,A,mean(A,2));
S = full(dot(A,A,1));
D = bsxfun(@plus,S,S')-full(2*(A'*A));
end