3
$\begingroup$

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.

If you go in reverse alphabetical order would the answer be the reverse of your answer?

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

enter image description here

Improve this question
$\endgroup$
8
  • $\begingroup$ 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 ? $\endgroup$
    – Evargalo
    Feb 21, 2022 at 14:52
  • 1
    $\begingroup$ Any touching point is sharing border $\endgroup$
    – DrD
    Feb 21, 2022 at 14:55
  • 1
    $\begingroup$ Correct me if I'm wrong, but with the newly added edit, doesn't that mean you can just do all 50 ? $\endgroup$
    – Auribouros
    Feb 21, 2022 at 15:03
  • $\begingroup$ As long as they share a border. $\endgroup$
    – DrD
    Feb 21, 2022 at 15:04
  • $\begingroup$ Well, yeah, 48/50, but it defeats the point of alphabetical order :( $\endgroup$
    – Auribouros
    Feb 21, 2022 at 15:06

4 Answers 4

Reset to default
8
$\begingroup$

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
Alaska          -                   1
Arizona         -                   1
Arkansas        -                   1
California      Arizona             2
Colorado        Arizona             2
Connecticut     -                   1
Delaware        -                   1
Florida         Alabama             2
Georgia         Florida             3
Hawaii          -                   1
Idaho           -                   1
Illinois        -                   1
Indiana         Illinois            2
Iowa            Illinois            2
Kansas          Colorado            3
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
Nebraska        Missouri            5
Nevada          California          3
New Hampshire   Massachusetts       3
New Jersey      Delaware            2
New Mexico      Colorado            3
New York        Massachusetts, NJ   3
North Carolina  Georgia             4
North Dakota    Minnesota           5
Ohio            Kentucky, Michigan  4
Oklahoma        Missouri            5
Oregon          Nevada              4
Pennsylvania    Ohio                5
Rhode Island    New York            4
South Carolina  North Carolina      5
South Dakota    Nebraska, ND        6
Tennessee       Missouri, NC        5
Texas           Oklahoma            6
Utah            Nevada, New Mexico  4
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.)

Improve this answer
$\endgroup$
4
  • $\begingroup$ Maybe I'm missing something but given you can loop can't you move on from either of your last states? $\endgroup$
    – Mohirl
    Feb 22, 2022 at 16:48
  • $\begingroup$ @Mohirl What gives you the idea that you can loop? (Loop around the alphabet is what I'm guessing you mean.) $\endgroup$
    – Bass
    Feb 22, 2022 at 16:53
  • $\begingroup$ 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. $\endgroup$
    – Mohirl
    Feb 23, 2022 at 10:41
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Bass
    Feb 23, 2022 at 11:23
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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

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

Improve this answer
$\endgroup$
1
$\begingroup$

An opening bid with

7

states:

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

Alternatively,

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.