2010-11-17 12:00:00 UTC

# noodles 1

Status: Passed
Results: 61009 (cyc: 11, node: 626)
CPU Time: 141.477
Score: 16055.4
Submitted at: 2010-11-11 00:20:11 UTC
Scored at: 2010-11-11 00:23:40 UTC

Current Rank: 2318th (Highest: 1st )
Basis for: noodles 2 (diff)

Code
```function [thrustRow, thrustCol] = solver(chart, aIndex, bIndex, maxThrottle)
% Basic solver, does nothing

% Copyright 2010 The MathWorks, Inc.

sz = [size(chart,1) size(chart,2)];

[ay,ax] = ind2sub(sz,aIndex);
[by,bx] = ind2sub(sz,bIndex);

[ty1,tx1,vy1,vx1,by,bx] = oneway(chart,ay,ax,by,bx,0,0,maxThrottle);
[ty2,tx2,vy2,vx2,by,bx] = oneway(chart,by,bx,ay,ax,vy1,vx1,maxThrottle);

thrustRow = [ty1 ty2];
thrustCol = [tx1 tx2];

function [ty,tx,vy,vx,by,bx] = oneway(chart,ay,ax,by,bx,vy,vx,maxThrottle)
rows = size(chart,1);
cols = size(chart,2);

% --------------------------------------
% dijkstra

Dis = inf(rows,cols);
Vel = zeros(rows,cols,2);
Vel(ay,ax,:) = [vy vx];
Dis(ay,ax) = 0;

% create differences to neighbors
r = 3;
nb = ones(r*2+1);
nb(r+1,r+1) = 0;
r = (size(nb,1)-1)/2;
[nby,nbx] = find(nb);
nb = [nby-r-1 nbx-r-1];

% do the dijkstra
Q = [ay ax];
while numel(Q)
% pop
x = Q(1,2);
y = Q(1,1);
Q = Q(2:end,:);

% neighbors
for j=1:size(nb,1)
nx = nb(j,2)+x;
ny = nb(j,1)+y;

if nx < 1 || ny < 1 || nx > cols || ny > rows
continue;
end

my = ny-y-Vel(y,x,1)-chart(y,x,1);
mx = nx-x-Vel(y,x,2)-chart(y,x,2);

% check motor crash
mtot = abs(my)+abs(mx);
if mtot > maxThrottle
continue;
end

% better path?
if Dis(ny,nx) > Dis(y,x)+mtot
Vel(ny,nx,1) = Vel(y,x,1)+chart(y,x,1)+my;
Vel(ny,nx,2) = Vel(y,x,2)+chart(y,x,2)+mx;
Dis(ny,nx) = Dis(y,x)+mtot;
Q(end+1,:) = [ny nx];
end
end
end

% --------------------------------------
% extract motor power

ty = [];
tx = [];

% find best turning spot
Dis = Dis ...
+ repmat(abs((1:cols)  - bx),rows,1) ...
+ repmat(abs((1:rows)' - by),1,cols);
[dummy,targetIndex] = min(Dis(:));
[by,bx] = ind2sub([rows cols],targetIndex);
vy = Vel(by,bx,1);
vx = Vel(by,bx,2);

% walk the path backwards
curPos = [by; bx];
while curPos(1) ~= ay || curPos(2) ~= ax
x = curPos(2);
y = curPos(1);
prevPos = curPos - permute(Vel(y,x,:),[3 1 2]);
py = prevPos(1);
px = prevPos(2);
m = Vel(y,x,:)-chart(py,px,:)-Vel(py,px,:);
ty(end+1) = m(1);
tx(end+1) = m(2);
curPos = prevPos;
end

% reverse motor power b/c of backwards walk
ty = fliplr(ty);
tx = fliplr(tx);
```