Finish 2010-11-17 12:00:00 UTC

Old trick

by Amitabh Verma

Status: Passed
Results: 4045 (cyc: 9, node: 1895)
CPU Time: 67.965
Score: 815.718
Submitted at: 2010-11-17 06:27:24 UTC
Scored at: 2010-11-17 06:29:31 UTC

Current Rank: 150th (Highest: 1st )
Based on: deadmau5 unhooked (diff)
Basis for: some chords (diff)
Basis for: tricky (diff)
Basis for: deadmau5 unhooked (diff)
...and 7 others.

Comments
Please login or create a profile.
Code
function [thrustRow, thrustCol] = npp(chart, aIndex, bIndex, maxThrottle)
[thrustRow, thrustCol,score] = nickelfelpeter(chart, aIndex, bIndex, maxThrottle);
if score<21
return;
else
[thrustRow1, thrustCol1,score1] = zeemcv(chart, aIndex, bIndex, maxThrottle);
if score1 < score
    thrustCol = thrustCol1;
    thrustRow = thrustRow1;
end
end
end

function [thrustRow, thrustCol, score] = nickelfelpeter(chart, aIndex, bIndex, maxThrottle)
ONEHUNDRED = 100;
rand(1,14);
y_winds         = chart(:,:,1);
x_winds         = chart(:,:,2);
[ny,nx]         = size(x_winds);
ay              = rem(aIndex-1, ny) + 1;
ax              = (aIndex - ay)/ny  + 1;
by              = rem(bIndex-1, ny) + 1;
bx              = (bIndex - by)/ny  + 1;
X = repmat(1:nx, ny,1);
Y = repmat((1:ny)', 1,nx);

dist_to_B       = ((X - bx).^2 + (Y - by).^2).^1.15;
dist_to_A       = ((X - ax).^2 + (Y - ay).^2).^1.155;

dist_to_B_w     = dist_to_B*1e-4;
dist_to_A_w     = dist_to_A*1e-4;

xvel            = 0*x_winds;
fuel            = xvel+ONEHUNDRED;
fuel(aIndex)    = 0;
yvel            = xvel;
checked         = xvel;
previous_stop   = xvel;
min_fuel        = 0;
cost_to_B = dist_to_B(aIndex);
zoon = nx*ny*[10 0.37];
ziter = [500 700] .* (1-0.05*rand(1,2));
sf = [0.31 0.19];

for i = 1:2
    
    SDB_tf = dist_to_B(:)<=zoon(i);
    SDB_idx = find(SDB_tf);
    
    SDBchecked = checked(SDB_tf);
    SDBfuel = fuel(SDB_tf);
    SDBdist_to_B_w = dist_to_B_w(SDB_tf);
    SDBdist_to_B = dist_to_B(SDB_tf);
    SDBxvel = xvel(SDB_tf);
    SDByvel = yvel(SDB_tf);
    SDBX = X(SDB_tf);
    SDBY = Y(SDB_tf);
    SDBprevious_stop = previous_stop(SDB_tf);
    
    slowdown = maxThrottle+SDBdist_to_B*sf(i);
    
    it = 0;
    metrix                  = SDBfuel + SDBchecked + SDBdist_to_B_w;
    while (  min_fuel <= cost_to_B  && ~all(SDBchecked) && it < ziter(i))
        it                      = it + 1;
        
        [dummy,i_p]             = min(metrix);
        i_p_full                = SDB_idx(i_p);
        min_fuel                = SDBfuel(i_p);
        i_y                     = rem(i_p_full - 1,ny) + 1;
        i_x                     = (i_p_full - i_y)/ny  + 1;
        i_y_winds               = y_winds(i_p_full);
        i_x_winds               = x_winds(i_p_full);
        i_vy                    = SDByvel(i_p) + i_y_winds;
        i_vx                    = SDBxvel(i_p) + i_x_winds;
        i_new_vy                = SDBY - i_y;
        i_new_vx                = SDBX - i_x;
        i_thrust                = abs(i_new_vx - i_vx) + abs(i_new_vy - i_vy);
        i_fuel                  = i_thrust + min_fuel;
        i_impr_tf               = (i_thrust <= maxThrottle) & (abs(i_new_vy+i_y_winds)+abs(i_new_vx+i_x_winds)<slowdown) & (i_fuel < SDBfuel);
        i_impr_idx              = find(i_impr_tf);
        SDBchecked(i_p)            = ONEHUNDRED; %true;
        metrix(i_p)             = SDBfuel(i_p) + ONEHUNDRED + SDBdist_to_B_w(i_p);
        if isempty(i_impr_idx)
            continue;
        end
        i_fuel_impr             = i_fuel  (i_impr_idx) ;
        SDBxvel           (i_impr_idx) = i_new_vx(i_impr_idx);
        SDByvel           (i_impr_idx) = i_new_vy(i_impr_idx);
        SDBfuel           (i_impr_idx) = i_fuel_impr;
        SDBprevious_stop  (i_impr_idx) = i_p_full;
        cost_to_B = min(cost_to_B,min(SDBfuel(i_impr_idx) + SDBdist_to_B(i_impr_idx)));
        SDBchecked(i_impr_idx)     = 0; %false;
        metrix(i_impr_idx) = SDBfuel(i_impr_idx) + SDBdist_to_B_w(i_impr_idx);
    end
    
    fuel(SDB_tf) = SDBfuel;
    previous_stop(SDB_tf) = SDBprevious_stop;
    xvel(SDB_tf) = SDBxvel;
    yvel(SDB_tf) = SDByvel;
    
end

fuel                    = fuel + dist_to_B;
cost_to_A               = min(fuel(:) + dist_to_A(:));

checked(:)                 = 0;
return_previous_stop    = checked;

min_fuel                = 0;
metrix              = fuel + checked + dist_to_A_w; %****
while ( min_fuel < cost_to_A &&  ~all(checked(:)))
    
    [dummy,i_p]             = min(metrix(:)); %****
    min_fuel            = fuel(i_p); %****
    
    i_y                 = rem(i_p - 1,ny) + 1;
    i_x                 = (i_p - i_y)/ny  + 1;
    i_vy                = yvel(i_p) + y_winds(i_p);
    i_vx                = xvel(i_p) + x_winds(i_p);
    i_new_vy            = Y-i_y;
    i_new_vx            = X-i_x;
    i_thrust            = abs(i_new_vx - i_vx) + abs(i_new_vy - i_vy);
    i_fuel              = i_thrust + min_fuel;
    i_impr_tf           = i_thrust <= maxThrottle & i_fuel < fuel;
    checked(i_p)            = 100; %true;
    metrix(i_p) = fuel(i_p) + 100 + dist_to_A_w(i_p);
        i_impr_idx          = find(i_impr_tf);
    if isempty(i_impr_idx)
        continue;
    end
    fuel                (i_impr_idx) = i_fuel(i_impr_idx);
    xvel                (i_impr_idx) = i_new_vx(i_impr_idx);
    yvel                (i_impr_idx) = i_new_vy(i_impr_idx);
    return_previous_stop(i_impr_idx) = i_p;
    cost_to_A = min(cost_to_A,min(fuel(i_impr_idx) + dist_to_A(i_impr_idx)));
    checked(i_impr_idx) = 0;
    metrix(i_impr_idx) = fuel(i_impr_idx) + dist_to_A_w(i_impr_idx);
end

cost_to_A           = fuel + dist_to_A;
[score,min_fuel]        = min(cost_to_A(:));
indices             = zeros(nx*ny,1);
indices(1)          = min_fuel(1);
next_move           = return_previous_stop(indices(1));
k                   = 1;
[indices, k] = while_next_move(indices, k, next_move, return_previous_stop);
next_move           = previous_stop(indices(k));
[indices, k] = while_next_move(indices, k, next_move, previous_stop);
indices             = indices(k:-1:1);

ypos                = rem(indices - 1, ny) + 1;
xpos                = (indices - ypos)/ny + 1;
xw                  = x_winds(indices);
yw                  = y_winds(indices);

thrustCol           = diff([0; diff(xpos)]) - xw(1:end-1);
thrustRow           = diff([0; diff(ypos)]) - yw(1:end-1);

end

function [indices, k] = while_next_move(indices, k, next_move, previous_stop)

while(next_move)
    k               = k + 1;
    indices(k)      = next_move;
    next_move       = previous_stop(next_move);
end

end

function [thrustRow, thrustCol,score] = zeemcv(chart, aIndex, bIndex, maxThrottle)
winds           = chart(:,:,1)*1i + chart(:,:,2);
[ny,nx]         = size(winds);
winds           = winds(:);
ay              = rem(aIndex-1, ny) + 1;
ax              = (aIndex - ay)/ny  + 1;
az              = ay*1i + ax;
by              = rem(bIndex-1, ny) + 1;
bx              = (bIndex - by)/ny  + 1;
bz              = by*1i + bx;
x               = (1:nx);
y               = (1:ny)';
Z               = reshape(bsxfun(@plus,y*1i,x),[],1);
Z2B             = Z - bz;        
dist_to_B       = conj(Z2B).*Z2B;
max_dist_to_B   = nx^2+ny^2;
fract_d2B       = dist_to_B/(max_dist_to_B + 1);
Z2A             = Z - az;
dist_to_A       = conj(Z2A).*Z2A;
max_dist_to_A   = max_dist_to_B;
fract_d2A       = dist_to_A/(max_dist_to_A + 1);
checked         = fract_d2B;
previous_stop   = zeros(ny*nx,1);
INF             = 100000;
min_fuel        = 0;
zoonB = dist_to_B < 5;
zoonA = dist_to_A < 5;
p = aIndex;
checked(p) = INF;
target = Z(p) + winds(p);
tvz = 0;
it=0;
md2B = (maxThrottle-2)+dist_to_B*0.25;
zwind = Z + winds;
fuel            = INF*ones(ny*nx,1);
fuel(aIndex)    = 0;

while ~any(checked(zoonB)>1)
    it=it+1;
    zp = Z - target;
    totalT  = abs(real(zp)) + abs(imag(zp));
    boxp = totalT <=maxThrottle; % & rowT<=maxThrottle & ~checked;
    new_fuel = totalT + min_fuel;
    update = boxp & new_fuel < fuel;
    T = zwind(update) + (tvz-target); % zp + tvz + winds;
    update(update) = abs(real(T)) + abs(imag(T)) < md2B(update);
    fuel(update) = new_fuel(update);
    previous_stop(update) = p;
    [~,p]                = min(fuel + checked);
    min_fuel               = fuel(p);
    bestz = Z(p);
    z = Z(previous_stop(p));
    tvz = bestz - z;
    target = bestz + tvz + winds(p);
    checked(p) = INF;
end

fuel                    = fuel + dist_to_B;
[~,p]                   = min(fuel);

checked                 = fract_d2A;
checked(p)              = Inf;
return_previous_stop    = zeros(ny*nx,1);
target = 2*Z(p)-Z(previous_stop(p))+winds(p);

min_fuel                = fuel(p);

while ~any(checked(zoonA)>1)
    zp = Z - target;
    totalT  = abs(real(zp)) + abs(imag(zp));
    boxp = totalT <=maxThrottle; 
    new_fuel = totalT + min_fuel;
    update = boxp & new_fuel < fuel;
    fuel(update) = new_fuel(update);
    return_previous_stop(update) = p;
    [~,p]                = min(fuel + checked);
    min_fuel               = fuel(p);
    bestz = Z(p);
    if ~return_previous_stop(p)
        z = Z(previous_stop(p));
    else
        z = Z(return_previous_stop(p));
    end
    target = 2*bestz -z + winds(p);
    checked(p) = INF;
end

[score,p] = min(fuel+dist_to_A);
tra=[ny, nx]*0;
k=0;
turned=false;
while p
    k=k+1;
    tra(k)=p;
    if turned||~return_previous_stop(p)
        turned=true;
        p=previous_stop(p);
    else
        p=return_previous_stop(p);
    end
end
tra=tra(k:-1:1);
trar = rem(tra-1, ny) + 1;
trac = (tra - trar)/ny + 1;

accelr=diff([0 diff(trar)]);
accelc=diff([0 diff(trac)]);

if length(tra)<2
    thrustRow=[];
    thrustCol=[];
else
    w = winds(tra(1:end-1)).';
    thrustRow = accelr-imag(w);
    thrustCol = accelc-real(w);
end

end