8
$\begingroup$

Create a list of US-state names with one state name per line, so that no two distinct lines on your list contain a common letter. Let $L$ be sum of the lengths of all the state names on your list (blanks/spaces are not counted).

What is the largest possible value for $L$?

$\endgroup$
  • $\begingroup$ I don't have an answer yet, but I have a useful tip for all those trying to find a solution. I suggest to compress the name of each state removing the repeated letters and sorting them alphabetically. For example: Alabama -> ABLM Ohio -> HIO Delaware -> ADELRW $\endgroup$ – leoll2 Mar 18 '15 at 17:07
13
$\begingroup$

Best I could find was 22.

Mississippi
New York
Utah

If Avarind is correct that the best answer has three states, then we can quickly brute force each 3 state combination to find the result. Sample Python implementation:

import itertools

seq = ["Alabama", "Alaska", "Arizona", "Arkansas", "California", "Colorado", "Connecticut", "Delaware", "Florida", "Georgia", "Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", "Kansas", "Kentucky", "Louisiana", "Maine", "Maryland", "Massachusetts", "Michigan", "Minnesota", "Mississippi", "Missouri", "Montana", "Nebraska", "Nevada", "New Hampshire", "New Jersey", "New Mexico", "New York", "North Carolina","North Dakota", "Ohio", "Oklahoma", "Oregon", "Pennsylvania", "Rhode Island", "South Carolina", "South Dakota", "Tennessee", "Texas", "Utah", "Vermont", "Virginia", "Washington", "West Virginia", "Wisconsin", "Wyoming"]

def shares_letters(a,b):
    return bool(set(a.replace(" ", "").lower()) & set(b.replace(" ", "").lower()))

size = lambda x: len("".join(item.replace(" ", "") for item in x))

print max([candidate for candidate in itertools.permutations(seq, 3) if all(not shares_letters(*pair) for pair in itertools.permutations(candidate,2))], key=size)

Result:

('Mississippi', 'New York', 'Utah')
$\endgroup$
  • 1
    $\begingroup$ For others looking to improve, best possible is 3 states because every state has either the letter a, or the letter i, or both the letters "e" and "n". Making this partition and checking a few possibilities might help to confirm if this is the best. $\endgroup$ – Aravind Mar 18 '15 at 17:11
  • 1
    $\begingroup$ Texas - Wyoming - Utah - New York is an example of 4 consecutive states. $\endgroup$ – leoll2 Mar 18 '15 at 17:38
  • 1
    $\begingroup$ @leoll2, I think we are interpreting the question two different ways. By my reckoning, Texas and Utah can't be in an answer together because they both contain an A. $\endgroup$ – Kevin Mar 18 '15 at 17:43
  • 1
    $\begingroup$ Probably you're right. After reading the problem twice, I realized that the author didn't say two consecutive lines, but two different lines. So, I was solving a completely different (and much more difficult) problem eheh. Well, I'll publish my variation of the problem asap. Thanks. $\endgroup$ – leoll2 Mar 18 '15 at 17:51
  • $\begingroup$ @Aravind: Interestingly, even if one regards upper and lower case letters as distinct I don't think that helps go beyond three, since no state contains an uppercase "E", and every state that contains an uppercase "A" also contains a lowercase one. It would allow one to include both "Mississippi" and "Iowa", but that doesn't help unless one can also include some state that starts with an uppercase "A" and doesn't contain a lowercase one. $\endgroup$ – supercat Mar 18 '15 at 23:00
12
$\begingroup$

Best I got is 42:

State of Rhode Island and Providence Plantations

$\endgroup$
  • $\begingroup$ Eheh definitely the funniest answer ever! $\endgroup$ – leoll2 Mar 18 '15 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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