science of board games

I have had a few requests come in for the code used in my previous Power Grid post, so I thought I would share it.

Well, the most important piece is Dijkstra's Algorithm for finding the shortest path between one node and all other nodes. Alternatively, you can use the Floyd–Warshall Algorithm for finding the shortest path between all points.

In Ruby, I implemented Dijkstra's in this way:

def dijkstra(graph, start)
  # initiliaze "infinite distances to everything"
  dist = Array.new(graph.length, 1000000000)
 
  # except the starting point
  dist[start] = 0
  cost = [0]
 
  # we haven't visited anywhere
  visited = Array.new(graph.length, false)
 
  # start with the start node
  queue = [start]
 
  while queue.length > 0
    queue = queue.sort { |x,y| dist[x] <=> dist[y] }
    node = queue.delete_at(0)
    if visited[node] == false
      visited[node] = true
      cost += [dist[node]]
      dist[node] = 0
      0.upto(dist.length - 1) { |t|
        if visited[t] == false
          dist[t] = dist[node] + graph[node][t] if dist[node] + graph[node][t] < dist[t]
          queue += [t] if queue.index(t) == nil
        end
      }
    end
  end
  totcost = 0
  0.upto(16) { |x|  totcost += cost[x] }
  return totcost
end
 

This will spit out the cost to build to 17 cities from a starting point (not including the actual building cost of 10/15/20).

The most annoying part is typing in all of the city links and cost. Here is my Ruby code for that:

$places = ['Oklahoma City', 'Dallas', 'Houston', 'New Orleans', 'Memphis', 'Kansas City', 'San Diego', 'Los Angeles', 'San Francisco', 'Las Vegas', 'Phoenix', 'Santa Fe', 'Salt Lake City', 'Denver', 'Cheyenne', 'Billings', 'Boise', 'Portland', 'Seattle', 'Omaha', 'Fargo', 'Duluth', 'Minneapolis', 'Chicago', 'Cincinatti', 'St. Louis', 'Knoxville', 'Detroit', 'Buffalo', 'Boston', 'New York', 'Pittsburgh', 'Washington', 'Norfolk', 'Philadelphia', 'Raleigh', 'Savannah', 'Atlanta', 'Birmingham', 'Miami', 'Tampa', 'Jacksonville']
 
$map = Array.new($places.length) { Array.new($places.length, 1000000) }
 
def addlink(a, b, c)
  $map[$places.index(a)][$places.index(b)] = c
  $map[$places.index(b)][$places.index(a)] = c
end
 
addlink('Oklahoma City', 'Kansas City', 8 )
addlink('Oklahoma City', 'Dallas', 3 )
addlink('Oklahoma City', 'Memphis', 14 )
addlink('Oklahoma City', 'Santa Fe', 15 )
addlink('Dallas', 'Houston', 5 )
addlink('Dallas', 'New Orleans', 12 )
addlink('Dallas', 'Memphis', 12 )
addlink('Dallas',  'Santa Fe', 16 )
addlink('Houston', 'New Orleans', 8 )
addlink('Houston', 'Santa Fe', 21 )
addlink('New Orleans', 'Birmingham', 11 )
addlink('New Orleans', 'Memphis', 7 )
addlink('New Orleans', 'Jacksonville', 16 )
addlink('Memphis', 'Birmingham', 6 )
addlink('Memphis', 'Kansas City', 12 )
addlink('Memphis', 'St. Louis', 7 )
addlink('Birmingham', 'Jacksonville', 9 )
addlink('Birmingham', 'Atlanta', 3 )
addlink('Kansas City', 'Santa Fe', 16 )
addlink('Kansas City', 'Denver', 16 )
addlink('Kansas City', 'Omaha', 5 )
addlink('Kansas City', 'Chicago', 8 )
addlink('Kansas City', 'St. Louis', 6 )
addlink('Santa Fe', 'Phoenix', 18 )
addlink('Santa Fe', 'Las Vegas', 27 )
addlink('Santa Fe', 'Salt Lake City', 28 )
addlink('Santa Fe', 'Denver', 13 )
addlink('Phoenix', 'Las Vegas', 15 )
addlink('Phoenix', 'San Diego', 14 )
addlink('San Diego', 'Los Angeles', 3 )
addlink('San Diego', 'Las Vegas', 9 )
addlink('Los Angeles', 'Las Vegas', 9 )
addlink('Los Angeles', 'San Francisco', 9 )
addlink('San Francisco', 'Las Vegas', 14 )
addlink('San Francisco', 'Salt Lake City', 27 )
addlink('San Francisco', 'Boise', 23 )
addlink('San Francisco', 'Portland', 24 )
addlink('Las Vegas', 'Salt Lake City', 18 )
addlink('Salt Lake City', 'Denver', 21 )
addlink('Salt Lake City', 'Boise', 8 )
addlink('Boise', 'Portland', 13 )
 
addlink('Boise', 'Seattle', 12 )
addlink('Boise', 'Billings', 12 )
addlink('Boise', 'Cheyenne', 24 )
addlink('Portland', 'Seattle', 3 )
addlink('Seattle', 'Billings', 9 )
addlink('Billings', 'Cheyenne', 9 )
addlink('Billings', 'Fargo', 17 )
addlink('Billings', 'Minneapolis', 18 )
addlink('Billings', 'Cheyenne', 9 )
addlink('Cheyenne', 'Denver', 0 )
addlink('Cheyenne', 'Omaha', 14 )
addlink('Cheyenne', 'Minneapolis', 18 )
addlink('Fargo', 'Duluth', 6 )
addlink('Fargo', 'Minneapolis', 6 )
addlink('Duluth', 'Minneapolis', 5 )
addlink('Duluth', 'Chicago', 12 )
addlink('Duluth', 'Detroit', 15 )
addlink('Minneapolis', 'Chicago', 8 )
addlink('Chicago', 'Detroit', 7 )
addlink('Chicago', 'Cincinatti', 7 )
addlink('Chicago', 'St. Louis', 10 )
addlink('St. Louis', 'Cincinatti', 12 )
addlink('St. Louis', 'Atlanta', 12 )
addlink('Cincinatti', 'Knoxville', 6 )
addlink('Cincinatti', 'Detroit', 4 )
addlink('Cincinatti', 'Raleigh', 15 )
addlink('Cincinatti', 'Pittsburgh', 7 )
addlink('Atlanta', 'Knoxville', 5 )
addlink('Atlanta', 'Savannah', 7 )
addlink('Atlanta', 'Raleigh', 7 )
addlink('Savannah', 'Jacksonville', 0 )
addlink('Savannah', 'Raleigh', 7 )
addlink('Jacksonville', 'Tampa', 4 )
addlink('Tampa', 'Miami', 4 )
addlink('Raleigh', 'Norfolk', 3 )
addlink('Raleigh', 'Pittsburgh', 7 )
addlink('Norfolk', 'Washington', 5 )
addlink('Washington', 'Pittsburgh', 6 )
addlink('Washington', 'Philadelphia', 3 )
addlink('Pittsburgh', 'Detroit', 6 )
addlink('Pittsburgh', 'Buffalo', 7 )
addlink('Detroit', 'Buffalo', 7 )
addlink('Buffalo', 'New York', 8 )
addlink('New York', 'Philadelphia', 0 )
addlink('New York', 'Boston', 3 )
 
0.upto($map.length-1) { |x| $map[x][x] = 0 }
 
$usmap = $map.dup
$usplaces = $places.dup

I threw that into a file named pg-map-us.rb, and then loaded the previous function and ran this short Ruby script (and then piped it through sort) to output the table:

0.upto($usmap.length-1) { |s|
  puts '
<tr>
<td> ' + dijkstra($usmap, s).to_s + ' </td>
<td>' + $usplaces[s] + '</td>
</tr>
 
'
}

Have fun!