# Travel in the USA

If you decide to travel from state to state in US in alphabetical order how many states can you cover if:

The state you are in must share a border with the previous state. The last state in your list need not share the border with the very first state you started from. Your answer should show a minimum of 7 states. Highest number gets the tick.

Note: States starting with same letter will be considered in alphabetical order per their following letters. Also you can start with ANY letter.

• How do you consider the 4 corners points in the SouthWest ? en.wikipedia.org/wiki/Four_Corners_Monument Do Utah and New Mexico share a border ? Arizona and Colorado ? Feb 21, 2022 at 14:52
• Any touching point is sharing border
– DrD
Feb 21, 2022 at 14:55
• Correct me if I'm wrong, but with the newly added edit, doesn't that mean you can just do all 50 ? Feb 21, 2022 at 15:03
• As long as they share a border.
– DrD
Feb 21, 2022 at 15:04
• Well, yeah, 48/50, but it defeats the point of alphabetical order :( Feb 21, 2022 at 15:06

The longest path problem, while NP-hard in general, is actually pretty easy to solve on directed acyclic graphs, which is what we have here:

• Directed: out of two neighbouring states, one is before the other in the alphabet, so the travel direction is one-way
• Acyclic: Since we can't go backwards in the alphabet, we can't get back to any state we've already visited

Let's see if we can't run the algorithm manually.

First, we'll need to find a topological order (no paths backwards anywhere in the list) for the states. There are several simple ways to find one on any DAG, but in our case, the alphabetical order already guarantees this property, so we get past this step for free.

Then, for each state, we check all the incoming paths (ie. that state's neighbours that are earlier than it in the alphabet). We set the state's LPEH (Longest Path Ending Here) as the maximum LPEH of the incoming paths, plus one. We also record the incoming path(s) we used for future reference.

State           Best Neighbour(s)   LPEH
- - - - - - - - - - -  - - - - - - - - - -
Alabama         -                   1
Arizona         -                   1
Arkansas        -                   1
California      Arizona             2
Connecticut     -                   1
Delaware        -                   1
Florida         Alabama             2
Georgia         Florida             3
Hawaii          -                   1
Idaho           -                   1
Illinois        -                   1
Indiana         Illinois            2
Iowa            Illinois            2
Kentucky        Indiana             3
Louisiana       Arkansas            2
Maine           -                   1
Maryland        Delaware            2
Massachusetts   Connecticut         2
Michigan        Indiana             3
Minnesota       Michigan            4
Mississippi     Louisiana           3
Missouri        Kansas,Kentucky     4
Montana         Idaho               2
New Hampshire   Massachusetts       3
New Jersey      Delaware            2
New York        Massachusetts, NJ   3
North Carolina  Georgia             4
North Dakota    Minnesota           5
Ohio            Kentucky, Michigan  4
Oklahoma        Missouri            5
Pennsylvania    Ohio                5
Rhode Island    New York            4
South Carolina  North Carolina      5
Tennessee       Missouri, NC        5
Texas           Oklahoma            6
Vermont         New Hampshire, NY   4
Virginia        Tennessee           6
Washington      Oregon              5
West Virginia   Virginia            7
Wisconsin       Minnesota           5
Wyoming         South Dakota        7


Then we pick the state(s) with the largest LPEH, and trace our route backwards using the Best Neighbour(s) list:

* West Virginia - Virginia - Tennessee - North Carolina - Georgia - Florida - Alabama
* West Virginia - Virginia - Tennessee - Missouri - Kansas - Colorado - Arizona
* West Virginia - Virginia - Tennessee - Missouri - Kentucky - Indiana - Illinois
* Wyoming - South Dakota - Nebraska - Missouri - Kansas - Colorado - Arizona
* Wyoming - South Dakota - Nebraska - Missouri - Kentucky - Indiana - Illinois
* Wyoming - South Dakota - North Dakota - Minnesota - Michigan - Indiana - Illinois

And unless we made a mistake along the way (not at all impossible, this is clearly a job for computers), reading those from right to left we get the complete list of the possible maximum routes.

For the question about "is the answer the same (but reversed) if the alphabet were reversed: Yes. All the same links would be there, every single one of them reversed. (Incidentally, this means we can also run the algorithm "in reverse gear" to find the answer, which is useful sometimes.)

• Maybe I'm missing something but given you can loop can't you move on from either of your last states? Feb 22, 2022 at 16:48
• @Mohirl What gives you the idea that you can loop? (Loop around the alphabet is what I'm guessing you mean.)
– Bass
Feb 22, 2022 at 16:53
• Sorry, the original version of the question stated you could loop from e.g. W back to A, C, D etc. I hadn't noticed it had been edited to remove that condition. Feb 23, 2022 at 10:41
• Ah ok, that's always the problem with OP changing the question after it's been posted. Glad OP chose this version though, the alphabet choice would give exactly the same boring busywork, just more of it. (Except if more than one loop was allowed, of course; in that case the alphabetical restriction would effectively cease to exist at all, and we would have reached the NP-hard (read: non-puzzle) territory.)
– Bass
Feb 23, 2022 at 11:23

Chain of seven with

Arizona > Colorado > Kansas > Missouri > Tennessee > Virgina > West Virgina (Accidental dupe of Evargalo)

Or another seven with

Arizona > Colorado > Kansas > Missouri > Nebraska > South Dakota > Wyoming

And another with

Illinois > Indiana > Michigan > Minnesota > North Dakota > South Dakota > Wyoming

I've at least found a chain of seven, to start

Illinois -> Indiana -> Kentucky -> Missouri -> Nebraska -> South Dakota -> Wyoming

An opening bid with

7

states:

Alabama, Florida, Georgia, North Carolina, Tennessee, Virginia, West Virginia

Alternatively,

Arizona, Colorado, Kansas, Missouri, Tennessee, Virginia, West Virginia