# State Abbreviations Graph

In a recent chat that I participated in, we were discussing US two-letter state abbreviations that were one letter off of each other (e.g., NY and NJ).

After that discussion, I was curious about whether it would be possible to step from any state abbreviation to any other by changing one letter at a time, using only valid states along the way. My first step was to determine if there were any state abbreviations which didn’t share a first or last letter with any other states, so I wrote a simple Ruby script to test that.

``````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 == s || sc == s)
}
puts "#{sc}: #{one_letter_changes[sc].join(", ")}"
end
``````

So every state had at least one other state it could go to. Texas (TX) had the fewest, with only Tennessee (TN); Massachusetts (MA) had the most, as quite a few state codes start with M or end with A.

Now I needed to find out if all the states would connect to each other, or if there would be several distinct “neighborhoods” of states. I decided to do this visually by creating a graph, using the output of my script to draw the connections: Green lines connect state abbreviations with the same first letter, and blue lines connect state abbreviations with the same second letter.

Based on this graph, it is possible for any state abbreviation to change to any other state abbreviation!

I was also curious about the number of steps needed to go between any pair of state abbreviations, so I wrote a path distance algorithm based on Dijkstra’s algorithm (but with each path having equal weight) to find the shortest number of hops between any pair:

``````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 == s || sc == s)
}
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}
puts "#{code}  #{values.join("  ")}"
end
puts "   #{state_codes.join(" ")}"
``````

Based on the results, the highest number of hops is 6—so every state abbreviation can be changed into any other state abbreviation in at most six steps!

Tags: