state-abbreviations-graph.rb

state_codes = %w(AL AK AZ AR CA CO CT DE FL GA HI ID IL IN IA KS KY LA ME MD MA MI MN MS MO MT NE NV NH NJ NM NY NC ND OH OK OR PA RI SC SD TN TX UT VT VA WA WV WI WY)
state_codes.sort!
one_letter_changes = Hash.new()
state_codes.each do |sc|
  one_letter_changes[sc] = state_codes.select{|s| sc != s && (sc[0] == s[0] || sc[1] == s[1])}
end

def path_distance(graph, source)
  vertexes = graph.keys
  return nil unless vertexes.include?(source)
  
  distance = Hash.new()
  previous_vertex = Hash.new()
  arbitrarily_large_distance = vertexes.length
  unvisited_vertices = Array.new

  vertexes.each do |v|
    distance[v] = arbitrarily_large_distance
    previous_vertex[v] = nil
    unvisited_vertices.push(v)
  end
  distance[source] = 0;

  while(unvisited_vertices.any?)
    min_distance_vertex = unvisited_vertices.min_by{|v| distance[v]}
    
    graph[min_distance_vertex].each do |neighbor|
      alt = distance[min_distance_vertex] + 1
      if alt < distance[neighbor]
        distance[neighbor] = alt
        previous_vertex[neighbor] = min_distance_vertex
      end
    end
    unvisited_vertices -= [min_distance_vertex]
  end

  return distance

end

state_codes.each do |code|
  values = path_distance(one_letter_changes, code).sort_by{|k,v| k}.reject{|k,v| k > code}.map{|d| d[1]}
  puts "#{code}  #{values.join("  ")}"
end
puts "   #{state_codes.join(" ")}"