Finish 1999-06-10 00:00:00 UTC

serial_rovers4

by Ram Rao

Status: Passed
Results: 17.963% unexplored
CPU Time: 15.493
Score: 436.717
Submitted at: 1999-06-10 16:45:26 UTC
Scored at: 2000-03-16 16:51:51 UTC

Current Rank: 1010th
Based on: serial_rovers3 (diff)

Comments
Please login or create a profile.
Code
function inst = serial_rovers4(map, p)
%LOLOMOV  For the Mathworks contest
%
%         Since LOLOMOV2 weren't better (it was way better on
%         the test suite) we try to decrease the random checks
%         to 0.07 and refuse to follow a rover (it is a stupid
%         observed behaviour to to go behind another Rover).
%         Also we slightly randomize starting direction.

%  Hmm...I really need to come up with a new algorithm...leading
%  by simply tweaking Anders' code is hardly fair :-)
%
%  I'm sure this will be beaten, but it gives a few hints about
%  optimizing code.
%
%  Now both subfunctions are inlined and I am (almost) running
%  out of ideas for improvements apart from improving the
%  algorithm itself.  But it's late here and it's about time
%  someone else beat me.
%   
%                                       --Peter

%---------------------------------------------------------------
%
%        SECTION 1 - LOOP TO GENERATE INSTRUCTIONS
%

%   Here we define the constants in this function and, since
%   we're filling inst using a FOR loop we preallocate it with
%   zeros for performance.

numberofrovers = 5;
numberoftimesteps = 500;
r=p(:,1); c=p(:,2); d=p(:,3);
inst=zeros(numberoftimesteps,numberofrovers);
passed=zeros(4,50,50);

left  = [ 4 1 2 3 ];
right = [ 2 3 4 1 ];

%   Loop over time, then over each rover generating instructions
%   for each rover


% flipped for loops so each rover moves sequentially
for rover = 1:numberofrovers
   map( r(rover),c(rover) ) = 0;

   for t = 1:numberoftimesteps


      row = r(rover);
      col = c(rover);
      dir = d(rover);

      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      % First improvement: Don't call nextmove if unserveyed
      % ahead!  But it seems to give better results if it is
      % tried sometimes :-) And randomize starting direction a
      % little.

      if (t==1) & (rand<0.6)
         action = 2+(rand>.5);
     elseif (rand>0.07) & ...
             (map(min(max(row-(dir==1)+(dir==3),1),50),...
                   min(max(col+(dir==2)-(dir==4),1),50)) == 1)
         action = 1;
      else
      
         %--- begin nextmove inlined ---------------------------
	 %
	 %
	 % NEXTMOVE subfunction which generates the next move
	 % based on the current position and direction

	 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	 % Check so that we are not following a rover

%	 if     (dir==1) & any(((row-1==r)|(row-2==r)) & (col==c) & (dir==d))
%	    action = 2+(rand>.5);
%	 elseif (dir==2) & any((row==r) & ((col+1==c)|(col+2==c)) & (dir==d))
%	    action = 2+(rand>.5);
%	 elseif (dir==3) & any(((row+1==r)|(row+2==r)) & (col==c) & (dir==d))
%	    action = 2+(rand>.5);
%	 elseif (dir==4) & any((row==r) & ((col-1==c)|(col-2==c)) & (dir==d))
%	    action = 2+(rand>.5);
%	 else
if (passed(dir,row,col)==1 & rand>.9)
   action=2+(rand>.5);
   else
	    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	    %   nesw = north,east,south,west
	    %   look at the squares around the current position
	    
	    nesw = [ -1 ; -1 ; -1 ; -1 ];
	    
	    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	    % Second improvement: count number of unsurveyed far
            % ahead but weigh those close heavier.
	    
	    if row > 1
	       z = map(row-1:-1:1,col)';
	       k = min(find([z,-1]==-1))-1;
	       if k>0, nesw(1) = max(cumsum(z(1:k)./(1:k))); end
	    end
	    if col < 50
	       z = map(row, col+1:50);
	       k = min(find([z,-1]==-1))-1;
	       if k>0, nesw(2) = max(cumsum(z(1:k)./(1:k))); end
	    end
	    if row < 50
	       z = map(row+1:50, col)';
	       k = min(find([z,-1]==-1))-1;
	       if k>0, nesw(3) = max(cumsum(z(1:k)./(1:k))); end
	    end
	    if col > 1
	       z = map(row,col-1:-1:1);
	       k = min(find([z,-1]==-1))-1;
	       if k>0, nesw(4) = max(cumsum(z(1:k)./(1:k))); end
	    end

	    %   frbl = front,right,back,left
	    %   reorient according to the direction I'm facing
	    
	    frbl = nesw([dir:end 1:dir-1]);
	    if max(frbl) == 0
	       if ~(col==1 & dir==4) & ~(col==50 & dir==2) & ...
	  	  ~(row==1 & dir==1) & ~(row==50 & dir==3) & ...
	          (map(row-(dir==1)+(dir==3), col+(dir==2)-(dir==4)) == 0),
		  action = 1;
	       else
		  action = 2+(rand>.5);
	       end
	    else
	       pd = max(frbl);
	       if (frbl(1)==pd)
		  action=1;
	       elseif (frbl(2)<pd) & (frbl(4)==pd)
		  action=2;
	       elseif (frbl(2)==pd) & (frbl(4)<pd)
		  action=3;
	       else
		  action=2+(rand>.5);
	       end
	    end

	 end

	 %
	 %--- end nextmove inlined ----------------------------
      
      end

      inst(t,rover) = action;

      %--- begin update_state inlined --------------------------
      %
      %        SECTION 2 - UPDATE_STATE SUBFUNCTION
      %
      %        UPDATE_STATE subfunction updates the current
      %        state to the new positions after each action.

      % update state
      switch action
      case 1 % move forward
         passed(d(rover),row,col)=1;
         switch d(rover)
         case 1
            row = row - (row ~= 1);
         case 2
            col = col + (col ~= 50);
         case 3
            row = row + (row ~= 50);
         case 4
            col = col - (col ~= 1);
         end
      case 2 % turn left
         d(rover) = left(d(rover));
      case 3 % turn right
         d(rover) = right(d(rover));
      end

      % If it is a valid region, update the state, otherwise, it
      % doesn't move.
      if map(row,col) ~= -1
         r(rover)=row; c(rover)=col; map(row,col) = 0;
      end

      %
      %--- end update_state inlined ----------------------------

   end
end