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)

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

```