Class: RoutePlanner

Inherits:
Object
  • Object
show all
Defined in:
lib/route_planner.rb

Constant Summary collapse

Infinity = 
1.0 / 0

Instance Method Summary collapse

Constructor Details

#initialize(graph_info) ⇒ RoutePlanner

Returns a new instance of RoutePlanner.



6
7
8
9
10
11
12
13
14
 
# 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

Instance Method Details

#distance(path) ⇒ Object

Determines the distance between two points (towns). Returns nil if no path is available.



18
19
20
21
22
23
24
25
26
 
# 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

#shortest_distance(start, finish) ⇒ Object 



36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# 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

#trips_number(start, finish, opts = { }) ⇒ Object

Number of possible trips between two points (towns)



29
30
31
32
33
34
 
# 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