#! /usr/bin/env ruby

require 'set'

if ARGV.length != 1
        abort("Incorrect arguments - needs input file")
elsif not File.exist? (ARGV[0])
	abort("File #{ARGV[0]} did not exist")
end

file = ARGV[0]

Coord = Struct.new(:x, :y)
Route = Struct.new(:steps, :distance)
Routes = Struct.new(:routes, :min_distance)

city_map = File.open(file, "r").each_line(chomp: true).map{ |line| line.each_char.map(&:to_i)}

start_space = Coord.new(0,0)
end_space = Coord.new(city_map[0].length - 1, city_map.length - 1)

visited = {}
routes = { start_space => Routes.new([Route.new([start_space], 0)], 0)}

unvisited = Set.new
unvisited << start_space
#(0...city_map.length).each {|y| (0...city_map[0].length).each {|x| unvisited << Coord.new(x,y)}}

$up = Coord.new(0, -1)
$down = Coord.new(0, 1)
$left = Coord.new(-1, 0)
$right = Coord.new(1, 0)

def get_neighbours(city_map, x, y)
	[$up, $down, $left, $right].map {|coord| Coord.new(coord.x + x, coord.y + y)}.filter {|coord| coord.x >= 0 and coord.y >= 0 and coord.x < city_map[0].length and coord.y < city_map.length}
end

def allowed_routes(city_map, routes, cur_node, next_node)
	next_step_distance = city_map[next_node.y][next_node.x]
	candidate_routes = routes[cur_node].routes.map {|route| Route.new(route.steps + [next_node], route.distance + next_step_distance)}
	valid_routes = candidate_routes.filter do |route|
		looped = route.steps.count(next_node) > 1
		if route.steps.length < 5
			! looped
		else
			step_range = route.steps[-5..-2]
			!(step_range.all?{|step| step.x == next_node.x} or step_range.all?{|step| step.y == next_node.y}) and !looped
		end
	end
	valid_routes = valid_routes + routes[next_node].routes if !routes[next_node].nil?
	Routes.new(valid_routes, valid_routes.map(&:distance).min)
end

def get_distance(routes, node)
	if routes.key?(node)
		routes[node].min_distance
	else
		Float::INFINITY
	end
end

until unvisited.empty?
#	puts unvisited
	min_node = nil
#	min_node_direct_distance = Float::INFINITY
	unvisited.each do |node|
#		x_dist = (end_space.x - node.x).abs
#		y_dist = (end_space.y - node.y).abs
#		direct_distance = x_dist * x_dist + y_dist * y_dist
		if min_node.nil? || get_distance(routes, node) < get_distance(routes, min_node)# || direct_distance < min_node_direct_distance
#			puts "#{get_distance(routes, node)} < #{get_distance(routes, min_node)} || #{direct_distance} < #{min_node_direct_distance}"
			min_node = node
#			min_node_direct_distance = direct_distance
		end
	end
#	puts unvisited.length
	puts "Min node: #{min_node}"

	break if get_distance(routes, min_node) == Float::INFINITY or min_node == end_space

	get_neighbours(city_map, min_node.x, min_node.y).each do |neighbour|
		new_routes = allowed_routes(city_map, routes, min_node, neighbour)
		if new_routes.routes.length > 0
			routes[neighbour] = new_routes
			unvisited << neighbour if !visited[neighbour]
		end
	end

	visited[min_node] = true
	unvisited = unvisited.delete(min_node)
#	puts "Delete #{min_node}"
#	a = $stdin.gets("\n")
end
=begin
city_map.length.times do |y|
	city_map[0].length.times do |x|
		print routes[Coord.new(x,y)].routes.map(&:distance).min.to_s.rjust(3) + " " + city_map[y][x].to_s + " |"
	end
	puts
end
city_map.length.times do |y|
	city_map[0].length.times do |x|
		puts "#{x},#{y} ⇒ #{routes[Coord.new(x,y)].routes.length} - #{routes[Coord.new(x,y)].routes.map(&:distance).minmax}"
	end
end
=end

puts routes[end_space].routes.sort {|a, b| a.distance <=> b.distance}[0]
#puts "#{routes[end_space]}"