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

fairly lame

by Mike Bindschadler

Status: Passed
Results: 51850 (cyc: 6, node: 801)
CPU Time: 24.656
Score: 51878.6
Submitted at: 2012-11-01 10:39:15 UTC
Scored at: 2012-11-01 18:23:34 UTC

Current Rank: 1662nd (Highest: 30th )

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

at = triu(a);
N = length(wts);

linkCount = sum(at,2);

[maxNLinks,maxind] = max(linkCount);
%{
depth = 10; 
an = zeros(N,N,depth);
an(:,:,1) = a;
for i =2:depth
    for j = 1:N
        for k = j:N
            an(j,k,i) = any(an(:,j,i-1) & an(:,k,1));
            %an(k,j,i) = an{i}(j,k);
        end
    end   
    an(:,:,i) = an(:,:,i)' | an(:,:,i);
end
%}
%% Define direction offsets
dir8 =  [0,1;
    1,1;
    1,0;
    1,-1;
    0,-1;
    -1,-1;
    -1,0;
    -1,1;
    0,1;];

dir16 = [0,2; % north, direction 1
    1,2;
    2,2;    % NE, 3
    2,1;
    2,0;    % east, 5
    2,-1;
    2,-2;   % SE, 7
    1,-2;
    0,-2;   % south, direction 9
    -1,-2;
    -2,-2;  % SW, 11
    -2,-1;
    -2,0;   % west, 13
    -2,1;
    -2,2;   % NW, 15
    -1,2;]; % NNW, 16
    
dir24 = [0,3;
    1,3;
    2,3;
    3,3;
    3,2;
    3,1;
    3,0;
    3,-1;
    3,-2;
    3,-3;
    2,-3;
    1,-3;
    0,-3;
    -1,-3;
    -2,-3;
    -3,-3;
    -3,-2;
    -3,-1;
    -3,0;
    -3,1;
    -3,2;
    -3,3;
    -2,3;
    -1,3;];

    

%% Initialize key vectors
placed = false(1,N);
linksToPlaced = zeros(1,N);

xyOut = xyIn;

%% Start at a link with the highest order
selectedInd = maxind;

%% move it to the center and mark it placed
[meanxy] = mean(xyIn,1);
xyOut(selectedInd,:) = round(meanxy);
placed(selectedInd) = true;

%% Update linksToPlaced
linksToPlaced = linksToPlaced + a(selectedInd,:);
linksToPlaced(placed) = 0; % ignore if already placed

%% Loop until all nodes placed
while any(~placed)
%% Select the next node
[maxLinksToPlaced] = max(linksToPlaced);
candidates = linksToPlaced==maxLinksToPlaced;
num_candidates = sum(candidates); 
if num_candidates>1
    % Choose among candidiates based on order
    links = linkCount(candidates);
    maxLinks = max(links);
    %Continuting candidates have maximal order
    candidates = candidates & (linkCount==maxLinks)';
    num_candidates = sum(candidates); 
    if num_candidates>1
        % Just pick one
        selectedInd = find(candidates,1,'first');
    else
        selectedInd = find(candidates,1,'first');
    end
else
    selectedInd = find(candidates,1,'first');
end


%% Place the selected node

% If 1/2 or more links are yet to be placed, we want to be towards the
% outside of the cloud.  
fracLeft = maxLinksToPlaced/linkCount(selectedInd);
if fracLeft>=0.5
    % prefer away from center of cloud to allow room for new links
    away = true;
else
    away = false;
end

% Find centroid of placed, linked points
placedLinked = placed & a(selectedInd,:);
cent_linked = mean(xyOut(placedLinked',:),1);

% Find centroid of all placed points
cent_placed = mean(xyOut(placed',:),1);

if away
    % Prefer to move away from centroid of all points, because the majority
    % of linkages are going to come from new points, and we want to have
    % room for those
    
    % pick one placed neigbor to be near, for now let's choose the lowest
    % order one
    [minLinks] = min(linkCount(placedLinked));
    bestNeighbor = find(linkCount==minLinks & placedLinked',1,'first');
    preferred_dir = xyOut(bestNeighbor,:)-cent_placed; 
    loc = xyOut(bestNeighbor,:);
    
else % not away
    % Prefer to be placed near centroid of linked points because most
    % linkages are already placed
    loc = round(cent_linked); 
    preferred_dir = [];
end

loc_final = placeme(loc,preferred_dir,placed);

% Update
xyOut(selectedInd,:) = loc_final;
placed(selectedInd) = true;
linksToPlaced = linksToPlaced + a(selectedInd,:);
linksToPlaced(placed) = 0; % ignore if already placed


        
end % end of while
    function loc_final = placeme(loc,preferred_dir,placed)
    % Choose a good final location near loc. if there is a preferred
    % direction, then the desired point is some distance in that direction
    % from the input loc.  The desired distance depends on the remaining
    % linkage order of the currently selected point.  
    
    if ~isempty(preferred_dir) && norm(preferred_dir)>0
        %Determine desired distance based on remaining node order
        desired_dist = linkCount(selectedInd)-linksToPlaced(selectedInd)+1;
        % Deterimine desired location
        loc = loc+preferred_dir/norm(preferred_dir)*desired_dist;
    end
    
    rounded_loc = round(loc);
    
    % Is something there?
    dirlevel = 8;
    dircount = 0;
    startdir = get_start_dir(preferred_dir,dirlevel);
    curdir = startdir; 
    
    base_loc = rounded_loc;
    cur_loc = base_loc;
 
    while ~isempty(intersect(xyOut(placed,:),cur_loc,'rows'))
        %keep looking if there is already a point there
        % Start in a direction, then move clockwise 
        
        % Increment dirlevel if necessary
        if dircount==dirlevel-1
            dirlevel = dirlevel+8;
            dircount = 0; 
            startdir = get_start_dir(preferred_dir,dirlevel);
        end
        
        cur_loc = new_loc(base_loc,dirlevel,dircount,startdir);
        if isnan(cur_loc)
            % error signal from new_loc, just put the point outside the
            % range of current points
            cur_loc =[max(xyOut(placed,1))+1,base_loc(2)];
            break
        end
        
        dircount = dircount+1;
    end

    loc_final = cur_loc;
    
    
        function cur_loc = new_loc(base_loc,dirlevel,dircount,startdir)
            % rotate from the starting direction by dircount units,
            % increment, and generate the new current location
            dirnow = startdir+dircount;
            if dirnow>dirlevel
                dirnow = dirnow-dirlevel;
            elseif dirnow==0
                dirnow=dirlevel;
            end
            if dirlevel==8
                cur_loc = base_loc+dir8(dirnow,:);
            elseif dirlevel==16
                cur_loc = base_loc+dir16(dirnow,:);
            elseif dirlevel == 24
                cur_loc = base_loc+dir24(dirnow,:);
            else
                % Give up and put it right on the spot, even though it will
                % be overlapping another point.
                cur_loc = NaN;
                %make_an_error
            end
        end
        function startdir = get_start_dir(preferred_direction,dirlevel)
            % get a starting direction at the preferred dirlevel
            if isempty(preferred_direction) || norm(preferred_direction)==0
                % choose randomly
                startdir = ceil(rand*dirlevel);
            else
                startdir = ceil(rand*dirlevel); 
            end
            
        end


    end % eof for placeme

end