Background

This task is inspired by Mark Nelson's DDJ Column "Wordplay" and one of the weekly puzzle challenges from Will Shortz on NPR Weekend Edition [1] and originally attributed to David Edelheit.

The challenge was to take the names of two U.S. States, mix them all together, then rearrange the letters to form the names of two different U.S. States (so that all four state names differ from one another).

What states are these?



The problem was reissued on the Unicon Discussion Web which includes several solutions with analysis. Several techniques may be helpful and you may wish to refer to Gödel numbering, equivalence relations, and equivalence classes. The basic merits of these were discussed in the Unicon Discussion Web.

A second challenge in the form of a set of fictitious new states was also presented.



Task

Write a program to solve the challenge using both the original list of states and the fictitious list.



Caveats

 case and spacing aren't significant - just letters (harmonize case)
 don't expect the names to be in any order - such as being sorted
 don't rely on names to be unique (eliminate duplicates - meaning if Iowa appears twice you can only use it once)


Comma separated list of state names used in the original puzzle:

    "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"

Comma separated list of additional fictitious state names to be added to the original (Includes a duplicate):

"New Kory",  "Wen Kory",  "York New",  "Kory New",  "New Kory"




Other tasks related to string operations:

Metrics
 Array length
 String length
 Copy a string
 Empty string  (assignment)
Counting
 Word frequency
 Letter frequency
 Jewels and stones
 I before E except after C
 Bioinformatics/base count
 Count occurrences of a substring
 Count how many vowels and consonants occur in a string
Remove/replace
 XXXX redacted
 Conjugate a Latin verb
 Remove vowels from a string
 String interpolation (included)
 Strip block comments
 Strip comments from a string
 Strip a set of characters from a string
 Strip whitespace from a string -- top and tail
 Strip control codes and extended characters from a string
Anagrams/Derangements/shuffling
 Word wheel
 ABC problem
 Sattolo cycle
 Knuth shuffle
 Ordered words
 Superpermutation minimisation
 Textonyms (using a phone text pad)
 Anagrams
 Anagrams/Deranged anagrams
 Permutations/Derangements
Find/Search/Determine
 ABC words
 Odd words
 Word ladder
 Semordnilap
 Word search
 Wordiff  (game)
 String matching
 Tea cup rim text
 Alternade words
 Changeable words
 State name puzzle
 String comparison
 Unique characters
 Unique characters in each string
 Extract file extension
 Levenshtein distance
 Palindrome detection
 Common list elements
 Longest common suffix
 Longest common prefix
 Compare a list of strings 
 Longest common substring
 Find common directory path
 Words from neighbour ones
 Change e letters to i in words
 Non-continuous subsequences
 Longest common subsequence
 Longest palindromic substrings
 Longest increasing subsequence
 Words containing "the" substring
 Sum of the digits of n is substring of n
 Determine if a string is numeric
 Determine if a string is collapsible
 Determine if a string is squeezable
 Determine if a string has all unique characters
 Determine if a string has all the same characters
 Longest substrings without repeating characters
 Find words which contains all the vowels
 Find words which contains most consonants
 Find words which contains more than 3 vowels
 Find words which first and last three letters are equals
 Find words which odd letters are consonants and even letters are vowels or vice_versa
Formatting
 Substring
 Rep-string
 Word wrap
 String case
 Align columns
 Literals/String
 Repeat a string
 Brace expansion
 Brace expansion using ranges
 Reverse a string
 Phrase reversals
 Comma quibbling
 Special characters
 String concatenation
 Substring/Top and tail
 Commatizing numbers
 Reverse words in a string
 Suffixation of decimal numbers
 Long literals, with continuations 
 Numerical and alphabetical suffixes
 Abbreviations, easy
 Abbreviations, simple
 Abbreviations, automatic
Song lyrics/poems/Mad Libs/phrases
 Mad Libs
 Magic 8-ball
 99 Bottles of Beer
 The Name Game (a song)
 The Old lady swallowed a fly
 The Twelve Days of Christmas
Tokenize
 Text between
 Tokenize a string
 Word break problem
 Tokenize a string with escaping
 Split a character string based on change of character
Sequences
 Show ASCII table
 De Bruijn sequences
 Self-referential sequences
 Generate lower case ASCII alphabet




/*REXX program  (state name puzzle)  rearranges two state's names ──► two new states.   */
!='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'
parse arg xtra;    !=! ',' xtra                     /*add optional  (fictitious)  names.*/
@abcU= 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';     !=space(!) /*!: the state list, no extra blanks*/
deads=0;    dups=0;    L.=0;     !orig=!;      @@.= /*initialize some REXX variables.   */
z=0                                                 /* [↑]  elide  dend─end (DE) states.*/
    do de=0  for 2;              !=!orig            /*use original state list for each. */
    @.=
        do states=0  by 0  until !==''              /*parse until the cows come home.   */
        parse var !  x  ','  !;       x=space(x)    /*remove all blanks from state name.*/
        if @.x\==''  then do                        /*was state was already specified?  */
                          if de  then iterate       /*don't tell error if doing 2nd pass*/
                          dups=dups + 1             /*bump the duplicate counter.       */
                          say 'ignoring the 2nd naming of the state: '    x;      iterate
                          end
        @.x=x                                       /*indicate this state name exists.  */
        y=space(x,0);    upper y;    yLen=length(y) /*get upper name with no spaces; Len*/
        if de  then do                              /*Is the firstt pass?  Then process.*/
                         do j=1  for yLen           /*see if it's a dead─end state name.*/
                         _=substr(y, j, 1)          /* _:  is some state name character.*/
                         if L._ \== 1  then iterate /*Count ¬ 1?  Then state name is OK.*/
                         say 'removing dead─end state  [which has the letter '   _"]: "  x
                         deads=deads + 1            /*bump number of dead─ends states.  */
                         iterate states             /*go and process another state name.*/
                         end   /*j*/
                    z=z+1                           /*bump counter of the state names.  */
                    #.z=y;  ##.z=x                  /*assign state name;  also original.*/
                    end
               else do k=1  for yLen                /*inventorize letters of state name.*/
                    _=substr(y,k,1);   L._=L._ + 1  /*count each letter in state name.  */
                    end   /*k*/
        end   /*states*/                            /*the index STATES isn't incremented*/
    end       /*de*/
call list                                           /*list state names in order given.  */
                   say z     'state name's(z)                "are useable."
if dups \==0  then say dups  'duplicate of a state's(dups)   'ignored.'
if deads\==0  then say deads 'dead─end state's(deads)        'deleted.'
sols=0                                              /*number of solutions found (so far)*/
say                                                 /*[↑]  look for mix and match states*/
     do j=1  for z     /* ◄──────────────────────────────────────────────────────────┐  */
       do k=j+1  to z                               /* ◄─── state K,  state J  ►─────┘  */
       if #.j<<#.k  then JK=#.j || #.k              /*is the state in the proper order? */
                    else JK=#.k || #.j              /*No,  then use the new state name. */
         do m=1  for z; if m==j | m==k then iterate /*no state  overlaps  are allowed.  */
         if verify(#.m, jk) \== 0      then iterate /*is this state name even possible? */
         nJK=elider(JK, #.m)                        /*a new JK, after eliding #.m chars.*/
           do n=m+1  to z; if n==j | n==k then iterate      /*no overlaps are allowed.  */
           if verify(#.n, nJK) \== 0      then iterate      /*is it possible?           */
           if elider(nJK, #.n) \== ''     then iterate      /*any leftovers letters?    */
           if #.m<<#.n  then MN=#.m || #.n                  /*is it in the proper order?*/
                        else MN=#.n || #.m                  /*we found a new state name.*/
           if @@.JK.MN\=='' | @@.MN.JK\==""  then iterate   /*was it done before?       */
           say 'found: '      ##.j','     ##.k       "  ───►  "        ##.m','      ##.n
           @@.JK.MN=1                            /*indicate this solution as being found*/
           sols=sols+1                           /*bump the number of solutions found.  */
           end   /*n*/
         end     /*m*/
       end       /*k*/
     end         /*j*/
say                                              /*show a blank line for easier reading.*/
if sols==0  then sols= 'No'                      /*use mucher gooder (sic) Englishings. */
say sols  'solution's(sols)    "found."          /*display the number of solutions found*/
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
elider: parse arg hay,pins                       /*remove letters (pins) from haystack. */
                            do e=1  for length(pins);    p=pos( substr( pins, e, 1),  hay)
                            if p==0  then iterate   ;    hay=overlay(' ', hay, p)
                            end   /*e*/          /* [↑]  remove a letter from haystack. */
        return space(hay, 0)                     /*remove blanks from the haystack.     */
/*──────────────────────────────────────────────────────────────────────────────────────*/
list:   say;   do i=1  for z;   say right(i, 9)   ##.i;   end;            say;      return
s:      if arg(1)==1  then return arg(3);    return word(arg(2) 's', 1)    /*pluralizer.*/