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

2opt12

by Corbin Holland

Status: Passed
Results: 21802.2960
CPU Time: 68.3586
Score: 2180.35
Submitted at: 2005-05-18 13:07:16 UTC
Scored at: 2005-05-18 15:17:30 UTC

Current Rank: 986th
Basis for: 2opt13 (diff)

Comments
Corbin Holland
18 May 2005
removed optimization included in opt1-opt11 which removed t matrix from outer move dx dy calc...I thought this would be great and showed up in test suite as being better time wise...but submission generated worse results with this version...makes no
Corbin Holland
18 May 2005
sense to me but oh well
Please login or create a profile.
Code
function [dy,dx,mark,carry]=solver6(main,food,ants,scent)
rand(1,5);
i35=3:5;
i24=2:4;
i02=0:2;
dirx = [-1, 2, 2, 2,-1; 
         2,-1,-1,-1, 2;
         2, 0, 0, 0, 2;
         2, 1, 1, 1, 2;
         1, 2, 2, 2, 1];
diry = [-1,-1, 0, 1, 1;
        -1,-1, 0, 1, 1;
        -1,-1, 0, 1, 1;
        -1,-1, 0, 1, 1;
        -1,-1, 0, 1, 1];
% find reachable regions
BAD=main<0;
if BAD(7)||BAD(9)||BAD(17)||BAD(19)
    if BAD(7)
        BAD(1)=1;
        BAD(2)=BAD(2)||BAD(8);
        BAD(3)=BAD(3)||(BAD(8)&&BAD(9));
        BAD(6)=BAD(6)||BAD(12);
        BAD(11)=BAD(11)||(BAD(12)&&BAD(17));
    end
    if BAD(9)
        BAD(4)=BAD(4)||BAD(8);
        BAD(5)=1;
        BAD(10)=BAD(10)||BAD(14);
    end
    if BAD(17)
        BAD(16)=BAD(16)||BAD(12);
        BAD(21)=1;
        BAD(22)=BAD(22)||BAD(18);
    end
    if BAD(19)
        BAD(15)=BAD(15)||(BAD(9)&&BAD(14));
        BAD(20)=BAD(20)||(BAD(14));
        BAD(23)=BAD(23)||(BAD(17)&&BAD(18));
        BAD(24)=BAD(24)||(BAD(18));
        BAD(25)=1;
    end
    % modify current board based on reachable regions
    main(BAD)=-1;
    food(BAD)=0;
    scent(BAD)=0;
end
BAD(13)=1;
% setup game stats
scents=scent(scent>0);
maxscent=max(scents(:));
% mark this field
if (max(main(:)))
    mark=400-scent(13);
    scent(13)=400;
    init=0;
    hills=find(main>0);
    scent(hills)=1e7;
    food(hills)=0;
    if isempty(scents);maxscent=mark;end
elseif (maxscent==min(scents(:))) % init phase
    mark=maxscent-scent(13);
    scent(13)=maxscent;
    init=1;
elseif isempty(scents) % nothing is marked
    mark=98;
    scent(13)=scent(13)+98;
    maxscent=mark;
    init=1;
else
    mark=maxscent-1-scent(13);
    scent(13)=maxscent-1;
    init=0;
end
% look around for food
if max(food(:))<1 ||init % nothing found or no way home, search
    target=maxscent-scent;target(BAD)=-1e8;
    [y,x]=find(target==max(target(:)));
    if (numel(y)>1)
        r=ceil(rand*numel(y));
        y=y(r);
        x=x(r);
    end
    carry=food(13)>0;
    dx = dirx(x,y);
    if dx<2
        dy = diry(x,y);
        return;
    end;
    m(7,7)=0;
    m(y+i02,x+i02)=1;
    m=m(i35,i35);
    t=target(i24,i24).*m+m;
    [dy,dx]=find(t==max(t(:)));
    r=ceil(rand*numel(dy));
    dy=dy(r)-2;
    dx=dx(r)-2;
    return;
end;
if (food(13)>1)&&rand<.95 % sit on a lot of food, go home
    target=scent;target(BAD)=-1e8;
    [y,x]=find(target==max(target(:)));
    if (numel(y)>1)
        r=ceil(rand*numel(y));
        y=y(r);
        x=x(r);
    end
    carry=1;
    dx = dirx(x,y);
    if dx<2
        dy = diry(x,y);
        return;
    end;
    m(7,7)=0;
    m(y+i02,x+i02)=1;
    m=m(i35,i35);
    t=target(i24,i24).*m+m;
    [dy,dx]=find(t==max(t(:)));
    r=ceil(rand*numel(dy));
    dy=dy(r)-2;
    dx=dx(r)-2;
    return;
end;
if (food(13) >= 1) % sit on one food, build track

    lowfood=food;lowfood(scent>=scent(13))=0;   % remove all food from view with scents greater then ant is on
    scent(BAD) = -1e8;                          % gotta remove this so
    [yhome,xhome]=find(scent==max(scent(:)),1);   % find maximum scents in view
%     if (numel(yhome)>1)
%        max(abs(yhome-3),abs(xhome-3));
%        r=find(;
%        yhome=yhome(r);
%        xhome=xhome(r);
%     end
    carry=1;
    dhere=max(max(abs(yhome-3),abs(xhome-3)));  % calc distance to farthest max scent in view from the ant
    runs=numel(lowfood(lowfood(:)>0));          % calc how much food lies behind ant (on lesser scented squares)
    lowfood(i24,i24)=lowfood(i24,i24)*1e8;      % emphasize any lowfood on adjacent squares to ant

    while runs % fetch food behind
       
        % find the highest food source lying behind the ant (looking at adjacent squares with more emphasis)
        [y,x]=find(lowfood==max(lowfood(:))); % find maximum 
        if (numel(y)>1)
            r=ceil(rand*numel(y));
            y=y(r);
            x=x(r);
        end
        
        % If distance between lowfood square and farthest max scent in view from the ant is greater
        % then from the ant's square then we have found the one we are looking for. dx and dy are good to go
        if ( min(max(abs(yhome-y),abs(xhome-x))) <= dhere )
            lowfood(y,x)=0;runs=runs-1;
            continue;            
        end
        
        % If this point is reached then we have found the lowfood square we are lookin for
        dx = dirx(x,y);
        if dx<2
            dy = diry(x,y);
        else
            m(7,7)=0;
            m(y+i02,x+i02)=1;
            m=m(i35,i35);
            t=lowfood(i24,i24).*m+m;
            [dy,dx]=find(t==max(t(:)));
            r=ceil(rand*numel(dy));
            dy=dy(r)-2;
            dx=dx(r)-2;
        end
        
        carry=0;
        return; % now we are set to move to the lesser scented food source
        
    end
    
    % If this point is reached then either no lowfoods were found or the lowest scented food
    % is the one we are standing on!
    [y,x]=find(scent==max(scent(:)));
    if (numel(y)>1)
       r=ceil(rand*numel(y));
       y=y(r);
       x=x(r);
    end
    dx = dirx(x,y);
    if dx<2
       dy = diry(x,y);
       return;
    end;
    m(7,7)=0;
    m(y+i02,x+i02)=1;
    m=m(i35,i35);
    t=scent(i24,i24).*m+m;
    [dy,dx]=find(t==max(t(:)));
    r=ceil(rand*numel(dy));
    dy=dy(r)-2;
    dx=dx(r)-2;
    return;
    
end;

% food in view ..but NOT on middle square
target=max(food-ants,0);target(BAD)=-1e8;
[y,x]=find(target==max(target(:)));
if (numel(y)>1)
    r=ceil(rand*numel(y));
    y=y(r);
    x=x(r);
end
carry=0;
dx = dirx(x,y);
if dx<2
    dy = diry(x,y);
    return;
end;
m(7,7)=0;
m(y+i02,x+i02)=1;
m=m(i35,i35);
t=target(i24,i24).*m+m;
[dy,dx]=find(t==max(t(:)));
r=ceil(rand*numel(dy));
dy=dy(r)-2;
dx=dx(r)-2;