CaptainNeedsSleep

function [thrustRow, thrustCol] = solver(chart, aIndex, bIndex, maxThrottle)

[nr,nc,dummy] = size(chart);
rw = reshape(chart(:,:,1),nr,nc);                % row winds 
cw = reshape(chart(:,:,2),nr,nc);                % colum winds
sp = aIndex;  [spr,spc]=ind2sub([nr nc],sp);     % start 
ep = bIndex;  [epr,epc]=ind2sub([nr nc],ep);     % end

%-- make a throttle matrix
mxt = maxThrottle;
thr = [-mxt:mxt]'*ones(1,2*mxt+1);
thc = ones(2*mxt+1,1)*[-mxt:mxt];
th  = [thr(:)';thc(:)'];
id  = find(sum(abs(th))<=mxt); th=th(:,id);       % possible throttles at any
X1  = [0.4 0.6 0.7]'*ones(1,3);
X2  = ones(3,1)*[0.4 0.6 0.7];
X   = [X1(:)';X2(:)'];
W   = ones(1,9);

score0=1e30; done=0; isc=1; nsc=0;                % loop over a number of possibilities
while ~done,                                      % and we pick the best until no more
   ni  = 1; tR=[]; tC=[];                         % improvement
   zz  = []; for kk=1:9, zz=[zz kk*ones(1,W(kk))]; end;
   ix  = zz(ceil(rand*length(zz)));
   x1  = X(1,ix); x2 = X(2,ix);
  
   [tR,tC,ri,ci,vRi,vCi,ni,dA] = trackpath(epr,epc,spr,spc,0,0,rw,cw,th,ni,tR,tC,x1,x2);
   [tR,tC,ri,ci,vRi,vCi,ni,dB] = trackpath(spr,spc,ri,ci,vRi,vCi,rw,cw,th,ni,tR,tC,x1,x2);
   score = dA + dB + sum(abs(tR)) + sum(abs(tC));
   if score<score0,
     score0 = score; dA0 = dA; dB0 = dB; VV=sum(abs(tR)) + sum(abs(tC));
     thrustRow = tR;
     thrustCol = tC;
     nsc=0; W(ix)=W(ix)+1; 
    else 
     nsc=nsc+1;
    end;
    isc = isc+1; 
    done=(isc>44 | nsc>18); 
 end;  
% [dA0 dB0 VV]
 return;


function [tR,tC,ri,ci,vRi,vCi,ni,dT] = trackpath(tr,tc,ri,ci,vRi,vCi,rw,cw,th,ni,tR,tC,x1,x2)

 done=(ni>999);                                  % check if already done
 [nr,nc] = size(rw);                             % get dimensions
 ts = sum(abs(th));                              % throttle used for each possible move
 di = (ri-tr)^2 + (ci-tc)^2;                     % initial distance to target
 
 while ~done,                                    % start tracking loop

   dRw = rw(ri,ci); vR=vRi+dRw;                  % movement without throttle
   dCw = cw(ri,ci); vC=vCi+dCw;                  % movement without throttle
   vRp = vR + th(1,:);                           % add possible throttles
   vCp = vC + th(2,:);                           % add possible throttles
   
   rn  = ri + vRp;                               % possible next positions                           
   cn  = ci + vCp;                                
   
   %-- eliminate those that go out of board
   
   id = find(rn>0 & rn<=nr & cn>0 & cn<=nc);     % possible moves
   len = length(id);                             % 
   if len==0,                                    % cannot move, stop here
      done = 1;
   else                                          % can still move
     dn  = (rn(id)-tr).^2 + (cn(id)-tc).^2;      % distances
     ts0 = find(ts(id)==0);                      % a move without using throttle
     if isempty(ts0)                             % not possible
       ts0 = len+1; dn(ts0)=1e30;
     end;
   
     %-- if zero throttle brings us closer, use
     
     choice = pickstep(di,dn,ts(id),ts0,x1,x2);     
     di = dn(choice);
     choice = id(choice);
   
   %-- move to new square, update variables
     rin = rn(choice);
     cin = cn(choice);
     pi = sub2ind([nr nc],rin,cin);
     vRi = vRp(choice);
     vCi = vCp(choice);
     tR=[tR; th(1,choice)];
     tC=[tC; th(2,choice)];
   
     if rin==ri & cin==ci, done=1; else ri=rin; ci=cin; end;  
     ni   = ni+1;
end;
done = done | (ni>999) | (di<=15);  %
end;
dT = di;
return;




function choice = pickstep(di,dn,ts,ts0,x1,x2)
   
if dn(ts0)<di & rand>x1,
   choice=ts0;    
else
   if dn(ts0)<di, dn(ts0)=1e30;  end;         % make sure this one doesn't get picked!
   jd=find(dn<di);                            % which ones get closer
              
   if ~isempty(jd) & rand>x2,                 % find the one with least thrust
       
 [mnv,loc] = min(ts(jd));      choice = jd(loc);
   elseif rand>0.1                            
      [mnv,choice] = min(dn);                 % the one gets closest      
   else
      choice = ceil(rand*length(ts));
   end;  
end;
return;