2010-11-17 12:00:00 UTC

# Some say that his sweat can be used to clean precious metals

by Magnus S

Status: Passed
Results: 4231 (cyc: 11, node: 1042)
CPU Time: 70.51
Score: 854.321
Submitted at: 2010-11-15 11:56:33 UTC
Scored at: 2010-11-15 12:00:07 UTC

Current Rank: 837th (Highest: 1st )
Based on: NFP dead mouse (diff)
Basis for: deadmau5 unhooked (diff)
Basis for: sometimes things get complicated (diff)
Basis for: deadmau5 unhooked (diff)
...and 6 others.

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));
dist_to_B       = (X - bx).^2 + (Y - by).^2;
dist_to_A       = (X - ax).^2 + (Y - ay).^2;

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
```