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

495b05225bceac364552d8b36f6f56a3a9c03544 (1 again)

by William Wu

Status: Passed
Results: 323235 (cyc: 13, node: 508)
CPU Time: 24.563
Score: 323552.0
Submitted at: 2012-11-01 08:04:51 UTC
Scored at: 2012-11-01 17:43:35 UTC

Current Rank: 1728th (Highest: 31st )

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

n = length(wts);
frame_width = max(xyIn(:,1)) - min(xyIn(:,1));
frame_height = max(xyIn(:,2)) - min(xyIn(:,2));

KE_threshold = 1;
elec_constant = -300; 
hooke_constant = 0.05;
time_step = 1; 
damping = 0.85; 
n1 = 20;
n2 = 60;
y1 = 60;
y2 = 60;
if (n>=n2)
    max_iters = y2;
elseif (n<n1)
    max_iters = y1;
else
    max_iters = ((y2-y1)/(n2-n1))*(n - n1) + y1;
end
max_iters = 1;

velocities = zeros(n,2); 
positions = xyIn; 

iter = 0;
positions_prev = positions;
KE_prev = Inf;
KE_best = Inf;
positions_best = positions;
while iter < max_iters
    iter = iter + 1;
    KE_total = 0;
    for i=1:n, 
        net_force = [0,0];
        for j=[1:i-1 i+1:n]
            difference_vector = positions_prev(j,:) - positions_prev(i,:);
            r = norm(difference_vector,2);
            unit_vector_i_to_j = difference_vector/norm(difference_vector);
            net_force = net_force + elec_constant*(wts(i)*wts(j))*unit_vector_i_to_j/r^2; 
            if 1==a(i,j) 
                net_force = net_force + hooke_constant*norm(difference_vector)*unit_vector_i_to_j;
            end
        end
        velocities(i,:) = time_step*net_force*damping/wts(i); 
        positions(i,:) = positions_prev(i,:) + time_step*velocities(i,:);
        KE_total = KE_total + wts(i)*norm(velocities(i,:))^2;
    end
    positions_prev = positions;
    if (KE_total > KE_prev)
        time_step = time_step/2;
    end
    KE_prev = KE_total;
    if (KE_total < KE_best)
       KE_best = KE_total;
       positions_best = positions;
    end
    if (KE_total < KE_threshold)
        break;
    end
end

rescaling_ratio_scalar = 1;
rescaling_ratio_mult_increase = 2;

large_frame_height = max(positions(:,2)) - min(positions(:,2));
large_frame_width = max(positions(:,1)) - min(positions(:,1));

max_rescaling_iters = 5;
iter = 0
while iter < max_rescaling_iters    
    iter = iter + 1;
    positions_rescaled_rounded(:,1) = round((rescaling_ratio_scalar*frame_width/large_frame_width)*(positions_best(:,1) - mean(positions_best(:,1))));
    positions_rescaled_rounded(:,2) = round((rescaling_ratio_scalar*frame_height/large_frame_height)*(positions_best(:,2) - mean(positions_best(:,2))));
    n_new = length(unique(positions_rescaled_rounded,'rows'));
    if n > n_new
        rescaling_ratio_scalar = rescaling_ratio_scalar*rescaling_ratio_mult_increase;
    else
        break;
    end
end
if n > n_new
    xyOut = xyIn;
else
    xyOut = positions_rescaled_rounded;
end

end