x = cell2mat(importdata('input.txt'));

E       = 200*(x=='E');   % Elves
G       = 200*(x=='G');   % Goblins
W       = x=='#';         % Walls
nElves  = length(find(E));

attackPowerElves  = 3;
[round,Enew,Gnew] = doBattle(E,G,W,attackPowerElves);
disp((round-1)*(sum(sum(Enew))+sum(sum(Gnew)))) % Part 1

while 1
    attackPowerElves = attackPowerElves + 1;
    [round,Enew,Gnew] = doBattle(E,G,W,attackPowerElves);
    if length(find(Enew))==nElves
        disp((round-1)*(sum(sum(Enew))+sum(sum(Gnew)))) % part 2
        break
    end
end

function d = distanceToTarget(r,c,Z)
d       = zeros(size(Z,1),size(Z,2));
d(r,c)  = 1;
iter    = 0;
while 1
    iter = iter + 1;
    dnew = d + iter*( ([zeros(1,size(d,2));d(1:end-1,:)]|...
        [d(2:end,:);zeros(1,size(d,2))]|...
        [d(:,2:end),zeros(size(d,1),1)]|...
        [zeros(size(d,1),1),d(:,1:end-1)])...
        & ~Z & ~d);
    if isequal(d,dnew)
        break
    else
        d = dnew;
    end
end

d(d==0)= 9999;
d(r,c) = 0;
end

function [round,E,G] = doBattle(E,G,W,attackPowerElves)

round = 0;
battleFinished = false;
while ~battleFinished
    round = round + 1;
    % Determine order for this round
    [order_c,order_r] = find(G'|E');

    for unit = 1:length(order_c)
        row = order_r(unit);
        col = order_c(unit);
        newRow = row;
        newCol = col;

        if E(row,col)
            % current unit is an Elf, target the Goblins
            T = G;
        elseif G(row,col)
            % current unit is a Goblin, target the Elves
            T = E;
        else
            % The unit that was here at the start of the round has died,
            % skip this unit.
            %disp('Dead units cannot take turns')
            continue
        end

        if ~any(T(:))
            disp('No more targets found. Battle finished.')
            battleFinished = true;
            break
        end

        % Determine squares that are in range:
        z_occ = E | G | W;
        z_occ(row,col) = false;

        inRange = ([zeros(1,size(T,2));T(1:end-1,:)]|...
            [T(2:end,:);zeros(1,size(T,2))]|...
            [T(:,2:end),zeros(size(T,1),1)]|...
            [zeros(size(T,1),1),T(:,1:end-1)])...
            & ~z_occ;

        if inRange(row,col)
            % Unit already in range, no movement required.
        else
            if ~any(inRange(:))
                % Unit not in range and no places to go, end turn
                %disp('No squares in range, ending turn.')
                continue
            else
                % move

                % Determine distance to all squares that are in range:
                [idx_c,idx_r]   = find(inRange');
                minSteps        = inf;
                bestTarget_r    = 0;
                bestTarget_c    = 0;
                bestD           = 0;
                for i=1:length(idx_r)
                    % exclude current unit position from obstacles send to
                    % distance function
                    z               = E|G|W;
                    z(row,col)      = false; % exclude own location as obstacle
                    d               = distanceToTarget(idx_r(i),idx_c(i),z);

                    min_distance    = min([d(row-1,col),d(row+1,col),d(row,col-1),d(row,col+1)]);

                    if min_distance<minSteps
                        minSteps        = min_distance;
                        bestTarget_r    = idx_r(i);
                        bestTarget_c    = idx_c(i);
                        bestD           = d;
                    end
                end
                if minSteps == 9999
                    %disp('No path found, ending turn.')
                    continue
                end

                % Take step towards [bestTarget_r,bestTarget_c]

                if bestD(row-1,col)==minSteps
                    if E(row,col)
                        E(row-1,col) = E(row,col);
                        E(row,col)   = 0;
                        newRow       = row-1;
                        newCol       = col;
                    else
                        G(row-1,col) = G(row,col);
                        G(row,col)   = 0;
                        newRow       = row-1;
                        newCol       = col;
                    end
                elseif bestD(row,col-1)==minSteps
                    if E(row,col)
                        E(row,col-1) = E(row,col);
                        E(row,col)   = 0;
                        newRow       = row;
                        newCol       = col-1;
                    else
                        G(row,col-1) = G(row,col);
                        G(row,col)   = 0;
                        newRow       = row;
                        newCol       = col-1;
                    end
                elseif bestD(row,col+1)==minSteps
                    if E(row,col)
                        E(row,col+1) = E(row,col);
                        E(row,col)   = 0;
                        newRow       = row;
                        newCol       = col+1;
                    else
                        G(row,col+1) = G(row,col);
                        G(row,col)   = 0;
                        newRow       = row;
                        newCol       = col+1;
                    end
                elseif bestD(row+1,col)==minSteps
                    if E(row,col)
                        E(row+1,col) = E(row,col);
                        E(row,col)   = 0;
                        newRow       = row+1;
                        newCol       = col;
                    else
                        G(row+1,col) = G(row,col);
                        G(row,col)   = 0;
                        newRow       = row+1;
                        newCol       = col;
                    end
                else
                    disp('something went wrong here...')
                end

            end
        end
        % Fight:
        minHP = inf;
        enemy_r = 0;
        enemy_c = 0;
        if T(newRow-1,newCol)
            if T(newRow-1,newCol)<minHP
                minHP = T(newRow-1,newCol);
                enemy_r = newRow-1;
                enemy_c = newCol;
            end
        end
        if T(newRow,newCol-1)
            if T(newRow,newCol-1)<minHP
                minHP = T(newRow,newCol-1);
                enemy_r = newRow;
                enemy_c = newCol-1;
            end
        end
        if T(newRow,newCol+1)
            if T(newRow,newCol+1)<minHP
                minHP = T(newRow,newCol+1);
                enemy_r = newRow;
                enemy_c = newCol+1;
            end
        end
        if T(newRow+1,newCol)
            if T(newRow+1,newCol)<minHP
                minHP = T(newRow+1,newCol);
                enemy_r = newRow+1;
                enemy_c = newCol;
            end
        end

        if minHP==inf
            % No targets, end turn.
            continue
        end

        if E(enemy_r,enemy_c)
            E(enemy_r,enemy_c) = E(enemy_r,enemy_c) - 3;
            if E(enemy_r,enemy_c)<1
                E(enemy_r,enemy_c) = 0;
            end
        else
            G(enemy_r,enemy_c) = G(enemy_r,enemy_c) - attackPowerElves;
            if G(enemy_r,enemy_c)<1
                G(enemy_r,enemy_c) = 0;
            end
        end
    end
    if battleFinished
        break
    end
end
end