Longest infinite loop of 5 states

Question

This is based on a question I posed in The Nineteenth Byte:

What group of 5 states have the longest total name, under the constraint that you must be able to travel from one state to another in the group, and form a cycle where you return the original start?

For example, California → Oregon → Washington → Idaho → Nevada → California forms such a loop, and the string CaliforniaOregonWashingtonIdahoNevada is 37 characters long. Note that this means states must have a land border, so Alaska and Hawaii cannot be included. However, something like Michigan → Indiana → Illinois → Iowa → Wisconsin would be valid, as each subsequent state in the loop shares a land border with the previous one, even though Michigan is split into two land masses.

Subsequent discussion lead to DLosc and emanresu A finding multiple different loops of 52 characters:

North Carolina -> South Carolina -> Georgia -> Tennessee -> Virginia
West Virginia -> Virginia -> North Carolina -> Tennessee -> Kentucky
Massachusetts -> New Hampshire -> Vermont -> New York -> Connecticut

However, it hasn't yet been shown that this is the maximum possible length. Are you able to find and prove the maximal length?

---

For further consideration, there are generalisations that are also worth thinking about:

• What about for loops of different n states? Is there any link between n and the resulting maximum length?

• How does "doubling back" affect the maximum possible length, where you can include a state more than once in order to reach other states:

  e.g. New York -> New Jersey -> Connecticut -> Massachusetts -> Vermont is allowed, doubling back through NY to get from NJ to Connecticut _Source

  This does increase the maximum length, as we can now get a 57 character solution:

  Connecticut -> Rhode Island -> Massachusetts -> New Hampshire -> (MA ->) New York

  _{Found by DLosc}

• Are there any particular different regions which give interesting answers, using a similar delineation as states? For example, what if we're considering countries of the world instead of US states?

Answer 1

You didn't specify the country, so I can easily beat this :-)

Mecklenburg-Vorpommern -> Schleswig-Holstein -> Niedersachsen -> Sachsen-Anhalt -> Brandenburg = 78

Another good contender would be a more western loop

Nordrhein-Westfalen -> Rheinland-Pfalz -> Baden-Württemberg -> Hessen -> Niedersachsen = 70

If you don't require going back to your original state we can do

"Mecklenburg-Vorpommern -> Schleswig-Holstein -> Niedersachsen -> Nordrhein-Westfalen -> Rheinland-Pfalz" = 87

Since Germany has only 16 states, this was done with a highly scientific method of "eyeballing" it.

The distribution of the name lengths is certainly unusual, it certainly doesn't look like a normal distribution at all

Answer 2

I was pretty sure the three loops we found were optimal and were the only 52-character loops, but I figured why not write a program to verify it.

Here is the core of my loop search code (written in Python 3):

LOOP_SIZE = 5
MIN_LENGTH = 50

def find_loops(starting_state, loop=None):
  if not loop:
    loop = [starting_state]
  if len(loop) == LOOP_SIZE:
    if starting_state in NEIGHBORS[loop[-1]]:
      yield loop
  else:
    for neighbor in NEIGHBORS[loop[-1]]:
      if neighbor not in loop:
        yield from find_loops(starting_state, loop + [neighbor])

def loop_len(loop):
  return sum(len(NAMES[state]) for state in loop)

# After generating the loops, we'll put them in a set to remove duplicates
long_loops = set()

for starting_state in NAMES:
  for loop in find_loops(starting_state):
    length = loop_len(loop)
    if length > MIN_LENGTH:
      loop_states = tuple(sorted(loop))
      long_loops.add((length, loop_states))

for length, states in sorted(long_loops):
  print(f"{length}:", ", ".join(NAMES[state] for state in states))

And sure enough, when we run it, it comes up with three 51-character loops and three 52-character loops:

51: Alabama, Georgia, North Carolina, South Carolina, Tennessee
51: Connecticut, Massachusetts, New York, Rhode Island, Vermont
51: Delaware, Maryland, New Jersey, Pennsylvania, West Virginia
52: Connecticut, Massachusetts, New Hampshire, New York, Vermont
52: Georgia, North Carolina, South Carolina, Tennessee, Virginia
52: Kentucky, North Carolina, Tennessee, Virginia, West Virginia

(The states are in alphabetical rather than loop order.)

---

Here are some results for different loop sizes:

• 2 states: max length 28 (North Carolina -> South Carolina)
• 3 states: max length 36 (Massachusetts -> Rhode Island -> Connecticut)
• 4 states: max length 44 (Massachusetts -> Rhode Island -> Connecticut -> New York and North Carolina -> South Carolina -> Georgia -> Tennessee)
• 5 states: max length 52 (three loops previously mentioned)
• 6 states: max length 64 (Massachusetts -> Rhode Island -> Connecticut -> New York -> Vermont -> New Hampshire)
• 7 states: max length 73 (North Carolina -> South Carolina -> Georgia -> Tennessee -> Kentucky -> West Virginia -> Virginia
• 8 states: max length 81 (same as the 7-state loop but with the addition of either Missouri or Maryland)

The common theme seems to be the two groups represented by the 2- and 3-state loops: North Carolina/South Carolina and Massachusetts/Rhode Island/Connecticut. Unsurprisingly, all five of these states have names longer than 10 characters.

The 5-state loops are actually the outlier here: in two out of the three longest loops, neither of these core groups is present in full. One loop contains Connecticut and Massachusetts but no Rhode Island, and one loop contains North Carolina but no South Carolina. The third loop does contain both Carolinas.

Answer 3

The given paths are of maximal length, as confirmed by my own graph traversal code, available on pastebin:

Connecticut -> Massachusetts -> New Hampshire -> Vermont -> New York = 52
Georgia -> South Carolina -> North Carolina -> Virginia -> Tennessee = 52
Kentucky -> Tennessee -> North Carolina -> Virginia -> West Virginia = 52

Without the restriction that the path be cyclic, we have direct paths of greater length:

New Hampshire -> Massachusetts -> New York -> Pennsylvania -> West Virginia = 59
Pennsylvania -> West Virginia -> Virginia -> North Carolina -> South Carolina = 61