Finish 2005-05-18 09:00:00 UTC

The Early Ant catches the worm I

by Hannes Naud

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

Comments
Hannes Naud
18 May 2005
Early discovery courtesy of Cobus
Please login or create a profile.
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
BAD=(r==0);
main(BAD)=-1;
food(BAD)=0;
scent(BAD)=0;
% 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
scent(BAD)=0;
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
   target=(main==0).*(maxscent-scent)-BAD-ants;
   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
ants(BAD)=0;
target=max(food-ants,0)-BAD;
[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
   target=scent;target(BAD)=0;target=target-BAD;%target=(main~=-1).*scent-BAD;
   [dx,dy,x,y]=pathfinder(target);
   carry=1;
   return;
end;
if (food(13) >= 1) % sit on one food, build track
   target=scent;target(BAD)=0;target=target-BAD;%target=(main~=-1).*scent-BAD;
   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
      target=lowfood.*emph-BAD;
      [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
      target=scent;target(BAD)=0;target=target-BAD;%target=(main~=-1).*scent-BAD;
      [dx,dy,x,y]=pathfinder(target);
   end
   return;
end;