The 8 Possessions of the United States
The first thing I learned on Friday was about all of the U.S. possessions. Can you name them all? I could have only named a few, and I would have incorrectly named a couple extra. Here they are in alphabetical order according to their abbreviation.
- AS: American Samoa
- FM: Federated States of Micronesia
- GU: Guam
- MH: Marshall Islands
- MP: Northern Mariana Islands
- PR: Puerto Rico
- PW: Palau
- VI: Virgin Islands
So, throw in DC, and we have 59 abbreviations to work with. Need a quick reference? Here is the Postal Explorer.
The Game
Beginning with any of the U.S. state or possession abbreviations, try and create the longest string of characters in the following way. Suppose we start with KS (Kansas). We look at the second letter, ‘S’, and find a state abbreviation that begins with that letter. Say, South Dakota. Now, we have ‘KSD’.
We continue this process, making sure we do not repeat states. Once you use a state’s abbreviation, you cannot use it again. Perhaps you might use DC, and then CO, and then OK, and then KY, for ‘KSDCOKY’.
States That End the Game
After thinking about how the game works, you can quickly deduce you don’t want to use the states AZ, DE, KY, ME, NE, NJ, NY, TX, and WY until the very end since they end with letters that no state or possession begins with.
How to Use Recursion
Recursion is such a powerful trick to pull on a computer. Here is how I used it to give me the longest string. I wanted to build a function that would take a string and a set of abbreviations as inputs with the following restriction. If the string “KS” was the single string input then the set of abbreviations cannot include “KS”. Similarly, if the string “KSCOH” was the single string input, then the set of abbreviations cannot include “KS”, “SC”, “CO”, nor “OH”. The output of the function is intended to be the longest possible string you can produce from the one given.
Here is how the logic goes. Suppose this function is called Longest_String. I may define a set called Set6. It is the set of all abbreviations except KS, SC, CO, OH, and HI. When I call the function, it might look something like this: Longest_String(“KSCOHI”, Set6).
Within the function, I first assume that the string that was the input is the longest one and measure the number of characters of that string. For example, if the input is “KSCOHI”, we set that as the largest string and set the number of characters to 6.
Now, we search through the set of abbreviations given to us for things that start with ‘I’. This is what we’ll call our loop set. It will contain IA, ID, IN, and IL.
We create a loop that will go through each of these states and call the function we are defining!! When we get to IA, we call Longest_String(“KSCOHIA”, Set7) where Set7 is simply Set6 but with IA removed. That is the first step of four in the loop. Within this loop, you keep track of the longest string using the number of characters and compare it with the longest string that the function assumed.
Why This Works
There will come a time when you run out of strings and can go no further. Perhaps the string ends with “NJ”. Maybe it was “OHIDCALAKSCTNJ”. The function would just return this string back to you since it can go no further. The computer will eventually hit this road block and come back out of its rabbit hole.
Are you curious what the longest string is that can be built? Try and build it, and tune in to The Riddler next week. Or, search #ThisWeeksRiddler on Twitter for JasonShaw1.
The Shaw Show 