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

p16

by Rafal Kasztelanic

Status: Passed
Results: 4189 (cyc: 11, node: 1052)
CPU Time: 70.557
Score: 845.957
Submitted at: 2010-11-15 12:27:05 UTC
Scored at: 2010-11-15 12:32:28 UTC

Current Rank: 822nd (Highest: 1st )
Based on: Some say that his sweat can be used to clean precious metals (diff)

Comments
Peter van der Walle
15 Nov 2010
Nice one. This pushes the loop faster to the target.
Please login or create a profile.
Code
function [thrustRow, thrustCol] = solver(chart, aIndex, bIndex, maxThrottle)
maxThrottle = maxThrottle - 1;
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               = (1:nx);
y               = (1:ny)';
X               = x(ones(ny,1),:);
Y               = y(:,ones(nx,1));
p               = 1.16;
dist_to_B       = ((X - bx).^2 + (Y - by).^2).^p;
dist_to_A       = ((X - ax).^2 + (Y - ay).^2).^p;

slowdown        = maxThrottle+dist_to_B/4-2;

%maxIter         = 1170;
maxIter         = 1034;
INF             = 100000;

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

y_dir           = 2*(by > ay) - 1;
x_dir           = 2*(bx > ax) - 1;
fuel            = Inf(ny,nx);
fuel(aIndex)    = 0;
fuel_to_reverse = fuel;
xvel            = zeros(ny,nx);
yvel            = xvel;
checked         = xvel;
previous_stop   = xvel;
it              = 0;
min_fuel        = 0;
[cost_to_B cost_to_B_idx] = min(fuel_to_reverse(:) + dist_to_B(:));

while (  min_fuel <= cost_to_B  && ~all(checked(:)) && it < maxIter)
    it                      = it + 1;
    metrix                  = fuel + checked + dist_to_B_w;
   [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_reacheable            = (i_thrust <= maxThrottle).*(abs(i_new_vy+y_winds)+abs(i_new_vx+x_winds)<slowdown);
    i_optimum               = i_fuel < fuel;
    i_impr_tf               = i_reacheable & i_optimum;
    i_impr_idx              = find(i_impr_tf);
    i_new_vx_impr           = i_new_vx(i_impr_idx);
    i_new_vy_impr           = i_new_vy(i_impr_idx);
    i_fuel_impr             = i_fuel  (i_impr_idx) ;
    i_fuel_to_reverse_impr  = i_fuel_impr + ...
        0.2*abs(i_new_vy_impr).*(i_new_vy_impr*y_dir>0) + ...
        0.2*abs(i_new_vx_impr).*(i_new_vx_impr*x_dir>0) ;
    xvel           (i_impr_idx) = i_new_vx_impr;
    yvel           (i_impr_idx) = i_new_vy_impr;
    fuel           (i_impr_idx) = i_fuel_impr;
    fuel_to_reverse(i_impr_idx) = i_fuel_to_reverse_impr;
    previous_stop  (i_impr_idx) = i_p;
    if i_impr_tf(cost_to_B_idx)
        [cost_to_B cost_to_B_idx] = min(fuel_to_reverse(:) + dist_to_B(:));
    else
        [cost_to_B_new cost_to_B_idx_new] = min(fuel_to_reverse(i_impr_idx) ...
            + dist_to_B(i_impr_idx));
        
        if cost_to_B_new<cost_to_B
            cost_to_B = cost_to_B_new;
            cost_to_B_idx = i_impr_idx(cost_to_B_idx_new);
        end
    end
    checked(i_impr_idx)     = 0; %false;
    checked(i_p)            = INF; %true;
end

fuel                    = fuel + dist_to_B;
[cost_to_A cost_to_A_idx] = min(fuel(:) + dist_to_A(:));

checked                 = checked*0;
return_previous_stop    = checked;

it                      = 0;
min_fuel                = 0;

while ( min_fuel < cost_to_A &&  ~all(checked(:)) && it < maxIter )
    
    it                  = it + 1;
    metrix              = fuel + checked + dist_to_A_w; %****
    [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_reacheable        = i_thrust <= maxThrottle;
    i_optimum           = i_fuel < fuel;
    i_impr_tf           = i_reacheable & i_optimum;
    i_impr_idx          = find(i_impr_tf);
    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;
    if i_impr_tf(cost_to_A_idx)
        [cost_to_A cost_to_A_idx] = min(fuel(:) + dist_to_A(:));
    else
        [cost_to_A_new cost_to_A_idx_new] = min(fuel(i_impr_idx) ...
            + dist_to_A(i_impr_idx));
        if cost_to_A_new<cost_to_A
            cost_to_A = cost_to_A_new;
            cost_to_A_idx = i_impr_idx(cost_to_A_idx_new);
        end
    end
    checked(i_impr_idx) = 0;
    checked(i_p)        = INF;
    
end

cost_to_A           = fuel + dist_to_A;
[dummy,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);

xspeed              = diff(xpos);
yspeed              = diff(ypos);

xdrive              = diff([0; xspeed]);
ydrive              = diff([0; yspeed]);

thrustCol           = xdrive - xw(1:end-1);
thrustRow           = ydrive - 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