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

Last Twilight

by Michael C.

Status: Passed
Results: 5947 (cyc: 10, node: 801)
CPU Time: 32.706
Score: 5976.84
Submitted at: 2012-11-02 15:57:51 UTC
Scored at: 2012-11-02 16:01:29 UTC

Current Rank: 1571st (Highest: 33rd )

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

p = polyfit(xyIn(:,1),xyIn(:,2),1);
dist_from_line = abs(p(1)*xyIn(:,1) - xyIn(:,2) + p(2));

% N = inf(3,1);
% xyTest = cell(3,1);

if std(dist_from_line) < 0.1
    failed = true;
%     xyTest{1} = xyIn;
    xyOut = xyIn;
else
%     [xyTest{1} failed] = solver_main(a,xyIn,wts);
    [xyOut failed] = solver_main(a,xyIn,wts);
%     if ~failed
%         N(1) = numKnotsOriginal(xyTest{1},a);
%     end
end

if failed || size(unique(xyOut,'rows'),1) < numel(wts) 
% for ii = 1:2
    rand_size = ceil(sqrt(numel(wts))+10)^2;
    rand_index = 1:rand_size;
    rand_index = sortrows([rand_index', rand(rand_size,1)],2);
    rand_index = rand_index(1:numel(wts),1);
    [x_rand,y_rand] = ind2sub([sqrt(rand_size) sqrt(rand_size)],rand_index);
    xyNew = ([x_rand,y_rand]-sqrt(rand_size)/2);
%     [xyTest{ii+1} failed] = solver_main(a,xyNew,wts);
    [xyOut failed] = solver_main(a,xyNew,wts);
%     if size(unique(xyTest{ii+1},'rows'),1) == numel(wts) && ~failed;
%         N(ii+1) = numKnotsOriginal(xyTest{ii+1},a);
%     end 
end

% if all(N==inf);
if size(unique(xyOut,'rows'),1) < numel(wts)
    xyOut = xyIn;
%     disp('All Methods Failed')
else
%     [junk best_i] = min(N);
% %     disp(best_i)
%     xyOut = xyTest{best_i};    
end
% disp(N)
end

function [xyOut failed] = solver_main(a, xyIn, wts)

failed = false;

xyOut = xyIn*100;

[junk1 b junk2] = unique(a,'rows');
bad_rows = setdiff(1:81,b);
% % Copyright 2012 The MathWorks, Inc.
% figure,
% [X,Y] = gplot(a,xyIn);
% line(X,Y,'Color','r','Marker','o');
% for ii = 1:length(xyIn)
%    text(xyIn(ii,1)+0.1,xyIn(ii,2)+0.1,num2str(ii));
% end

% keyboard;

n_connections = sum(a,2);

singles = find(n_connections == 1);
single_hub = zeros(size(singles));
for ii = 1:length(singles)
    single_hub(ii) = find(a(singles(ii),:));
end
single_hub = unique(single_hub);

valid_solution = false;
last_valid = xyOut;
for loop_i = 1:16

    %     [N nKnots_per_point]= numKnots(xyOut,a);
    %     [junk sort_i] = sortrows([nKnots_per_point, n_connections, wts'],[-1 -2 -3]);
%     if mod(loop_i,2) == 0
%        [junk sort_i] = sortrows([n_connections, wts'],[-1 -2]);
%     else
         D = sqdistance(xyOut');
         D(a==0) = 0;
         D_total = sum(D,2);
         [junk sort_i] = sortrows([D_total, n_connections, wts'],[-1 -2 -3]);
%     end

    xyOut = Fix_Singles(single_hub,singles,a,xyOut);
    
    for ii = 1:length(sort_i)
        if n_connections(sort_i(ii)) > 1
            all_connections = find(a(sort_i(ii),:));
            mean_x = mean(xyOut(all_connections,1));
            mean_y = mean(xyOut(all_connections,2));
            if ismember(sort_i(ii),bad_rows)
                mean_y = mean_y + 1;
            end
            xyOut(sort_i(ii),:) = [mean_x, mean_y];
        end
    end

    if size(unique(round(xyOut),'rows'),1) == numel(wts)
        valid_solution = true;
        last_valid = xyOut;
%         last_index = loop_i;
    elseif size(unique(round(xyOut*2),'rows'),1) == numel(wts)
        xyOut = xyOut*2;
        valid_solution = true;
        last_valid = xyOut;
%         last_index = loop_i;
    end
%     figure,
%     [X,Y] = gplot(a,xyOut);
%     line(X,Y,'Color','r','Marker','o');
%     for ii = 1:length(xyOut)
%         text(xyOut(ii,1)+0.1,xyOut(ii,2)+0.1,num2str(ii));
%     end

end

xyOut = Fix_Singles(single_hub,singles,a,xyOut);
% for ii = 1:length(single_hub)
%     connected_singles = intersect(find(a(single_hub(ii),:)),singles);
%     for jj = 1:length(connected_singles)
%         xyOut(connected_singles(jj),:) = xyOut(single_hub(ii),:) + round([sind(45*jj), cosd(45*jj)]);
%     end
% end

if ~valid_solution
    xyOut = xyIn;
    failed = true;
    return
elseif size(unique(round(xyOut),'rows'),1) < numel(wts)
    xyOut = last_valid;
end

xyOut = FinishingTouches(wts,xyIn,xyOut,single_hub,singles,a);

% figure,
% [X,Y] = gplot(a,xyOut);
% line(X,Y,'Color','r','Marker','o');
% for ii = 1:length(xyOut)
%     text(xyOut(ii,1)+0.1,xyOut(ii,2)+0.1,num2str(ii));
% end


end

function xyOut = FinishingTouches(wts,xyIn,xyOut,single_hub,singles,a)
[junk max_wt_i] = max(wts);
offset = round(xyIn(max_wt_i,:) - xyOut(max_wt_i,:));
xyOut = xyOut + repmat(offset,numel(wts),1);

% xy_Orig = xyOut;
% xyOut = round(xyOut);
total_dist_moved = inf(20,1);
for shrink_i = 1:20

    xy_Test = round(xyOut*(shrink_i/20));

    xy_Test = Fix_Singles(single_hub,singles,a,xy_Test);

    if size(unique(xy_Test,'rows'),1) == numel(wts)
        total_dist_moved(shrink_i) = sum(moved_dist(xyIn,xy_Test));
    end
end

[junk min_dist_i] = min(total_dist_moved);
xyOut = round(xyOut*(min_dist_i/20));
xyOut = Fix_Singles(single_hub,singles,a,xyOut);
end

function xyOut = Fix_Singles(single_hub,singles,a,xyOut)

for ii = 1:length(single_hub)
    connected_singles = intersect(find(a(single_hub(ii),:)),singles);
    for jj = 1:length(connected_singles)
        xyOut(connected_singles(jj),:) = xyOut(single_hub(ii),:) + round([sind(45*jj), cosd(45*jj)]);
    end
end

end

% 
function d = moved_dist(XYold,XYnew)

% This function calculates the distance each node has moved based on the
% starting and ending positions of each node.

dXY = XYnew-XYold;

d = sqrt(dXY(:,1).^2 + dXY(:,2).^2);
end

function D = sqdistance(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