// Take the names of two U.S. States, mix them all together, then rearrange the
// letters to form the names of two other U.S. States.  What are the states?
// -- contributed by David Edelheit
// -- weekly puzzle challenge from Will Shortz on NPR Weekend Edition
// www.ddj.com/dept/architect/198701685   Architecture & Design newsletter, 2 Apr 2007

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using std::cout;
using std::multiset;
using std::vector;
using std::sort;
using std::string;
using std::multimap;
using std::map;

string 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", "newhampshire", "newjersey",
   "newmexico", "newyork", "northcarolina", "northdakota", "ohio",
   "oklahoma", "oregon", "pennsylvania", "rhodeisland", "southcarolina",
   "southdakota", "tennessee", "texas", "utah", "vermont",
   "virginia", "washington", "westvirginia", "wisconsin", "wyoming" };

int main() {
   int array[] = { 1, 2, 3, 4, 5, 6 };
   for (int i=0; i < 4; ++i)
      for (int j=i+1; j < 5; ++j)
         for (int k=j+1; k < 6; ++k)
            cout << array[i] << array[j] << array[k] << ' ';
   cout << '\n';
}

// 123 124 125 126 134 135 136 145 146 156
// 234 235 236 245 246 256 345 346 356 456
// 6 * 5 * 4  /  3 * 2 * 1 = 20


int main() {
   multimap<string,string>  mapping;
   string                   pairing, sorted;

   int count = 0;
   for (int i=0; i < 49; ++i)
      for (int j=i+1; j < 50; ++j)
         count++;
   cout << "total combinations is " << count << '\n';
}

// total combinations is 1225
// 50 * 49  /  2 * 1


int main() {
   string  pairing, sorted;
   for (int i=0; i < 3; ++i)
      for (int j=i+1; j < 4; ++j) {
         sorted = pairing = states[i] + states[j];
         sort( sorted.begin(), sorted.end() );
         cout << sorted << '\t' << pairing << '\n';
}     }

// aaaaaaabkllms    alabamaalaska
// aaaaaabilmnorz   alabamaarizona
// aaaaaaabklmnrss  alabamaarkansas
// aaaaaiklnorsz    alaskaarizona
// aaaaaakklnrsss   alaskaarkansas
// aaaaaiknnorrssz  arizonaarkansas


int main() {
   vector<string>  pairing(1225), sorted(1225);

   // Load all two-state combinations in an array
   for (int i=0, m=0; i < 49; ++i)
      for (int j=i+1; j < 50; ++j, ++m) {
         sorted[m] = pairing[m] = states[i] + states[j];
         // Sort each combination and store it in a different array
         sort( sorted[m].begin(), sorted[m].end() );
      }
   // Take each entry in the sorted array
   for (int i=0; i < sorted.size()-1; ++i)
      // ... and compare it to every other entry in the sorted array
      for (int j=i+1; j < sorted.size(); ++j)
         if (sorted[i] == sorted[j])
            cout << pairing[i] << " ... " << pairing[j] << '\n';
}

// northcarolinasouthdakota ... northdakotasouthcarolina


int main() {
   multimap<string,string>  mapping;
   string                   pairing, sorted;

   // Load all sorted pairings into multimap
   for (int i=0; i < 49; ++i)
      for (int j=i+1; j < 50; ++j) {
         sorted = pairing = states[i] + states[j];
         sort( sorted.begin(), sorted.end() );
         // all insertions are maintained in alphabetical order
         mapping.insert( make_pair( sorted, pairing ) );
      }

   // Find adjacent pairings that are equal
   multimap<string,string>::iterator it1 = mapping.begin(),
                                     it2 = mapping.begin();
   for (++it2; it2 != mapping.end(); ++it1, ++it2)
      if (it1->first == it2->first)
         cout << it1->second << " ... " << it2->second << '\n';
}

// northcarolinasouthdakota ... northdakotasouthcarolina


int main() {
   map<string,string>  mapping;
   string              pairing, sorted;

   for (int i=0; i < 49; ++i)
      for (int j=i+1; j < 50; ++j) {
         sorted = pairing = states[i] + states[j];
         sort( sorted.begin(), sorted.end() );

         // If this sorted pairing has not already been loaded, then load it
         if (mapping[sorted].empty())
            mapping[sorted] = pairing;

         // Otherwise, report the match
         else
            cout << pairing << " ... " << mapping[sorted] << '\n';
      }
}

// northdakotasouthcarolina ... northcarolinasouthdakota




// .......... Mark Nelson solutions ..........

char* 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", "newhampshire", "newjersey",
   "newmexico", "newyork", "northcarolina", "northdakota", "ohio",
   "oklahoma", "oregon", "pennsylvania", "rhodeisland", "southcarolina",
   "southdakota", "tennessee", "texas", "utah", "vermont",
   "virginia", "washington", "westvirginia", "wisconsin", "wyoming", };

int main() {
   for (int i=0; i < 49; i++)
      for (int j=i+1; j < 50; j++) {
         multiset<char> label1;
         char *p = states[i];
         while (*p)
            label1.insert( *p++ );
         p = states[j];
         while (*p)
            label1.insert( *p++ );
         for (int m=0; m < 49; m++)
            if (m != i  &&  m != j)
               for (int n=m+1; n < 50; n++)
                  if (n != i  &&  n != j) {
                     multiset<char> label2;
                     char *p = states[m];
                     while (*p)
                        label2.insert( *p++ );
                     p = states[n];
                     while (*p)
                        label2.insert( *p++ );
                     if (label1 == label2)
                        cout << states[i] << ", " << states[j] << ", "
                             << states[m] << ", " << states[n] << '\n';
                  }
      }
}

// northcarolina, southdakota, northdakota, southcarolina
// northdakota, southcarolina, northcarolina, southdakota


int main() {
   multiset<char> letters[50][50];
   for (int i=0; i < 49; i++)
      for (int j=i+1; j < 50; j++) {
         char *p = states[i];
         while (*p)
            letters[i][j].insert( *p++ );
         p = states[j];
         while (*p)
            letters[i][j].insert( *p++ );
      }
   for (int i=0; i < 49; i++)
      for (int j=i+1; j < 50; j++)
         for (int m=0; m < 49; m++)
            if (m != i  &&  m != j)
               for (int n=m+1; n < 50; n++)
                  if (n != i  &&  n != j)
                     if (letters[i][j] == letters[m][n])
                        cout << states[i] << ", " << states[j] << ", "
                             << states[m] << ", " << states[n] << '\n';
}


int main() {
   vector<char> letters[50][50];
   for (int i=0; i < 49; i++)
      for (int j=i+1; j < 50; j++) {
         char *p = states[i];
         while (*p)
            letters[i][j].push_back( *p++ );
         p = states[j];
         while (*p)
            letters[i][j].push_back( *p++ );
         sort( letters[i][j].begin(), letters[i][j].end() );
      }
   for (int i=0; i < 49; i++)
      for (int j=i+1; j < 50; j++) {
         cout << i << ' ' << j << "    \r";
         for (int m=0; m < 49; m++) {
            if (m == i  ||  m == j)
               continue;
            for (int n=m+1; n < 50; n++) {
               if (n == i  ||  n == j)
                  continue;
               if (letters[i][j] == letters[m][n])
                  cout << '\n' << states[i] << ", " << states[j]
                       << ", "  << states[m] << ", " << states[n] << '\n';
}     }  }  }

// 32 40    
// northcarolina, southdakota, northdakota, southcarolina
// 33 39    
// northdakota, southcarolina, northcarolina, southdakota