day15

local grid, units;
local function loadinput()
    grid, units = {}, {}
    for line in getinput():gmatch("[^\n]+") do
        local t = {}
        grid[#grid+1] = t
        for c in line:gmatch(".") do
            t[#t+1] = c
            if c == "E" or c == "G" then
                units[#units+1] = {kind = c, health = 200, x = #t, y = #grid}
            end
        end
    end
end

local function getunit(y, x)
    for _, unit in pairs(units) do
        if unit.y == y and unit.x == x and unit.health > 0 then
            return unit
        end
    end
end

local function drawgrid()
    for y = 1, #grid do
        local data = ""
        for x = 1, #grid[y] do
            if grid[y][x] == "E" or grid[y][x] == "G" then
                local unit = getunit(y, x) or {health = 0}
                data = data.." "..grid[y][x].."("..unit.health..")"
            end
        end
        print(table.concat(grid[y], "")..data)
    end
end

local function open(y, x)
    if not grid[y] then return false end
    return grid[y][x] == "."
end

local function priority(y1, x1, y2, x2)
    if y1 == y2 then return x1 < x2 end
    return y1 < y2
end

local function step(atk)
    for _, u in pairs(units) do
        u.moved = false
    end
    for y = 1, #grid do
        for x = 1, #grid[y] do
            local y = y
            local c = grid[y][x]
            if c == "E" or c == "G" then
                local gcount, ecount = 0, 0
                for y = 1, #grid do
                    for x = 1, #grid[y] do
                        if grid[y][x] == "E" then
                            ecount = ecount + 1
                        elseif grid[y][x] == "G" then
                            gcount = gcount + 1
                        end
                    end
                end
                if gcount == 0 or ecount == 0 then return "end" end
                local thisunit = getunit(y, x)
                if not thisunit.moved then
                    thisunit.moved = true
                    local enemy = (c == "E" and "G" or "E")
                    local adjacent = {}
                    local function checkneighbor(y, x)
                        if not grid[y] then return end
                        if grid[y][x] == enemy then
                            adjacent[#adjacent+1] = {y = y, x = x, unit = getunit(y, x)}
                        end
                    end
                    local function checkneighbors(y, x)
                        checkneighbor(y-1, x)
                        checkneighbor(y, x-1)
                        checkneighbor(y, x+1)
                        checkneighbor(y+1, x)
                    end
                    checkneighbors(y, x)
                    if #adjacent == 0 then
                        local targets = {}
                        local function addtarget(y, x)
                            if open(y, x) then
                                targets[#targets+1] = {y = y, x = x}
                            end
                        end
                        for _, u in pairs(units) do
                            if u.health > 0 and u.kind == enemy then
                                local Y, X = u.y, u.x
                                addtarget(Y+1, X)
                                addtarget(Y, X-1)
                                addtarget(Y, X+1)
                                addtarget(Y-1, X)
                            end
                        end
                        local paths = {}
                        for _, e in pairs(targets) do
                            local visited = {[y] = {[x] = true}}
                            local solution;
                            local stack = {{y = y, x = x}}
                            repeat
                                local newstack = {}
                                local function checkpos(y, x, p)
                                    if open(y, x) and (not visited[y] or not visited[y][x]) then
                                        local newpos = {y = y, x = x, parent = p}
                                        newstack[#newstack+1] = newpos
                                        visited[y] = visited[y] or {}
                                        visited[y][x] = true
                                        if y == e.y and x == e.x then
                                            solution = solution or newpos
                                        end
                                    end
                                end
                                for _, p in pairs(stack) do
                                    local y, x = p.y, p.x
                                    checkpos(y-1, x, p)
                                    checkpos(y, x-1, p)
                                    checkpos(y, x+1, p)
                                    checkpos(y+1, x, p)
                                end
                                stack = newstack
                            until solution or #stack == 0
                            if solution then
                                local list = {solution}
                                while list[1].parent do
                                    table.insert(list, 1, list[1].parent)
                                end
                                paths[#paths+1] = {path = list, target = e}
                            end
                        end
                        table.sort(paths, function(a, b)
                            if #a.path == #b.path then
                                return priority(a.target.y, a.target.x, b.target.y, b.target.x)
                            end
                            return #a.path < #b.path
                        end)
                        local path = paths[1]
                        if path then
                            local step = path.path[2]
                            grid[y][x] = "."
                            grid[step.y][step.x] = c
                            y, x = step.y, step.x
                            thisunit.y, thisunit.x = y, x
                            adjacent = {}
                            checkneighbors(y, x)
                        end
                    end
                    table.sort(adjacent, function(a, b)
                        if a.unit.health == b.unit.health then
                            return priority(a.y, a.x, b.y, b.x)
                        end
                        return a.unit.health < b.unit.health
                    end)
                    local victim = adjacent[1] and adjacent[1].unit
                    if victim then
                        victim.health = victim.health - (c == "E" and atk or 3)
                        if victim.health <= 0 then
                            if grid[victim.y][victim.x] == "E" then return "killed" end
                            grid[victim.y][victim.x] = "."
                        end
                    end
                end
            end
        end
    end
end

local function getoutcome(atk)
    local rounds = 0
    loadinput()
    while true do
        print(rounds, atk)
        local v = step(atk)
        if v == "killed" then
            return "killed"
        elseif v ~= "end" then
            rounds = rounds + 1
        else
            break
        end
    end
    local healthsum = 0
    for _, u in pairs(units) do
        if u.health > 0 then
            healthsum = healthsum + u.health
        end
    end
    return healthsum*rounds
end
for atk = 4, 100 do
    local result = getoutcome(atk)
    if result ~= "killed" then
        drawgrid()
        print(atk, result)
        break
    end
end