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)
	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(#elist)
				end
			else
				io.write(".")
			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] and
		map[row][col] == nil
	)
	--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 branches = {state}
local min_path = 147
local nbranches = 0
while #branches > 0 do
	--print(#branches)
	local tbranch = table.remove(branches)
	nbranches = nbranches + 1
	if nbranches % 100000 == 0 then
		print("Analyzed",nbranches,"branches",#branches,"active")
	end
	if tbranch.minute > min_path then
		goto nextbranch
	end
	if tbranch.speculative_goal > min_path then
		goto nextbranch
	end
	local nloc = tbranch.location
	if nloc[1] == h and nloc[2] == finish then
		print("Found a working branch:",tbranch)
		print("Branches remaining:",#branches)
		if tbranch.minute < min_path then
			min_path = tbranch.minute
		end
		goto nextbranch
	end
	local ctime = tbranch.minute
	local nmap = mapat[ctime + 1]
	--print_puzzle(nmap)
	for name, direction in pairs(directions) do
		local nrow, ncol = nloc[1] + direction[1], nloc[2] + direction[2]
		if could_move(nmap,nrow,ncol) then
			if nrow == h then
				assert(ncol == finish)
			end
			local sc = copy_state(tbranch)
			sc.location = {nrow,ncol}
			sc.speculative_goal = sc.speculative_goal + spec_tbl[direction]
			if sc.speculative_goal < min_path and sc.minute < min_path then
				sc.minute = sc.minute + 1
				table.insert(branches,sc)
			end
		end
	end
	--[[
	--It's actually faster if we don't do this, and all states fit into one memory page
	--Once in a while, sort the branhces to prioritize promising paths
	if nbranches % 100000 == 0 then
		table.sort(branches,function(a,b)
			return (a.minute + a.speculative_goal) > (b.minute + b.speculative_goal)
		end)
	end
	]]
	::nextbranch::
end
print(nbranches)
print("Out of branches")
print(min_path)