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

class Combinations {
private:
   bool done;
   int* a;
   int  a_size;
   int* maxs;
public:
   Combinations( int num_things, int num_at_a_time ) {
      done = false;
      a = new int[num_at_a_time];
      a_size = num_at_a_time;
      for (int i=0; i < num_at_a_time; ++i)
         a[i] = i;
      maxs = new int[num_at_a_time];
      for (int i=num_at_a_time-1, j=0; i > -1; --i, ++j)
         maxs[i] = num_things - j;
   }
   bool next( int array[] ) {
      for (int k=0; k < a_size; ++k)
         array[k] = a[k];
      return increment();
   }
   bool increment() {
      if (done)
         return false;
      int end = a_size - 1;
      while (++a[end] == maxs[end]) {
         end--;
         if (end == -1)
            return done = true;
      }
      for (int i=end+1; i < a_size; ++i)
         a[i] = a[i-1] + 1;
      return true;
   }
};

// guess mapping, letter-position mapping, all words, number of words
bool is_guess_valid( int digits[], map<char,int>& letters, char* words[], int argc ) {
   for (int i=1; i < argc; ++i)
      if (digits[letters[words[i][0]]] == 0)
         return false;
   return true;
}

// word, guess mapping, letter-position mapping
int get_value_for_word( char* word, int digits[], map<char,int>& letters ) {
   int result = 0;
   for (int i=strlen(word)-1, mult=1;
        i > -1;
        i -= 1, mult *= 10)
      result += digits[letters[word[i]]] * mult;
   return result;
}

// word, guess mapping, letter-position mapping, max word size
void print_word( char* word, int digits[], map<char,int>& letters, int max_word_size ) {
   string blanks( max_word_size - strlen(word), ' ' );
   cout << blanks << word << "    " << blanks;
   for (int i=0; i < strlen(word); ++i)
     cout << digits[letters[word[i]]];
   cout << '\n';
}

int main( int argc, char* argv[] ) {
   map<char,int> letters;
   int count = 0, total, last_word = argc-1, max_word_size = 0;
   // Find all the letters, and put them in a sorted list
   for (int i=1; i < argc; ++i) {
      for (int j=0; j < strlen(argv[i]); ++j)
         letters[argv[i][j]] = 0;
      if (strlen(argv[i]) > max_word_size)
         max_word_size = strlen(argv[i]);
   }
   // Create an array of digits that is the same size as the array of letters
   int* digits = new int[ letters.size() ];

   // Report the array of letters, and assign each its ordinal position
   map<char,int>::iterator it = letters.begin();
   for (int i=0; it != letters.end(); ++it, ++i) {
      letters[it->first] = i;
      cout << it->first << ' ';
   }
   cout << '\n';

   // Iterate through all combinations, and all permutations of each combination
   Combinations combos( 10, letters.size() );
   while (combos.next( digits ))
      do {
         count++;
         if ( ! is_guess_valid( digits, letters, argv, argc ))
            continue;

         // Total all but the last word
         total = 0;
         for (int i=1; i < last_word; ++i)
            total += get_value_for_word( argv[i], digits, letters );

         // If the value of the last word equals the total of the other words ...
         if (total == get_value_for_word( argv[last_word], digits, letters )) {
            // Report the array of digits that solves the puzzle
            for (int i=0; i < letters.size(); ++i)
               cout << digits[i] << ' ';
            cout << "\n\n";
            // Report each word and the number it represents
            for (int i=1; i < argc-1; ++i)
               print_word( argv[i], digits, letters, max_word_size );
            string line( max_word_size, '-' );
            cout << line << "    " << line << '\n';
            print_word( argv[argc-1], digits, letters, max_word_size );
         }
      } while (next_permutation( digits, digits+letters.size() ));
   cout << "\ncount is " << count << '\n';
}

/**********
% alphametics i did too
d i o t 
1 9 0 2 

  i      9
did    191
---    ---
too    200

count is 5040

% alphametics hes the best
b e h s t 
1 2 4 6 8 

 hes     426
 the     842
----    ----
best    1268

count is 30240

% alphametics no no too late
a e l n o t 
0 2 1 7 4 9 

  no      74
  no      74
 too     944
----    ----
late    1092

count is 151200

% alphametics base ball games
a b e g l m s 
4 7 3 1 5 9 8 

 base     7483
 ball     7455
-----    -----
games    14938

count is 604800

% alphametics usa ussr peace
a c e p r s u 
2 7 0 1 8 3 9 

  usa      932
 ussr     9338
-----    -----
peace    10270

count is 604800

% alphametics send more money
d e m n o r s y 
7 5 1 6 0 8 9 2 

 send     9567
 more     1085
-----    -----
money    10652

count is 1814400

% alphametics three three two two one eleven
e h l n o r t v w 
1 4 7 9 3 6 8 2 0 

 three     84611
 three     84611
   two       803
   two       803
   one       391
------    ------
eleven    171219

count is 3628800

% alphametics double double toil trouble
b d e i l o r t u 
0 7 4 3 6 9 5 1 8 

 double     798064
 double     798064
   toil       1936
-------    -------
trouble    1598064

count is 3628800

% alphametics world trade center
a c d e l n o r t w 
0 1 4 2 8 9 3 6 7 5 

 world     53684
 trade     76042
------    ------
center    129726

count is 3628800

% alphametics this isa great time waster
a e g h i m r s t w 
0 4 9 6 2 3 7 8 5 1 

  this      5628
   isa       280
 great     97405
  time      5234
------    ------
waster    108547

count is 3628800



o Read the arguments from the command line
o Identify, count, and sort the unique letters
o Generate all combinations and permutations
o Filter out all guesses that have a '0' on the left of the number
o Compute the value for each argument
o Compare the sum of the first N-1 arguments with the N-th (last) argument
o Print each answer found

b i l    3
9 1 0 

  i      1
 bb     99
ill    100

count is 720

d i o t    4
1 9 0 2 

  i      9
did    191
too    200

count is 5040

a e r s t    5
6 2 1 4 5 

 tar     561
star    4561
tree    5122

count is 30240

b e h s t    5
1 2 4 6 8 

 hes     426
 the     842
best    1268

count is 30240

a d h n o s    6
7 4 5 2 3 1 

 and     724
 had     574
  no      23
sons    1321

count is 151200

a e l n o t    6
0 2 1 7 4 9 

  no      74
  no      74
 too     944
late    1092

count is 151200

a b e g l m s    7
4 7 3 1 5 9 8 

 base     7483
 ball     7455
games    14938

count is 604800

a c e p r s u    7
2 7 0 1 8 3 9 

  usa      932
 ussr     9338
peace    10270

count is 604800

d e m n o r s y    8
7 5 1 6 0 8 9 2 

 send     9567
 more     1085
money    10652

count is 1,814,400

e h l n o r t v w    9
1 4 7 9 3 6 8 2 0 

 three     84611
 three     84611
   two       803
   two       803
   one       391
eleven    171219

count is 3,628,800

b d e i l o r t u    9
0 7 4 3 6 9 5 1 8 

 double     798064
 double     798064
   toil       1936
trouble    1598064

count is 3628800

a c d e l n o r t w    10
0 1 4 2 8 9 3 6 7 5 

 world     53684
 trade     76042
center    129726

count is 3628800

www.tkcs-collins.com/truman/alphamet/alphamet.shtml
here she comes
there are risks
pacific pacific pacific atlantic
god sodom bible
one nine twenty fifty eighty
dos dos tres siete



int main( int argc, char* argv[] ) {
   int digits[5];
   Combinations combos( 5, 4 );
   int count = 0;
   while (combos.next( digits )) {
      do {
         cout << digits[0] << digits[1] << digits[2] << digits[3] << ' ';
         count++;
      } while (next_permutation( digits, digits+4 ));
      cout << '\n';
   }
   cout << "count is " << count << '\n';
}

012 021 102 120 201 210 
013 031 103 130 301 310 
014 041 104 140 401 410 
023 032 203 230 302 320 
024 042 204 240 402 420 
034 043 304 340 403 430 
123 132 213 231 312 321 
124 142 214 241 412 421 
134 143 314 341 413 431 
234 243 324 342 423 432 
count is 60    10 * 6

0123 0132 0213 0231 0312 0321 1023 1032 1203 1230 1302 1320
 2013 2031 2103 2130 2301 2310 3012 3021 3102 3120 3201 3210 
0124 0142 0214 0241 0412 0421 1024 1042 1204 1240 1402 1420
 2014 2041 2104 2140 2401 2410 4012 4021 4102 4120 4201 4210 
0134 0143 0314 0341 0413 0431 1034 1043 1304 1340 1403 1430
 3014 3041 3104 3140 3401 3410 4013 4031 4103 4130 4301 4310 
0234 0243 0324 0342 0423 0432 2034 2043 2304 2340 2403 2430
 3024 3042 3204 3240 3402 3420 4023 4032 4203 4230 4302 4320 
1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431
 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321 
count is 120    24 * 5

**********/