class RoutePlanner

# File lib/route_planner.rb, line 6
def initialize(graph_info)
  @graph = { }
  graph_info.scan(/\w\w\d+/).each do |x|
    start = x[0,1]
    finish = x[1,1]
    @graph[start] ||= { }
    @graph[start][finish] = x[2..-1].to_i
  end    
end

# File lib/route_planner.rb, line 18
def distance(path)
  dist = 0
  path.each_char.map.inject do |prev, cur|
    return nil unless @graph[prev][cur]
    dist += @graph[prev][cur]
    cur
  end
  dist
end

# File lib/route_planner.rb, line 36
def shortest_distance(start, finish)
  all_nodes = @graph.each.map { |k,v| [k, v.keys] }.flatten.uniq
  dist = { }
  all_nodes.each { |x| dist[x] = Infinity }
  dist[start] = 0
  if start == finish then

    all_nodes.delete(start)
    dist[start] = Infinity
    @graph[start].each { |nxt, how_far| dist[nxt] = how_far }
  end
      
  while not all_nodes.empty? do
    min_node = all_nodes.min { |a,b| dist[a] <=> dist[b] }
    if !min_node || min_node == Infinity
      return nil 
    end
    all_nodes.delete(min_node)
    
    @graph[min_node].each_key do |v|
      alt = dist[min_node] + (@graph[min_node][v] || Infinity)
      dist[v] = alt if dist[v] && alt < dist[v]
    end
  end
  return nil if dist[finish] == Infinity
  dist[finish]
end

# File lib/route_planner.rb, line 29
def trips_number(start, finish, opts = { })
  opts = { :min_stops => 1, :max_stops => Infinity, :max_distance => Infinity }.merge(opts)
  total = 0
  explore_routes(start, finish, opts) { total += 1}
  total
end

# File lib/route_planner.rb, line 67
def explore_routes(start, finish, opts, stats = {:distance => 0, :stops => 0}, &callback)
  lower_bound_ok = stats[:stops] >= opts[:min_stops]
  upper_bound_ok = stats[:distance] <= opts[:max_distance] && stats[:stops] <= opts[:max_stops]
  
  callback.call(stats[:path]) if start == finish && lower_bound_ok && upper_bound_ok
  # Recursion basis: stop exploration when reached upper-bound restrictions
  if upper_bound_ok    
    @graph[start].each do |nxt, dist|
      inner_stats = {:distance => stats[:distance] + dist, :stops => stats[:stops] + 1}
      explore_routes(nxt, finish, opts, inner_stats, &callback)
    end
  end
end