%% Ants on a Log puzzle simulation
% This simulation places a number of ants at random locations on a log. The
% ants march along, bumping into eachother until they all fall off. The
% average amount of time it takes for all the ants to fall off is
% calculated.
%
% Mar 13 '15
% Jay Brady

Nants = 25; % number of ants
L = 100;    % length of the log
nruns = 100;  % number of trials for averaging

timetofinish = nan(1,nruns);
for r = 1:nruns
    % set initial ant locations
    ants = randperm(L); 
    ants = ants(1:Nants);
    
    % set initial ant directions (1 right, -1 left)
    directions = randi(2,size(ants)) - 1;
    directions(directions == 0) = -1;
    
    colors = rand(size(ants));
    figure(1);
    scatter(ants, zeros(size(ants)), 1, colors);
    
    % at each timestep
    for t=0:0.005:10000
        % keep ant locations sorted (helps when checking collisions)
        [ants, I] = sort(ants);
        directions = directions(I);
        colors = colors(I);
        
        if isempty(ants) % ants all fell off
            break;
        elseif length(ants) == 1 % only 1 ant left
            ants = ants + directions./2;
            if ants > L || ants < 0
                timetofinish(r) = t;
                break;
            end
        end
        
        % each timestep, each ant moves 1/2 position
        ants = ants + directions./2;
        
        % check if any ants collide or fall off the edge
        numants = length(ants);
        for i=2:numants 
            if ants(i) == ants(i-1) % if ants collide, switch directions
                directions(i) = -directions(i);
                directions(i-1) = -directions(i-1);
            end
            if ants(i) > L || ants(i) < 0 % if an ant falls off, remove it
                ants(i) = [];
                directions(i) = [];
                colors(i) = [];
                numants = numants-1;
            end
            if i+1 > numants
                break;
            end
        end
        
        % plot ants
        scatter(ants, zeros(size(ants)), 50, colors, 'filled');
        caxis([0 1]);
        axis([0 100 -1 1]);
        pause(.05);
    end
end
% print average time to finish
mean(timetofinish)