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

Zeemeeuw 8

by Peter van der Walle

Status: Passed
Results: 4405 (cyc: 11, node: 1175)
CPU Time: 163.385
Score: 29110.8
Submitted at: 2010-11-14 12:03:37 UTC
Scored at: 2010-11-14 12:07:28 UTC

Current Rank: 2388th (Highest: 878th )
Based on: Zeemeeuw 7 (diff)
Basis for: Zeemeeuw 9 (diff)
Basis for: Zeemeeuw 9 (diff)

Comments
Please login or create a profile.
Code
function [thrustRow, thrustCol] = solver(chart, aIndex, bIndex, maxThrottle)

rowwind=chart(:,:,1);
colwind=chart(:,:,2);

[numrows,numcols]=size(rowwind);

ar = rem(aIndex-1, numrows) + 1;
ac = (aIndex - ar)/numrows + 1;

br = rem(bIndex-1, numrows) + 1;
bc = (bIndex - br)/numrows + 1;

% minr=max([1 min([ar-5 br-5])]);
% minc=max([1 min([ac-5 bc-5])]);
% maxr=min([numrows max([ar+5 br+5])]);
% maxc=min([numcols max([ac+5 bc+5])]);
% 
% rowwind=rowwind(minr:maxr,minc:maxc);
% colwind=colwind(minr:maxr,minc:maxc);
% 
% ar=ar-minr+1;
% br=br-minr+1;
% ac=ac-minc+1;
% bc=bc-minc+1;
% 
% [numrows,numcols]=size(rowwind);
% 
% aIndex=(ac-1)*numrows+ar;
% bIndex=(bc-1)*numrows+br;

[gridc,gridr]=meshgrid(1:numcols,1:numrows);

adist=(gridr-ar).^2+(gridc-ac).^2;
bdist=(gridr-br).^2+(gridc-bc).^2;

aenv=find(adist<2);
benv=find(bdist<2);

for i=1:2*maxThrottle+1
    for j=1:2*maxThrottle+1
        movecost(i,j)=abs(i-maxThrottle-1)+abs(j-maxThrottle-1);
    end
end
movecost(movecost>maxThrottle)=1e10;
[vc,vr]=meshgrid(-maxThrottle:maxThrottle,-maxThrottle:maxThrottle);

targetr=ar+rowwind(ar,ac);
targetc=ac+colwind(ar,ac);
done=zeros(numrows,numcols);
parent=done;
thr=ones(numrows,numcols)*1e10;
thr(aIndex)=0;
done(aIndex)=1;
p=aIndex;
tvr=0;
tvc=0;

while ~any(done(benv))

    i=max([1 targetr-maxThrottle]):min([numrows targetr+maxThrottle]);
    j=max([1 targetc-maxThrottle]):min([numcols targetc+maxThrottle]);
    ii=max([1 maxThrottle-targetr+2]):min([maxThrottle*2+1 maxThrottle*2+1-targetr-maxThrottle+numrows]);
    jj=max([1 maxThrottle-targetc+2]):min([maxThrottle*2+1 maxThrottle*2+1-targetc-maxThrottle+numcols]);

        update=~done(i,j).*(thr(i,j)>(movecost(ii,jj)+thr(p))).*(abs(vr(ii,jj)+tvr+rowwind(i,j))+abs(vc(ii,jj)+tvc+colwind(i,j))<maxThrottle+bdist(i,j)/3-2);
        thr(i,j)=update.*(movecost(ii,jj)+thr(p))+~update.*thr(i,j);
        parent(i,j)=update*p+~update.*parent(i,j);

    [m,p]=min(thr(:)+1e11*done(:));
    if ~parent(p)
        break;
    end
    besti = rem(p-1, numrows) + 1;
    bestj = (p - besti)/numrows + 1;
    
    r = rem(parent(p)-1, numrows) + 1;
    c = (parent(p) - r)/numrows + 1;
    tvr=besti-r;
    tvc=bestj-c;
    targetr=besti+tvr+rowwind(besti,bestj);
    targetc=bestj+tvc+colwind(besti,bestj);
    done(p)=1;
end


% and back home
thr=thr+bdist;
[m,p]=min(thr(:));

done=zeros(numrows,numcols);
parentback=done;

targetr = rem(p-1, numrows) + 1;
targetc = (p - targetr)/numrows + 1;

r = rem(parent(p)-1, numrows) + 1;
c = (parent(p) - r)/numrows + 1;

targetr=2*targetr-r+rowwind(p);
targetc=2*targetc-c+colwind(p);
done(p)=1;

while ~any(done(aenv))

    i=max([1 targetr-maxThrottle]):min([numrows targetr+maxThrottle]);
    j=max([1 targetc-maxThrottle]):min([numcols targetc+maxThrottle]);
    ii=max([1 maxThrottle-targetr+2]):min([maxThrottle*2+1 maxThrottle*2+1-targetr-maxThrottle+numrows]);
    jj=max([1 maxThrottle-targetc+2]):min([maxThrottle*2+1 maxThrottle*2+1-targetc-maxThrottle+numcols]);

        update=~done(i,j).*(thr(i,j)>(movecost(ii,jj)+thr(p)));
        thr(i,j)=update.*(movecost(ii,jj)+thr(p))+~update.*thr(i,j);
        parentback(i,j)=update*p+~update.*parentback(i,j);

        [m,p]=min(thr(:)+1e11*done(:));

        besti = rem(p-1, numrows) + 1;
        bestj = (p - besti)/numrows + 1;

    if ~parentback(p)
        r = rem(parent(p)-1, numrows) + 1;
        c = (parent(p) - r)/numrows + 1;
    else
        r = rem(parentback(p)-1, numrows) + 1;
        c = (parentback(p) - r)/numrows + 1;
    end
    targetr=2*besti-r+rowwind(besti,bestj);
    targetc=2*bestj-c+colwind(besti,bestj);
    done(p)=1;
end

[m,p]=min(thr(:)+adist(:));

tra=[];
turned=0;
while p
    tra(end+1)=p;
    if turned||~parentback(p)
        turned=1;
        p=parent(p);
    else
        p=parentback(p);
    end
end
tra=tra(end:-1:1);
trar = rem(tra-1, numrows) + 1;
trac = (tra - trar)/numrows + 1;

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

if length(tra)<2
    thrustRow=[];
    thrustCol=[];
else
    thrustRow = accelr-rowwind(tra(1:end-1));
    thrustCol = accelc-colwind(tra(1:end-1));
end

end