require "ext"
local map = {}
local row, col = 0,0
local function fmt_location(row, col)
	return string.format("%d,%d",row,col)
end
for line in io.lines() do
	row = row + 1
	col = 0
	for char in line:gmatch("(.)") do
		col = col + 1
		local locf = fmt_location(row,col)
		if char == "#" then
			map[locf] = true
		end
	end
end

local directions = {
	N = {-1,0},
	S = {1,0},
	E = {0,1},
	W = {0,-1},
	NE = {-1,1},
	NW = {-1,-1},
	SE = {1,1},
	SW = {1,-1}
}
local dir_order = {
	{"N","NE","NW"},
	{"S","SE","SW"},
	{"W","NW","SW"},
	{"E","NE","SE"}
}

print(map)

local function parse_location(location)
	local trow,tcol = location:match("([%d-]+),([%d-]+)")
	return tonumber(trow), tonumber(tcol)
end
local function round(map, order_dir)
	--print("Directions:",order_dir)
	--first half, propose
	local propositions = {}
	for location, elf in pairs(map) do
		local elf_nearby = false
		local trow, tcol = parse_location(location)
		for _, dir in pairs(directions) do
			local nrow, ncol = trow + dir[1], tcol + dir[2]
			local nloc = fmt_location(nrow,ncol)
			if map[nloc] then
				elf_nearby = true
				break
			end
		end
		if not elf_nearby then
			propositions[location] = {location}
			goto nextelf
		end
		assert(elf_nearby)
		for _,dset in ipairs(dir_order) do
			local dir_empty = true
			for _,d in ipairs(dset) do
				local dir = directions[d]
				local nrow, ncol = trow + dir[1], tcol + dir[2]
				local nloc = fmt_location(nrow,ncol)
				if map[nloc] then
					dir_empty = false
					break
				end
			end
			if dir_empty then
				local dir = directions[dset[1]]
				local nrow, ncol = trow + dir[1], tcol + dir[2]
				local nloc = fmt_location(nrow,ncol)
				if not propositions[nloc] then
					propositions[nloc] = {location}
				else
					table.insert(propositions[nloc],location)
				end
				goto nextelf
			end
		end
		-- no new location proposed, sit tight
		propositions[location] = {location}
		::nextelf::
	end

	--print("Propositions:",propositions)
	--second half, move if we were the only ones that want to go there
	local any_moved = false
	for location, elftbl in pairs(propositions) do
		if #elftbl == 1 and elftbl[1] ~= location then
			any_moved = true
		end
	end
	if not any_moved then
		os.exit(0)
	end
	local newmap = {}
	for location, elftbl in pairs(propositions) do
		if #elftbl == 1 then
			newmap[location] = true
		else
			for _,oloc in pairs(elftbl) do
				newmap[oloc] = true
			end
		end
	end
	return newmap
end

local function aabb(map)
	local minrow,mincol,maxrow,maxcol= math.huge, math.huge, -math.huge, -math.huge
	for location,_ in pairs(map) do
		local row,col = parse_location(location)
		minrow = math.min(minrow,row)
		maxrow = math.max(maxrow,row)
		mincol = math.min(mincol,col)
		maxcol = math.max(maxcol,col)
	end
	return minrow, mincol, maxrow, maxcol
end

local function print_puzzle(map)
	local minrow, mincol, maxrow, maxcol = aabb(map)
	io.write("    ")
	for col = mincol - 1, maxcol + 1 do
		io.write(col)
	end
	io.write("\n")
	for row = minrow - 1, maxrow + 1 do
		io.write(string.format("%3d|",row))
		for col = mincol - 1,maxcol + 1 do
			local loc = fmt_location(row,col)
			if map[loc] then
				io.write("#")
			else
				io.write(".")
			end
		end
		io.write("\n")
	end
end

local function emptyaabb(map)
	local minrow, mincol, maxrow, maxcol = aabb(map)
	local count = 0
	for row = minrow, maxrow do
		for col = mincol ,maxcol do
			local loc = fmt_location(row,col)
			if not map[loc] then
				count = count + 1
			end
		end
	end
	return count
end

print_puzzle(map)
print("==========")
local i = 0
while true do
	i = i + 1
	print(i)
	map = round(map,dir_order)
	table.insert(dir_order,table.remove(dir_order,1))

	--print_puzzle(map)
	--print("==========")
end
print(emptyaabb(map))