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

ideogram

by Jack Snoeyink

Status: Passed
Results: 26902.4123
CPU Time: 101.792
Score: 2693.53
Submitted at: 2005-05-18 16:54:53 UTC
Scored at: 2005-05-19 02:09:46 UTC

Current Rank: 1378th
Based on: bedlam (diff)

Comments
Jack Snoeyink
18 May 2005
final hopeless attempt to improve bedlam
Please login or create a profile.
Code
function [dy,dx,mark,carry] = solver(main,food,ants,scent)
%SOLVER The ant brain.
%   
%  INPUTS: (all 5x5 matrices, the ant is located at the center)
%  main  -- anthills (1), impassable regions (-1), and open space (0)
%  food  -- number of sugar cubes
%  ant   -- number of ants (always be at least 1 at (3,3))
%  scent -- strength of chemical scent (decreases by one each time interval)
% 
%  OUTPUTS: (all scalars)
%  dy    -- delta in rows (-1 is up, 0 no move, 1 is down)
%  dx    -- delta in columns (-1 is left, 0 no move, 1 is right)
%  mark  -- scent left by the ant, any integer between 0 and 100
%  carry -- logical indicating if the ant will carry one unit of food or not

% lookup tables for when we convert the 5x5 to row vectors
% rand added to distance to break ties
dist = [2.81,2.48,2.01,2.43,2.86, 2.42,1.41,1.01,1.40,2.40, 2.03,1.04,0,1.02,2.02, 2.41,1.43,1.00,1.42,2.44, 2.85,2.45,2,2.47,2.83];
mdist = [2,2,2,2,2, 2 1 1 1 2, 2 1 0 1 2, 2 1 1 1 2, 2,2,2,2,2];
dirx = [-1,-1,-1,-1,-1, -1,-1,-1,-1,-1, 0,0,0,0,0, 1,1,1,1,1, 1,1,1,1,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];
go1  = [1 1 2 3 3,  1 1 2 3 3,  4 4 0 5 5, 6 6 7 8 8, 6 6 7 8 8];
go2  = [7 7 8 9 9,  7 7 8 9 9, 12 12 13 14 14, 17 17 18 19 19, 17 17 18 19 19];
nhbr = [7    12     8    17     9    18    14    19;
     8     9     7    12    14    19    17    18;
     9     8    14    19     7    18    12    17;
    12    17     7     8    18     9    19    14;
    14     9    19     8    18     7    17    12;
    17    12    18    19     7     8    14     9;
    18    17    19    12    14     9     7     8;
    19    18    14    17     9     8    12     7];
 
nhbr8 = [7,8,9,12,14,17,18,19];
%7 12 17   1 4 6 
%8    18   2   7
%9 14 19   3 5 8

reach = [ 1  2  3  6 11 99; %7
          2  3  4  4  4 99; %8
          3  4  5 10 15 99; %9
          6 11 16 16 16 99;%12
         10 15 20 20 20 99;%14
         11 16 21 22 23 99;%17
         22 23 24 24 24 99;%18
         15 20 25 24 23 99];%19

mark = 0;
carry = main(13)<1 && food(13)>1;
dx = 0; 
dy = 0;
n = main(nhbr8)>=0;
if ~any(n(:))
    return
end
nn = reach(n,:);
a = sort(nn(:));
n1 = nhbr8(n);
n2 = [n1 a(diff(a)~=0)'];
n2 = n2(main(n2)>-1);
n3 = [13 n2];

toi = n1(ceil(rand*length(n1))); % default: move randomly

hills = n3(main(n3)==1);
if (~isempty(hills)) 
    mark = 100-dist(hills(1));
else
    [m,i] = max(scent(n2));
    if m>0
        mark = m - dist(n2(i)) - scent(13);
    else 
        dx = dirx(toi);
        dy = diry(toi);
        return
    end
end

food(main>0) = 0; % ignore food at anthills or on rocks
if (food(13) > 0) % food; shall I carry?
    if scent(13) > 20
        down = n2(scent(n2)<scent(13));
        if ~isempty(down)
            fa = food-ants/1.5;
            [m,i] = max(fa(down));
            toi = down(i);
            if m > food(13) + 2*mdist(toi)-3 % back up if more available
                carry = false;
                g = go2(toi);
                if main(g) == -1
                    n = nhbr(go1(toi),:);
                    n(main(n)==-1) = [];
                    if isempty(n)
                        toi = 13;
                    else
                        toi = n(1);
                    end
                end
                dx = dirx(toi);
                dy = diry(toi);
                return
            end
        end
    end
    carry = main(13)<1;
    if (~isempty(hills))
        [m,i] = min(dist(hills));
        toi = hills(i(1)); % closest hill to go to.
        mark = 0;
    else
        m = max(scent(n2)); % any beacons?
        if (m > 0)
            s = n2(scent(n2)==m);
            [m,i] = min(dist(s));
            toi = s(i(1)); % head toward closest large
            mark = 0;
        end
    end
else
    fa = food-ants/1.5; % don't ignore food carried by other ants
    f = n2(fa(n2)>0);
    if ~isempty(f)
        if numel(f)==1
            toi = f;
        else
            [m,i] = max(fa(f) - 2*mdist(f) - scent(f)/100); % find closest food (pref lower elevation for ties
            toi = f(i(1));
        end
    else
        if rand*ants(3,3) < 2
            s = n2(scent(n2) <= min(scent(n2))+ sum(ants(:)));
            toi = s(ceil(rand*length(s)));
        end
    end

end

g = go2(toi);
if main(g) == -1
    n = nhbr(go1(toi),:);
    n(main(n)==-1) = [];
    if isempty(n)
        toi = 13;
    else
        toi = n(1);
    end
end
dx = dirx(toi);
dy = diry(toi);