12
$\begingroup$

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?

$\endgroup$
8
  • 1
    $\begingroup$ Everyone is so concerned with "gender neutrality" while nobody calls for "country neutrality" ^^|| (Please understand this comment correctly: I'm not claiming that we need country neutrality.) $\endgroup$
    – WhatsUp
    Commented Jan 31, 2022 at 1:33
  • $\begingroup$ @WhatsUp I will say, the original question came about as a "misunderstanding" around the title of this CGCC challenge which is why it's US states, rather than any other geographical region $\endgroup$ Commented Jan 31, 2022 at 1:48
  • 1
    $\begingroup$ 52 is not an unquestionably small number, but it's still quite a ways away from infinite. $\endgroup$
    – Bass
    Commented Jan 31, 2022 at 15:31
  • $\begingroup$ For doubling back, I'd say: Massachusetts, New Hampshire, Massachusetts, Rhode Island, Connecticut = 63. $\endgroup$ Commented Jan 31, 2022 at 15:53
  • $\begingroup$ @DarrelHoffman See the example given: that only uses 4 states, and double counts Massachusetts $\endgroup$ Commented Jan 31, 2022 at 20:34

3 Answers 3

15
$\begingroup$

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

enter image description here

$\endgroup$
4
  • $\begingroup$ Nice abuse of the rules. $\endgroup$
    – Joshua
    Commented Feb 1, 2022 at 1:17
  • $\begingroup$ Looks like a Poisson distribution that starts at 6 :) $\endgroup$ Commented Feb 1, 2022 at 5:12
  • 2
    $\begingroup$ Nice subversion of the OP's assumption that everyone would think they meant the USA. $\endgroup$
    – Rosie F
    Commented Feb 1, 2022 at 9:46
  • $\begingroup$ As a resident of Schleswig-Holstein I simply have to upvote this. $\endgroup$
    – z00l
    Commented Feb 1, 2022 at 11:52
8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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
$\endgroup$
2
  • 1
    $\begingroup$ Would it be possible for you to include your code, potentially as a link if necessary? $\endgroup$ Commented Jan 31, 2022 at 0:41
  • $\begingroup$ @cairdcoinheringaahing Done. The non-cyclic paths used a slightly modified version of the traversal. $\endgroup$ Commented Jan 31, 2022 at 1:01

Your Answer

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

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