2005-05-18 09:00:00 UTC

# The Early Ant catches the worm I

Status: Passed
Results: 19207.2085
CPU Time: 119.538
Score: 1940.15
Submitted at: 2005-05-18 16:59:12 UTC
Scored at: 2005-05-19 04:12:47 UTC

Current Rank: 485th

Hannes Naud
18 May 2005
Early discovery courtesy of Cobus
Code
```function [dy,dx,mark,carry]=solver(main,food,ants,scent)
%17497.91 @29.20
rand(1,5);
% find reachable regions
r=main~=-1;
if r(1);r(1)=r(7);end;
if r(2);r(2)=max(r(7),r(8));end;
if r(3);r(3)=max(r(7),max(r(8),r(9)));end;
if r(4);r(4)=max(r(8),r(9));end;
if r(5);r(5)=r(9);end;
if r(10);r(10)=max(r(9),r(14));end;
if r(15);r(15)=max(r(9),max(r(14),r(19)));end;
if r(20);r(20)=max(r(14),r(19));end;
if r(25);r(25)=r(19);end;
if r(24);r(24)=max(r(18),r(19));end;
if r(23);r(23)=max(r(17),max(r(18),r(19)));end;
if r(22);r(22)=max(r(17),r(18));end;
if r(21);r(21)=r(17);end;
if r(16);r(16)=max(r(12),r(17));end;
if r(11);r(11)=max(r(7),max(r(12),r(17)));end;
if r(6);r(6)=max(r(7),r(12));end;
% modify current board based on reachable regions
% setup game stats
HILLS=(main==1);hills=find(HILLS);
seehills=length(hills);
food(hills)=0;
scents=scent(scent>0);
maxscent=max(scents(:));
minscent=min(scents(:));
if ((maxscent==29) & (minscent==1))
maxscent=1;
end
if (main(13)==1) % If I am ON an anthill
mark=400-scent(13);
init=0;
if (maxscent<200)
[dx,dy]=pathfinder(scent==minscent);
carry=0;
return
end
elseif (isempty(scents)) % nothing is marked
mark=29;
init=1;
elseif (maxscent==minscent)
init=1;
if (maxscent==1)
mark=29-scent(13);
else
mark=maxscent-scent(13);
end
else
mark=max(max(scent(2:4,2:4)))-1; % Edit by JJN to prevent ant going back to init when walking away from nest and marking 100 99 99
if (mark<28)  % Naive test for init phase
mark=maxscent-2;
end
mark=mark-scent(13);
init=0;
if ((minscent==1) &(max(scent(2:4,2:4)==1)))
dx=0;
dy=0;
carry=0;
return
end
end
scent(hills)=1e6;
%if (seehills)
%  for counter=1:length(hills)
% 	scent(min(max(hills(counter)-6:hills(counter)-4,1),25))=2e6;
%   scent(min(max(hills(counter)+4:hills(counter)+6,1),25))=2e6;
%   scent(min(max([hills(counter)-1 hills(counter)+1],1),25))=2e6;

%scent(min(max(hills(counter)-12:hills(counter)-8,1),25))=1e6;
%   scent(min(max(hills(counter)+8:hills(counter)+12,1),25))=1e6;
% 	scent(min(max([hills(counter)-2 hills(counter)+2],1),25))=1e6;
%	scent(min(max([hills(counter)-7 hills(counter)+7],1),25))=1e6;
%	scent(min(max([hills(counter)+3 hills(counter)-3],1),25))=1e6;
%end
if isempty(scents);
maxscent=mark;
end

if ((~init) & maxscent<30 & ~(seehills))
[dx,dy]=pathfinder(scent);
carry=1;
return
end

% look around for food
if (~any(food(:))|init) % nothing found or no way home, search

%     if ~init & (min(scent(main>=0))==scent(13)-mark) & scent(13)~=mark% standing on a local minimum;
%         target=scent;
%         [dx,dy]=pathfinder(target);
%         mark=scent(3+dx,3+dy)-(scent(13)-mark);
%         carry=1;
%         return
%     end
if init
if (seehills)
[dx,dy]=pathfinder(main);
carry=0;
return
end
end
scent(13)=scent(13)+mark;
local=(main(2:4,2:4)~=-1)&(ants(2:4,2:4)==0)&(scent(2:4,2:4)==0);
[r,c]=find(local);
if length(r)
score=zeros(length(r),1);
for counter=1:length(r)
score(counter)=5*sum(sum(scent(r(counter):r(counter)+2,c(counter):c(counter)+2)>0))+ 3*sum(sum(ants(r(counter):r(counter)+2,c(counter):c(counter)+2))) + (r(counter)==2) + (c(counter)==2);
end
j=randperm(length(r));
[m,i] = min(score(j));
dy=r(j(i))-2;
dx=c(j(i))-2;
carry=0;
return;
end
emph=ones(5);
emph(2:4,2:4)=1.1;
[dx,dy,x,y]=pathfinder(target.*emph);
carry=(~init) & (seehills==0);
return;
end;
if (scent(13)>0)&& (scent(13)<32)
j=[7 8 9 12 14 17 18 19];
i=find(scent(j)==scent(13));
i=j(i);
for counter=i
[dy,dx]=ind2sub([5 5],counter);
if max(scent(max(dy-1,1):min(dy+1,5),max(dx-1,1):min(dx+1,5)))<=scent(13)
dy=dy-3;
dx=dx-3;
carry=1;
return
end
end
end

if (food(13))
lfood=food(2:4,2:4);
lmain=main(2:4,2:4);
lscent=scent(2:4,2:4);
if lfood(5)>1
carry=1;
lscent(lscent==0)=-1e5;
lmax=max(lscent(:));
if (lmax==lscent(5))
[dx,dy]=pathfinder(scent);
return
else
[dy,dx]=find(lscent==lmax);
dx=dx(1)-2;
dy=dy(1)-2;
return
end
else % then food ==1
food(scent>=scent(13))=0;
if any(any(food))
[dx,dy]=pathfinder(food);
carry=0;
return
end
tscent=lscent;
tscent(lfood==0)=1e7;
tscent(lmain<0)=1e7;
lmin=min(tscent(:));
if ((lmin==tscent(5)) | maxscent<31) % run for home if trail is getting weak
carry=1;
lscent(lscent==0)=-1e5;
lmax=max(lscent(:));
if (lmax==lscent(5))
[dx,dy]=pathfinder(scent);
return
else
[dy,dx]=find(lscent==lmax);
dx=dx(1)-2;
dy=dy(1)-2;
return
end
else
carry=0;
%         if (scent(13)==mark) %test for scent=0
%            dy=0;
%            dx=0;
%            return
%         end
[dy,dx]=find(tscent==lmin);
dx=dx(1)-2;
dy=dy(1)-2;
return
end
end
end
scent(13)=scent(13)+mark;

% have seen food; not yet on it and not in init phase
[dx,dy,x,y]=pathfinder(target);
carry=0;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [dx,dy,x,y]=pathfinder(target)
target(13)=0;
v=max(target(:));[y,x]=find(target==v);
if (length(y)>1)
r=ceil(rand(1)*length(y));
y=y(r);
x=x(r);
end
if (y>1&y<5&x>1&x<5) % direct way
dy=y-3;
dx=x-3;
return;
end;
if ((y==1|y==5)&(x==1|x==5)) % corner
dy=(y-3)/2;
dx=(x-3)/2;
return;
end;
m(7,7)=0;
m(y:y+2,x:x+2)=1;
m=m(3:5,3:5);
t=target(2:4,2:4).*m+m;
v=max(t(:));[dy,dx]=find(t==v);
r=ceil(rand(1)*length(dy));
dy=dy(r)-2;
dx=dx(r)-2;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function [dx,dy,carry]=foodtrain(food,main,scent)
%lmax=max(max(scent(2:4,2:4));
if food(5)>1
scent(scent==0)=1e5;
lmax=max(scent(:));
if lmax==scent(5);
[dx,dy]=pathfinder(main)
else
[dx,dy]=find(scent==lmax);
dx=2-dx;
dy=2-dy;
end
carry=1;
return
else % then food ==1
tscent(food==0)=1e5;
tscent(main<0)=1e5;
lmin=min(tscent(:));
if (lmin==scent(5))
[dx,dy]=find(scent==lmax);
dx=2-dx;
dy=2-dy;
carry=0;
return
else
scent(scent==0)=1e5;
lmax=max(scent(:));
if lmax==scent(5);
[dx,dy]=pathfinder(main)
else
[dx,dy]=find(scent==lmax);
dx=2-dx;
dy=2-dy;
end
carry=1;
return
end
end

if (food(13)>1)&rand<.95 % sit on a lot of food, go home
[dx,dy,x,y]=pathfinder(target);
carry=1;
return;
end;
if (food(13) >= 1) % sit on one food, build track
target(13)=-1;
v=max(target(:));[yhome,xhome]=find(target==v);
lowscent=(scent<scent(13));
lowfood(5,5)=0;
lowfood(lowscent)=food(lowscent);
carry=1;
dhere=max(max(abs(yhome-3),abs(xhome-3)));
emph=ones(5);
emph(2:4,2:4)=1e8;
while (any(lowfood(:))) % fetch food behind
[dx,dy,x,y]=pathfinder(target);
dthere=min(max(abs(yhome-y),abs(xhome-x)));
if (dthere>dhere)
carry=0;
return;
end
lowfood(y,x)=0;
end
if (carry) % go home