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$?

Improve this question
$\endgroup$
1
  • $\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, 2015 at 17:07

2 Answers 2

Reset to default
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')
Improve this answer
$\endgroup$
5
  • 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, 2015 at 17:11
  • 1
    $\begingroup$ Texas - Wyoming - Utah - New York is an example of 4 consecutive states. $\endgroup$
    – leoll2
    Mar 18, 2015 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, 2015 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, 2015 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, 2015 at 23:00
13
$\begingroup$

Best I got is 42:

State of Rhode Island and Providence Plantations

Improve this answer
$\endgroup$
1
  • $\begingroup$ Eheh definitely the funniest answer ever! $\endgroup$
    – leoll2
    Mar 18, 2015 at 16:53

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.