input1.txt

AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7

q1.rb

# 
#  q1.rb
# 
#  Tested using Ruby >= 1.9.2
#  usage: ruby q1.rb input1.txt         
# 

$LOAD_PATH.unshift(File.dirname(__FILE__))
require "train_yard"

def print_result(question,result)                      
  puts "##{question}: #{result ||= 'NO SUCH ROUTE'}"
end

puts ""
puts "******************** BEGIN *************************" 

raw_graph = ARGF.readline   # AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7
ty = TrainYard.new(:raw_graph => raw_graph, :debug => true)

# Run the 10 questions:
puts "Running Mandatory Questions..."  
print_result(1,ty.total_distance("ABC"))
print_result(2,ty.total_distance("AD"))
print_result(3,ty.total_distance("ADC"))
print_result(4,ty.total_distance("AEBCD"))
print_result(5,ty.total_distance("AED"))   
print_result(6,ty.count_trips("C", "C", {:max_stops => 3}))
print_result(7,ty.count_trips("A", "C", {:min_stops => 4, :max_stops => 4}))   
print_result(8,ty.shortest_path("A","C")) 
print_result(9,ty.shortest_path("B","B"))
print_result(10,ty.count_trips("C", "C", {:max_distance => 29})) 
puts "****************************************************"     

# puts "Extra Testing Questions..." 
# print_result("Extra1",ty.total_distance("AEBCEBCDE"))  
# print_result("Extra2",ty.total_distance("ACDDCAABCADECDEDCCBCEBCDE"))  
# print_result("Extra3",ty.total_distance("AAAAA"))  
# print_result("Extra4",ty.total_distance("")) 
# print_result("Extra5",ty.count_trips("A", "C", {:max_stops => 0})) 
# print_result("Extra6",ty.count_trips("B", "C", {:max_stops => 10, :max_distance =>50})) 
# print_result("Extra7",ty.shortest_path("B","C")) 
# puts ""

q1_tests.rb

# 
#  q1_tests.rb
#
#  Tested using Ruby >= 1.9.2
#  usage: ruby q1_tests.rb

$LOAD_PATH.unshift(File.dirname(__FILE__))
require "train_yard"
require "test/unit"   

class Test::Unit::TestCase
  def setup
    @testgraph = "AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7"
    @trainyard = TrainYard.new(:raw_graph => @testgraph)    
  end
  
  # Supplied test data (minimum tests needed to pass)
  def test_question1
    assert_equal 9, @trainyard.total_distance("ABC")
  end            
  
  def test_question2
    assert_equal 5, @trainyard.total_distance("AD")
  end  
  
  def test_question3
    assert_equal 13, @trainyard.total_distance("ADC")
  end
  
  def test_question4
    assert_equal 22, @trainyard.total_distance("AEBCD")
  end
  
  def test_question5
    assert_nil @trainyard.total_distance("AED")
  end    
  
  def test_question6
    assert_equal 2, @trainyard.count_trips("C", "C", {:max_stops => 3})
  end
  
  def test_question7
    assert_equal 3, @trainyard.count_trips("A", "C", {:min_stops => 4, :max_stops => 4})
  end
  
  def test_question8
    assert_equal 9, @trainyard.shortest_path("A","C") 
  end
  
  def test_question9
    assert_equal 9, @trainyard.shortest_path("B","B") 
  end
  
  def test_question10
    assert_equal 7, @trainyard.count_trips("C", "C", {:max_distance => 29})  
  end                                                                             
  
  # ******************************************************************************
  # More tests
  #
   
  def test_extra1
    assert_equal 37, @trainyard.total_distance("AEBCEBCDE")
  end   
    
  def test_extra2
    assert_nil @trainyard.total_distance("ACDDCAABCADECDEDCCBCEBCDE")
  end     
  
  def test_extra3
    assert_nil @trainyard.total_distance("AAAAA")
  end
  
  def test_extra4
    assert_nil @trainyard.total_distance("")
  end 
  
  def test_extra5
    assert_equal 0, @trainyard.count_trips("A", "C", {:max_stops => 0})
  end  
      
  def test_extra6
    assert_equal 26, @trainyard.count_trips("B", "C", {:max_stops => 10, :max_distance =>50})
  end    
  
  def test_extra7
    assert_equal 4, @trainyard.shortest_path("B", "C")
  end  

end
   

train_yard.rb

# 
#  train_yard.rb
#  
#  Tested using Ruby >= 1.9.2
# 
#  Problem:
#  The local commuter railroad services a number of towns in Kiwiland.  Because of monetary concerns, 
#  all of the tracks are 'one-way.' That is, a route from Kaitaia to Invercargill does not imply the 
#  existence of a route from Invercargill to Kaitaia.  In fact, even if both of these routes do happen 
#  to exist, they are distinct and are not necessarily the same distance!
#  The purpose of this problem is to help the railroad provide its customers with information about 
#  the routes.  In particular, you will compute the distance along a certain route, the number of 
#  different routes between two towns, and the shortest route between two towns.
# 
#  Input:  A directed graph where a node represents a town and an edge represents a route between two 
#  towns.The weighting of the edge represents the distance between the two towns.  A given route will never 
#  appear more than once, and for a given route, the starting and ending town will not be the same town.
#   
#  Output: For test input 1 through 5, if no such route exists, output 'NO SUCH ROUTE'.  Otherwise, 
#  follow the route as given; do not make any extra stops!  For example, the first problem means to 
#  start at city A, then travel directly to city B (a distance of 5), then directly to city C 
#  (a distance of 4).

class TrainYard
  # Constructor 
  # @param options[:raw_graph] [String]
  # @param options[:debug] [Boolean] (optional)
  def initialize(options = {})
    @graph = {} #our directed graph {"A"=>{"B"=>5, "D"=>5, "E"=>7}, "B"=>{"C"=>4}, "C"=>{"D"=>8, "E"=>2}, "D"=>{"C"=>8, "E"=>6}, "E"=>{"B"=>3}} 
    @nodes = [] #our nodes ["A", "B", "C", "D", "E"]                         
    @debug = options[:debug] || false

    load_graph(options[:raw_graph].split(",").map(&:strip))    
  end   
  
  # Builds internal graph from raw graph string:
  # Ex:
  # {
  #     "A" = >{
  #         "B" = >5,
  #         "D" = >5,
  #         "E" = >7
  #     },
  #     "B" = >{
  #         "C" = >4
  #     },
  #     "C" = >{
  #         "D" = >8,
  #         "E" = >2
  #     },
  #     "D" = >{
  #         "C" = >8,
  #         "E" = >6
  #     },
  #     "E" = >{
  #         "B" = >3
  #     }
  # }   
  # 
  # @param raw_graph [String] - Assume format of: 'AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7'  
  def load_graph(raw_graph)
    raw_graph.each{ |route_str| add_route(route_str[0],route_str[1],route_str[2].to_i)} #build the graph from the raw instruction input   
    @nodes = @graph.each.map { |k,v| [k, v.keys] }.flatten.uniq #grab all the unique keys (nodes)  
    @nodes.sort! { |a,b| a <=> b } #sort them based on letter (no reason to do this really :)
    
    if @debug
      puts "Loaded graph: #{@graph}"
      puts "Loaded nodes: #{@nodes}"
      puts ""     
    end
  end

  # Calculates the total distance of a route in the graph
  # ex: A-B-C-D
  # 
  # @param route [String] The route to calculate: "ABCD"
  # @return [Fixnum] or [Nil]
  def total_distance(route)
    total = 0             
    if route.nil? || route.empty?     # check for bad data
      total = nil
    end  
    route.chars.to_a.each_with_index{|e,i|
      unless (i+1 == route.length)
        dist = find_dist(e, route[i+1])
        total = (dist.nil? || total.nil?)? nil : (total + dist)
      end
    }
    total
  end 
  
  # Given a starting node and ending node, calculate the total number of trips possible
  # 
  # @param start [String] - Key for starting node in graph
  # @param finish [String] - Key for ending node in graph
  # @param options[:min_stops] [Fixnum] - Minimum number of stops
  # @param options[:max_stops] [Fixnum] - Maximum number of stops
  # @param options[:min_distance] [Fixnum] - Maximum distance allowed
  # @return [Fixnum]
  def count_trips(start, finish, opts={})  
    opts = { 
      :min_stops => opts[:min_stops] || 1, 
      :max_stops => opts[:max_stops] || Float::INFINITY, 
      :max_distance => opts[:max_distance] || Float::INFINITY 
    }     
    total = 0
    traverse_routes(start, finish, opts) { total += 1 }
    total
  end   
  
  # Getter function to return the shortest distance between two nodes
  # 
  # @param start [String] - Key for starting node in grap
  # @param finish [String] - Key for ending node in graph
  # @return [Fixnum] or [Nil]
  def shortest_path(start, finish)  
     distances = calculate_shortest_paths(start,finish)  
     (distances[finish] != Float::INFINITY)? distances[finish] : nil 
  end
  
       

  private  
  
  # Add a route to our directed graph hash. StartNode => EndNode = Distance
  # 
  # @param start [String] - Key for starting node in graph
  # @param dest [String] - Key for ending node in graph
  # @param distance [Fixnum] - Distance from start to dest
  def add_route(start,dest,distance)
    if(not @graph.has_key?(start))  # check for existance of 'station' first
      @graph[start] = {dest => distance}
    else
      @graph[start][dest] = distance                          
    end       
  end
  
  # Utility function for checking and returning the distance from a start node to an end node
  # 
  # @param start [String] - Key for starting node in graph
  # @param dest [String] - Key for ending node in graph
  # @return [Fixnum] or [Nil] 
  def find_dist(start,dest)
    (@graph[start] && @graph[start][dest])? @graph[start][dest] : nil 
  end
  
  # Implementation of Dijkstra's algorithm 
  # based on pseudocode found: http://en.wikipedia.org/wiki/Dijkstra's_algorithm
  # 
  # @param source [String] - Key for starting node in grap
  # @param finish [String] (optional) - Key for ending node in graph. Used in case source==finish. we don't want 0 distance
  # @return [Hash] - A hash of the shortest distances possible from the source node to all other nodes in the graph 
  def calculate_shortest_paths(source, finish = -1)
    distances= {}
    previous = {}
    
    @nodes.each do |i|
      distances[i] = Float::INFINITY
      previous[i] = -1  
    end	  

    distances[source] = 0
    q = @nodes.compact        # All nodes in the graph are unoptimized - thus are in Q
         
    if source == finish  
      #  In order to get back to the start, we must first travel somewhere.
      q.delete(source)
      distances[source] = Float::INFINITY
      @graph[source].each { |sibling, dist| distances[sibling] = dist }    
    end     
    
    while (q.size > 0)     # Main loop
      u = nil;                
      q.each do |min|
        if  (!u) or (distances[min] and (distances[min] < distances[u]))
          u = min          # vertex in Q with smallest distance in dist   
        end 
      end        

      if (distances[u] == Float::INFINITY)
        break              # all remaining vertices are inaccessible from source
      end   
      
      q.delete(u)
      @graph[u].keys.each do |v|
        alt = distances[u] + find_dist(u,v)
        if (!distances[v].nil? && alt < distances[v])
          distances[v] = alt
          previous[v]  = u      
        end  
      end # end keys loop
    end # end main while loop 
    distances #return our shortest distances object
  end

  # Recursive function used for traversing the graph
  # 
  # @param start [String] - Key for starting node in graph
  # @param finish [String] - Key for ending node in graph
  # @param options[:min_stops] [Fixnum] - Minimum number of stops
  # @param options[:max_stops] [Fixnum] - Maximum number of stops
  # @param options[:min_distance] [Fixnum] - Maximum distance allowed to travel
  # @param counters[:distance] [Fixnum] - varibale used to keep track of the total distance travelled
  # @param counters[:stops] [Fixnum] - varibale used to keep track of the total number of nodes visited
  # @param &cb [Proc] object used to inform calling function a route was sucessfully found
  def traverse_routes(start, finish, opts, counters = {:distance => 0, :stops => 0}, &cb)
    minimum_limit_check = counters[:stops] >= opts[:min_stops]
    maximum_limit_check = (counters[:distance] <= opts[:max_distance]) && (counters[:stops] <= opts[:max_stops])
    
    if start == finish and minimum_limit_check and maximum_limit_check 
      cb.call() # up the counter only if we are at our destination AND all the requirements are met
    end
      
    if maximum_limit_check   #keep going deeper if we havent reached our top limit
      @graph[start].each do |nxt, dist|
        updated_counters = {:distance => counters[:distance] + dist, :stops => counters[:stops] + 1}
        traverse_routes(nxt, finish, opts, updated_counters, &cb)
      end
    end
  end
  
end