     ## Ticket to Ride Helper App: pre Alpha release Leave Comment
Alrighty then. After much floundering about (diminishing returns on programming achievement apparently decrease rapidly for me post 11 PM), I have the initial cut of the algorithm that underlies this application. For the introduction and cities flat file, see this previous post. Those of you familiar with the game know that shortest path by train length itself is not always the best route since tunnels and colors can have great effects on your play. For now those are non existent, shortest path only, the rest TBD.

Algorithm: Dijkstra's algorithm
TLDR: Global optimum shortest path. O(V2)

Next step is to throw a GUI on this. While the interesting part is done, everyone loves GUIs, less love for the command line I've found. Here is the core code:

```#todo add colors, tunnels, maps, etc
class Edge
attr_accessor :visited, :distance
def initialize(name, length)
@name = name
@length = length
@visited = false
@distance = 999 #sufficient to represent infinity, longest route is 8
end

def to_s
"[#{@name}, #{@length}]"
end
end

class Board
def initialize
@error = false
puts "Building graph..."
build_graph
verify_graph
end

def reset
puts "Resetting board"
entry.each do |edge|
edge.visited = false
edge.distance = 999
end
end
end

def find_path(start, finish)
if start == finish
puts "Shortest path cost from #{start} to #{finish}: 0"
return
end
if cur_node_edge_list == nil or dest_node_edge_list == nil
puts "ERROR start or dest node not in graph"
return
end
puts "Calculating shortest route from #{start} to #{finish}..."
cur_node = cur_node_edge_list
dest_node = dest_node_edge_list

cur_node.distance = 0
start_node = cur_node
while dest_node.visited == false
next_node = nil
cur_node_edge_list.each do |edge|
if edge.name == cur_node.name then next end
if edge.visited == false
tenative_distance = cur_node.distance + edge.length.to_i
if tenative_distance < edge.distance
edge.distance = tenative_distance
#update all nodes in the list, TODO make one master node list for ref
listing.each do |item|
if item.name == edge.name then item.distance = edge.distance end
end
end
end #distance update
end #visited == false
end #cur_node edge list

cur_node.visited = true
#need to set visited true for each copy of this edge in the list
#yes inefficient, todo fix later
node.each do |city|
if city.name == cur_node.name
city.visited = true
city.distance = cur_node.distance
end
end
end

#determine next node, must be unvisited
#shortest distance for any edge connected to any visited node
if node.visited == true
node.each do |city|
if city.name == cur_node.name then next end
if next_node == nil and not city.visited then next_node = city end
if not city.visited and next_node != nil and city.distance < next_node.distance
next_node = city
end #if
end #city do
end #visited list include check
end #node
cur_node = next_node
if cur_node == nil then break end #we hit the destination
end #while dest.visited == false

puts "Shortest path cost from #{start} to #{finish}: #{dest_node.distance}"
#start at dest and work backwards
temp = dest_node
path = []
path << temp
while temp.name != start_node.name
dest_node_edge_list.each do |edge|
#don't check origin node
if edge.name == temp.name then next end
#clever me: find the shortest node by subtracting the edge length
#from the total distance calculated for the node we're looking at
#it should match the node that is in the shortest path
if ((temp.distance - edge.length.to_i) == edge.distance)
temp = edge
end
end
path << temp
end
path.reverse!
puts "#{path}"
end #find_path

def print_graph
puts "#{x}:   \t#{x}"
end #do
end #print_graph

private

def build_graph
city_file = File.new("cities.distances")
contents = line.split
#odd: origin city + [destinations+length...]
if (contents.size % 2 == 0) then puts "Should be odd -  Error in file" end
#add the node itself as the first element in the edge map
i = 1
while i <= (contents.size-2)
@adj_list[contents] << Edge.new(contents[i], contents[i+1]) #make these Edge objects
i = i + 2
end
end
end #build_graph

def verify_graph
#verify that there are no spelling errors or such with the data set
#edges that do not exist
origin.each do |edge|
@error = true
puts "ERROR in data set: #{origin}: #{edge.name} check spelling?"
end
end
end
end #verify graph
end #Board

```

Notes: there are few things I could do to optimize, most notably have a master node list that is referenced for updates rather than update each node object in each list, but there are only 47 cities in the Europe map which is 2209 combinations and the current code can process them all in 13.875794 seconds.

Stats
Ruby 1.9.3
Intel Core i7 Q720 @ 1.6Ghz [laptop]
4.00 GB RAM

This doesn't take into account that X->Y is the same as Y->X and that calculation could be stored and retrieved rather than recalculated. Additionally any calculation could be stored for later lookup and thus with persistent storage the app would only ever do 2209 calculations.

Driver:

```test = Board.new
#misc test paths
#test.find_path("Zurich", "Edinburgh")
#test.reset
#test.reset
#test.find_path("Munchen", "Smolensk")
#test.reset
#test.find_path("Zurich", "Paris")
#test.reset
#test.find_path("Paris", "Paris")
#test.reset
#test.reset
#test.reset
#test.find_path("Lisboa", "Erzurum")
#test.reset

start = Time.now
#do every combination test
test.find_path(node,other)
test.reset
end
end
puts "Executed all permutations in #{Time.now - start} seconds..."

```

--

S M T W T F S
12
3456789
10111213141516
1718 19 20212223
24252627282930
31

### Recent Entries

• • • • • • • • • • ### 0 user(s) viewing

0 Guests
0 member(s)
0 anonymous member(s)