#! /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)
Node = Struct.new(:coords, :direction, :num_prev_steps)
RouteNode = Struct.new(:node, :cost, :previous_node)

module Directions
        UP = 0
        LEFT = 1
        DOWN = 2
        RIGHT = 3
end

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

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

routes = city_map.map {|row| row.map { (0..3).map { (0..2).map {nil}}}}

$width = city_map[0].length
$height = city_map.length

Colour = Struct.new(:r, :g, :b)

start_space = Coord.new(0, 0)
end_space = Coord.new($width - 1, $height - 1)

class PQueue
        def initialize()
                # Placeholder at the root to simplify calculations
                @objects = [nil]
        end

        def push(element)
                new_idx = @objects.size
                @objects << element
                _reorder_insert(new_idx)
        end

        def _reorder_insert(idx)
                parent_idx = idx / 2
                if idx > 1 and @objects[parent_idx].cost > @objects[idx].cost
                        _swap(idx, parent_idx)
                        _reorder_insert(parent_idx)
                end
        end

        def _swap(idx1, idx2)
                @objects[idx2], @objects[idx1] = @objects[idx1], @objects[idx2]
        end

        def pop()
                # Swap for easy popping without moving everything
                _swap(1, @objects.size - 1)
                priority_obj = @objects.pop
                _reorder_remove(1)
                priority_obj
        end

        def _reorder_remove(idx)
                child1_idx = idx * 2
                child2_idx = child1_idx + 1
                last_idx = @objects.size - 1

                if child1_idx <= last_idx
                        child1_val = @objects[child1_idx].cost
                        child2_val = child2_idx <= last_idx ? @objects[child2_idx].cost : Float::INFINITY
                        child_idx, child_val =  child1_val < child2_val ? [child1_idx, child1_val] : [child2_idx, child2_val]

                        if @objects[idx].cost >= child_val
                                _swap(idx, child_idx)
                                _reorder_remove(child_idx)
                        end
                end
        end

        def empty?
                @objects.size <= 1
        end

        def to_s
                @objects.map {|val| "#{val.coords.x},#{val.coords.y}=#{val.cost}" if val }
        end
end

# Our route is constrained to "four consecutive spaces". Zig-zag through the middle
# obeys that rule and it's either the shortest route _or_ we won't explore a longer route
max_score = city_map.each_with_index.map {|row, i| i < row.length - 1 ? [row[i], row[i+1]] : [row[i]]}.flatten.reduce(:+)

$colours = (0..max_score).map do |i|
	angle = (i.to_f / max_score) * 360
	if angle <= 60
		r = 0xff
		g = 0xff * angle / 60
		b = 0
	elsif angle <= 120
		r = 0xff * (120 - angle) / 60
		g = 0xff
		b = 0
	elsif angle <= 180
		r = 0
		g = 0xff
		b = 0xff * (angle - 120) / 60
	elsif angle <= 240
		r = 0
		g = 0xff * (240 - angle) / 60
		b = 0xff
	elsif angle <= 300
		r = 0xff * (240 - angle) / 60
		g = 0
		b = 0xff
	else
		r = 0xff
		g = 0
		b = 0xff * (360 - angle) / 60
	end
	Colour.new(r.to_i, g.to_i, b.to_i)
end

def update_map(new_node, map)
	up = $height - new_node.node.coords.y
	# We printed a new line after the map, so we're already in column 0 and go X forward (right)
	forward = new_node.node.coords.x
        colour = $colours[new_node.cost]
        cell = map[new_node.node.coords.y][new_node.node.coords.x]
        #puts [cell, new_node, $height, $width, up, forward, colour]
        print "\e[s"
        if forward > 0
                print "\e[#{forward}C"
        end
        if up > 0
                print "\e[#{up}A"
        end
        print "\e[48;2;#{colour.r};#{colour.g};#{colour.b}m#{cell}\e[0m\e[u"
end

puts "#{city_map.map {|row| row.join("")}.join("\n")}"
# sleep(5)  # For screen recording

unvisited = PQueue.new
# Fake two starting steps from outside so that we use the "turn" logic to get
# routes with zero previous steps
start_node_1 = RouteNode.new(Node.new(start_space, Directions::RIGHT, 0), 0, nil)
start_node_2 = RouteNode.new(Node.new(start_space, Directions::DOWN, 0), 0, nil)
unvisited.push(start_node_1)
unvisited.push(start_node_2)
visited = Set.new
candidate_node = nil

def is_shorter?(cur_shortest, new_node)
        not cur_shortest or cur_shortest.cost > new_node.cost
end

def is_valid?(x, y)
        0 <= x and x  < $width and 0 <= y and y < $height
end

while not unvisited.empty?
        candidate_node = unvisited.pop
        candidate_node_node = candidate_node.node

        if visited.include?(candidate_node_node)
                # Longer route to an already visited node
                next
        end
        visited.add(candidate_node_node)

        candidate_coords = candidate_node_node.coords
        update_map(candidate_node, city_map)


        if candidate_coords == end_space
                break
        end

        current_direction = candidate_node_node.direction

        # We can always turn
        anticlockwise = (current_direction + 1) % 4
        clockwise = (anticlockwise + 2) % 4

        next_steps = [
                [anticlockwise, 0],
                [clockwise, 0]
        ]
        next_steps.append([current_direction, candidate_node_node.num_prev_steps + 1]) if candidate_node_node.num_prev_steps < 4

        next_steps.each do |direction, num_prev_steps|
                dir = directions[direction]
                new_x = candidate_coords.x + dir.x
                new_y = candidate_coords.y + dir.y
                if is_valid?(new_x, new_y)
                        next_num_prev_steps = num_prev_steps + 1
                        cur_shortest = routes[new_y][new_x][direction][next_num_prev_steps]
                        if is_shorter?(cur_shortest, candidate_node)
                                new_shortest = RouteNode.new(Node.new(Coord.new(new_x, new_y), direction, next_num_prev_steps), candidate_node.cost + city_map[new_y][new_x], candidate_node)
                                routes[new_y][new_x][direction][next_num_prev_steps] = new_shortest
                                unvisited.push(new_shortest)
                        end
                end
        end
end

if candidate_node
        route_node = candidate_node
        coords = []
        while route_node
                coords.append(route_node.node.coords)
                route_node = route_node.previous_node
        end
        coords.each do |step|
                cell = city_map[step.y][step.x]
                up = $height - step.y
                forward = step.x
                print "\e[s"
                if forward > 0
                        print "\e[#{forward}C"
                end
                if up > 0
                        print "\e[#{up}A"
                end
                print "\e[1;30m\e[1;47m#{cell}\e[0m\e[u"
        end
        puts candidate_node.cost
end