require "ext"
local directions = {
	right = {0,1},
	down = {1,0},
	left = {0,-1},
	up = {-1,0},
	wait = {0,0},
}
local tiles = {
	wall = {rep="#"},
	lbliz = {rep="<",move=directions.left},
	rbliz = {rep=">",move=directions.right},
	ubliz = {rep="^",move=directions.up},
	dbliz = {rep="v",move=directions.down},
	empty = {rep="."}
}
local map = {}
local row,col = 0,0
local start,finish
local function place(map,row,col,ent)
	map[row] = map[row] or {}
	map[row][col] = map[row][col] or {}
	table.insert(map[row][col],ent)
end
for line in io.lines() do
	map[#map+1] = {}
	row = row + 1
	col = 0
	for char in line:gmatch("(.)") do
		col = col + 1
		if char == "." then
			if row == 1 then
				start = col
			else
				finish = col
			end
		end
		for name,tile in pairs(tiles) do
			if char == tile.rep and name ~= "empty" then
				place(map,row,col,{r=row,c=col,t=tile})
				break
			end
		end
	end
end
local w,h = col,row
local function print_puzzle(map,flood)
	for row = 1,h do
		for col = 1,w do
			if map[row] and map[row][col] then
				local elist = map[row][col]
				if #elist == 1 then
					io.write(elist[1].t.rep .. " ")
				else
					io.write("* ")
				end
			else
				if flood and flood[row] and flood[row][col] then
					io.write(string.format("%-2d",flood[row][col]))
				else
					io.write("  ")
				end
			end
		end
		io.write("\n")
	end
end
				
local h,w = #map, #map[1]
local min_walk = math.abs(finish - start) + h

print_puzzle(map)

local function step_map(map)
	local newmap = {}
	for row = 1,h do
		for col = 1,w do
			if map[row] and map[row][col] then
				for _, ent in pairs(map[row][col]) do
					if ent.t.move then
						local dir = ent.t.move
						ent.r = ent.r + dir[1]
						ent.c = ent.c + dir[2]
						--loop
						if ent.r == 1 then
							ent.r = h-1
						elseif ent.r == h then
							ent.r = 2
						elseif ent.c == 1 then
							ent.c = w-1
						elseif ent.c == w then
							ent.c = 2
						end
						place(newmap,ent.r,ent.c,ent)
					else
						place(newmap,ent.r,ent.c,ent)
					end
				end
			end
		end
	end
	return newmap
end
local function could_move(map,row,col)
	local ret = (
		row >= 1 and
		col > 1 and
		row <= h and
		col < w and
		(map[row] == nil or
		map[row][col] == nil or
		map[row][col].t ~= tiles.wall)
	)
	--print(ret)
	return ret
end

--map doesn't change, no matter what we do, we can store the blizzard simulation
local map_mem, mapat = {}, {[0] = map}
setmetatable(mapat,{__index=function(self,key)
	if map_mem[key] then return map_mem[key] end
	map_mem[key] = step_map(mapat[key-1])
	return map_mem[key]
end})

local state = {
	location = {1,start},
	minute = 0,
	speculative_goal = min_walk
}
local function copy_state(state)
	return {
		location = {state.location[1],state.location[2]},
		minute = state.minute,
		speculative_goal = state.speculative_goal
	}
end
local spec_tbl = {
	[directions.right] = -1,
	[directions.down] = -1,
	[directions.left] = 2,
	[directions.up] = 2,
	[directions.wait] = 0
}

local flood = {}
for row = 1,h do
	flood[row] = {}
end
flood[1][2] = 0
local min = 0
while flood[h][w-1] == nil do
	min = min + 1
	print("Min",min)
	local nmap = mapat[min-1]
	local toins = {}
	--[[
	print("Before flooding 1:")
	print_puzzle(nmap,flood)
	]]
	--flood outward
	for rn,row in pairs(flood) do
		for cn,col in pairs(row) do
			if flood[rn][cn] then
				for name, direction in pairs(directions) do
					--print("Flooding",rn,cn,name)
					local trow = rn + direction[1]
					local tcol = cn + direction[2]
					if could_move(nmap,trow,tcol) and flood[trow][tcol] == nil then
						table.insert(toins,{trow,tcol})
					end
				end
			end
		end
	end
	for _,v in pairs(toins) do
		flood[v[1]][v[2]] = min
	end
	--[[
	print("After flooding 1:")
	print_puzzle(nmap,flood)
	]]
	nmap = mapat[min]
	--clean up where blizzards pass
	for rn,row in pairs(nmap) do
		for cn, col in pairs(row) do
			flood[rn][cn] = nil
		end
	end
	--[[
	print("After cleaning:")
	print_puzzle(nmap,flood)
	]]
end
print("First goal reached after:",min)
flood = {}
for row = 1,h do
	flood[row] = {}
end
flood[h][w-1] = min
while flood[1][2] == nil do
	min = min + 1
	print("Min",min)
	local nmap = mapat[min-1]
	local toins = {}
	--[[
	print("Before flooding 1:")
	print_puzzle(nmap,flood)
	]]
	--flood outward
	for rn,row in pairs(flood) do
		for cn,col in pairs(row) do
			if flood[rn][cn] then
				for name, direction in pairs(directions) do
					--print("Flooding",rn,cn,name)
					local trow = rn + direction[1]
					local tcol = cn + direction[2]
					if could_move(nmap,trow,tcol) and flood[trow][tcol] == nil then
						table.insert(toins,{trow,tcol})
					end
				end
			end
		end
	end
	for _,v in pairs(toins) do
		flood[v[1]][v[2]] = min
	end
	--[[
	print("After flooding 1:")
	print_puzzle(nmap,flood)
	]]
	nmap = mapat[min]
	--clean up where blizzards pass
	for rn,row in pairs(nmap) do
		for cn, col in pairs(row) do
			flood[rn][cn] = nil
		end
	end
	print("After cleaning:")
	print_puzzle(nmap,flood)
end
print("back to start reached after:",min)
flood = {}
for row = 1,h do
	flood[row] = {}
end
flood[1][2] = min
while flood[h][w-1] == nil do
	min = min + 1
	print("Min",min)
	local nmap = mapat[min-1]
	local toins = {}
	--[[
	print("Before flooding 1:")
	print_puzzle(nmap,flood)
	]]
	--flood outward
	for rn,row in pairs(flood) do
		for cn,col in pairs(row) do
			if flood[rn][cn] then
				for name, direction in pairs(directions) do
					--print("Flooding",rn,cn,name)
					local trow = rn + direction[1]
					local tcol = cn + direction[2]
					if could_move(nmap,trow,tcol) and flood[trow][tcol] == nil then
						table.insert(toins,{trow,tcol})
					end
				end
			end
		end
	end
	for _,v in pairs(toins) do
		flood[v[1]][v[2]] = min
	end
	--[[
	print("After flooding 1:")
	print_puzzle(nmap,flood)
	]]
	nmap = mapat[min]
	--clean up where blizzards pass
	for rn,row in pairs(nmap) do
		for cn, col in pairs(row) do
			flood[rn][cn] = nil
		end
	end
	print("After cleaning:")
	print_puzzle(nmap,flood)
end
print("Back to goal reached after",min)