#! /usr/bin/env ruby

require 'set'

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

file = ARGV[0]

lines = File.open(file, "r").each_line(chomp: true).to_a
start_pos = [lines[0].index("."), 0]
end_pos = [lines[-1].index("."), lines.length - 1]
maze = lines.map {|line| line.each_char.to_a}

$maze_width = 0...maze[0].length
$maze_height = 0...maze.length
$can_climb_hills = ARGV.length == 2

open_segments = [[start_pos]]
segments = Hash.new

$moves = [[0,1], [0,-1], [1,0], [-1,0]]

def valid_move(move, space, maze)
    if $maze_width.cover?(space[0]) && $maze_height.cover?(space[1])
        case maze[space[1]][space[0]]
        when "#" then false
        when "." then true
        when "^" then $can_climb_hills || move == [0,-1]
        when "v" then $can_climb_hills || move == [0, 1]
        when ">" then $can_climb_hills || move == [1, 0]
        when "<" then $can_climb_hills || move == [-1,0]
        end
    else
        false
    end
end

def next_steps(route, maze)
    last_space = route[-1]
    $moves.map do |move|
        new_space = [move[0] + last_space[0], move[1] + last_space[1]]
        [move, new_space]
    end.filter do |move, new_space|
        valid_move(move, new_space, maze) && !route.include?(new_space)
    end
end

def add_segment(segments, start_step, end_step, route_length)
    current_segments = segments.key?(start_step) ? segments[start_step] : []
    current_segments << [end_step, route_length]
    segments[start_step] = current_segments
end

while open_segments != []
    open_segments = open_segments.flat_map do |route|
        candidate_steps = next_steps(route, maze)
        if candidate_steps.length > 1
            been_here_before = segments.key?(route[-1])
            # We got to a fork - record the segment
            if $can_climb_hills
                add_segment(segments, route[-1], route[0], route.length)
            end
            add_segment(segments, route[0], route[-1], route.length)
            if ! been_here_before
                # Start some new segments
                candidate_steps.map do |move, step|
                    [route[-1], step]
                end
            else
                # Else we've already explored to this fork from another direction, so we can stop
                []
            end
        else
            # We're following a corridor
            candidate_steps.filter do |move, step|
                if step == end_pos
                    # We got to the end - record the segment
                    add_segment(segments, route[0], step, route.length + 1)
                    false
                else
                    true
                end
            end.map do |move, step|
                route + [step]
            end
        end
    end
end

open_routes = [[[start_pos], 0]]
routes = []

while open_routes.length > 0
    open_routes = open_routes.flat_map do |route|
        segments[route[0][-1]].filter do |segment|
            if segment[0] == end_pos
                #puts "Add route #{routes.length}: #{route[0] + [segment[0]]} = #{route[1] + segment[1]}"
                routes << route[1] + segment[1]
                false
            else
                !route[0].include?(segment[0]) && !route[0].include?([segment[0]])
            end
        end.map do |segment|
            # Subtract the overlapping node
            [route[0] + [segment[0]], route[1] + segment[1] - 1]
        end
    end
    open_routes = Set.new(open_routes)
end

longest_route = routes.max
# Subtract the start node
puts "#{routes.length} routes - max length #{longest_route - 1}"