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

A little bit Better

by Daniel Guellmar

Status: Passed
Results: 26788 (cyc: 16, node: 870)
CPU Time: 2.465
Score: 5364.48
Submitted at: 2010-11-12 14:41:17 UTC
Scored at: 2010-11-12 14:42:17 UTC

Current Rank: 2182nd (Highest: 89th )

Comments
Please login or create a profile.
Code
function [thrustRow, thrustCol] = solver(chart, aIndex, bIndex, maxThrottle)
% Solver for Matlab contest fall 2010 (sailing boat)

% empty results
thrustRow = zeros(1000,1);
thrustCol = zeros(1000,1);

rowWind = chart(:,:,1);
colWind = chart(:,:,2);

% obtain bounds
[nR,nC] = size(rowWind);
[aRow, aCol] = ind2sub([nR,nC],aIndex);
[bRow, bCol] = ind2sub([nR,nC],bIndex);

% create possible throttle matrix
maxThrottledCombinations = maxThrottle*2+1;
tM = [reshape(repmat(-maxThrottle:maxThrottle,maxThrottledCombinations,1),[],1),...
      reshape(repmat(-maxThrottle:maxThrottle,1,maxThrottledCombinations),[],1)];
tM = tM(sum(abs(tM),2) < maxThrottle+1,:);
tM = [tM, sum(abs(tM),2)];  
tM = sortrows(tM,3);

goAhead = 1;
nTurns = 1;

% set initial position
Ri = aRow;
Ci = aCol;

% set initial velocity
vRi = 0;
vCi = 0;
vRm = 0;
vCm = 0;

% current destination, which changes to start postion if farway island was
% reached
cdR = bRow;
cdC = bCol;
bReached = 0;
optimaFailed = 0;
turndetected = 0; % means boat stoped (initial speed = 0)

wayPoints = zeros(1000,5);
wayPoints(1,1:2) = [aRow, aCol];
visitMap = zeros(size(rowWind));
visitMap(aRow,aCol) = 1;
I = 0;
dB = (Ri-bRow)^2 + (Ci-bCol)^2;

while (goAhead && nTurns <= 1000)
    
    % calc current distance to destination
    cDist = sqrt((cdR -Ri)^2 + (cdC - Ci)^2);
    
    if (cDist < 0.1)
       if bReached
           break;
       else
          bReached = 1;
       end
       cdR = aRow;
       cdC = aCol;
       cDist = sqrt((cdR -Ri)^2 + (cdC - Ci)^2);
    end
    
    nextsolution = 0;
    
    % catch not moving any more
    if (vRi==0 && vCi==0)
        if (turndetected==0)
            turndetected = 1;
        else
            turndetected = 0;
            nextsolution = 1;
        end        
    end
    
    
    % motor optimization
        
      vRM = vRi + rowWind(Ri,Ci) + tM(:,1);    
      vCM = vCi + colWind(Ri,Ci) + tM(:,2);
    
      RfM = Ri + vRM;
      CfM = Ci + vCM;
      
      % calculate the distance of the RfM/CfM to destination
      distVec = sqrt([RfM - cdR].^2 + [CfM - cdC].^2);
      
      % remove all combinations which bring us off the chart
      solutionMask = find(sum([ RfM>0, RfM<=nR, CfM>0, CfM<=nC],2)==4);
      cIdx = sub2ind([nR,nC],RfM(solutionMask),CfM(solutionMask));
      
      % remove all combinations which bring us to a point on card which was
      % already visited twice
      solutionMask = solutionMask(visitMap(cIdx)<3);
      cIdx = cIdx(visitMap(cIdx)<3);
      
      % initial Velocity at destination
      ivRM = vRM(solutionMask) + rowWind(cIdx);
      ivCM = vCM(solutionMask) + colWind(cIdx);
      sm2 = solutionMask((abs(ivRM)+abs(ivCM))<=maxThrottle);
      if (isempty(sm2))
         sm2 = solutionMask( (abs(ivRM)+abs(ivCM))==min((abs(ivRM)+abs(ivCM))));
      end
      
      if (isempty(sm2))
          optimaFailed = 1;
          break;
      end
      
      XX = sortrows([tM(sm2,:) distVec(sm2)],[4 3]);
      
      Iold = I;
      
      if ( nnz(distVec(sm2) < 0.001) || size(XX,1)<2 )
        I = 1;
      else        
        if (~nextsolution)
          [~,I] = min(sqrt((XX(:,3).^2 + XX(:,4).^2)));
        else
          [~,I] = min(XX(:,3));
          if (I==Iold)
              % try to get off randomly
              I = randi(size(XX,1));
              %[~,I] = min(XX(:,4));
          end
        end
      end
      
     %scatter(XX(:,3),XX(:,4));hold on
     %scatter(XX(I,3),XX(I,4),'filled'); hold off
     
     
     vRm = XX(I,1);      
     vCm = XX(I,2);
     
    % end motor optimization
    
    
    
    
    % final row/col velocity and position
    vRf = vRi + rowWind(Ri,Ci) + vRm;
    vCf = vCi + colWind(Ri,Ci) + vCm;
    Rf = Ri + vRf;
    Cf = Ci + vCf;
    
    %fprintf('old point: %4d %4d --> new point: %4d %4d\n',Ri,Ci,Rf,Cf);
    
    
    % check bounds
    %if (Rf<1 || Rf>nR || Cf<1 || Cf>nC)
    %    % fprintf('ups, we left the chart in turn %d.\n',nTurns);
    %    break;
    %    goAhead = 0;
    %else
    %   %fprintf('Round %d: %4d %4d %4d %4d %4d %4d %4d %4d\n',...
    %   %         nTurns,rowWind(Ri,Ci),colWind(Ri,Ci),vRm,vCm,vRf,vCf,Rf,Cf); 
    %end
    
    
    % save to result vector
    thrustRow(nTurns) = vRm;
    thrustCol(nTurns) = vCm;
    
    % set data for the next turn    
    Ri = Rf;
    Ci = Cf;
    vRi = vRf;
    vCi = vCf;
    nTurns = nTurns + 1;
    
    % Verify if this is the closest point to B
    if ((Rf-bRow)^2 + (Cf-bCol)^2) < dB
         dB = ((Rf-bRow)^2 + (Cf-bCol)^2);    
    end
    
    
    dA = (Rf-aRow)^2 + (Cf-aCol)^2;    
    wayPoints(nTurns,:) = [Rf Cf dA dB myScores(dA,dB,thrustRow,thrustCol)]; 
    visitMap(Rf,Cf) = visitMap(Rf,Cf) + 1;
end


%plot(wayPoints(:,5))
%fprintf('final score: %6d\n',wayPoints(nTurns,5));
if (optimaFailed)
    %fprintf('failed\n');
    thrustRow = [];
    thrustCol = [];
else
  % shorten vectors
  thrustRow = thrustRow(1:nTurns-1);
  thrustCol = thrustCol(1:nTurns-1);    
end

end

function score = myScores(dA, dB, tR, tC)
  score = dB + dA + sum(abs(tR)) + sum(abs(tC));
end