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.
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:
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:
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!