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

noodles 1

by Jan Langer

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)

Comments
Please login or create a profile.
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);