/* - - - - - - - - - - - - - - - - - - - - - *\
*                                             *
|        Lost Alphametics Easy Recovery       |
|                                             |
|  syntax : $laer term(1) ... term(n) sum     |
|  example : to solve SEND + MORE = MONEY :   |
|            $laer send more money            |
|                                             |
*                                             *
\* - - - - - - - - - - - - - - - - - - - - - */

// License : GPL

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

// occurence
struct occ        
{
	unsigned char lett;
	short val;
	long coeff;
};

long pow(int x, short n);
void comb (short n, short p, short *p_arr, short lg, short *p_place, occ *lc, int *p_cpt, int argc, char *argv[]);

int main(int argc, char *argv[])
{

	// 1st step : setting each letter "weight"

	if (argc < 4){
		cout << "laer - Lost Alphametics Easy Recovery v0.3\n";
		cout << "http://submoon.freeshell.org/en/laer      \n";
		cout << "syntax : $laer term(1) ... term(n) sum    \n";
		cout << "example : to solve SEND + MORE = MONEY:   \n";
		cout << "          $laer send more money           \n";
		return 0;
	}
  
	cout << "Initializing data...\n";
	
	short place[256];
	for (int i=0; i<256; i++) place[i]=-1;
	short ndc = 0;		// number of different chars
	occ lc[10];			// char list
	for (int i=0; i<10; i++) lc[i].coeff=0;
	short pos = 0;		// 1 if term, -1 if sum

	for (short arg=1; arg<argc; arg++){
		pos = ((arg == argc-1) ? -1 : 1);
		for (short i=0; argv[arg][i]; i++){
			if (place [argv[arg][i]]!=-1)
				lc[place[argv[arg][i]]].coeff += pos*pow(10,strlen(argv[arg])-1-i);
	  		else{
				place[argv[arg][i]]= ndc;
				lc[ndc].lett = argv[arg][i];
				lc[ndc].val = 0;
				lc[ndc].coeff = pos*pow(10,strlen(argv[arg])-1-i);
				ndc++;
				if (ndc>10)
				{
					cout << "Error : too many different characters.\n\n";
					return 0;
				}
			}
		} 
	}


  // 2nd step : brute-force scanning
  
  cout << "Looking for solutions...\n\n";
  int cpt = 0;
  short arr[10];

  comb (10, ndc, arr, ndc, place, lc, &cpt, argc, argv);

 
  cout << "Total : " << cpt << " solution" << (cpt>1?"s":"") << ".\n\n\a";

  return 0;

      
}

// power function
long pow(int x, short n)
{
  long res = 1;
  for (int cx=0; cx<n; cx++)
  res *= x;
  return res;
}

// comb. of p elements of [|0..n-1|], adapted from alg. (thx to Ian Parberry)
void comb (short n, short p, short *p_arr, short lg, short *p_place, occ *lc, int *p_cpt, int argc, char *argv[])
{
  
  if (p == 0)
   
  do 
  {

    long long sum = 0;
    for (short chf=0; chf<lg; chf++)
    {
      lc[chf].val = p_arr[chf];
      sum += lc[chf].val*lc[chf].coeff;
    }
    
    if (sum == 0)
    {
      bool ok = true;
      for (short cy=1; cy<argc;cy++)
      {
        if (lc[p_place[argv[cy][0]]].val == 0)
        ok = false;
      }
      if (ok)
      // 3rd step : displaying results
      {
        for (short i=1; i<argc-1; i++)
        {
          for (short j=strlen(argv[i]); j<strlen(argv[argc-1]); j++)
          cout << ' ';            
          for (short j=0; j<strlen(argv[i]); j++)
          cout << lc[p_place[argv[i][j]]].val;
          cout << '\n';
        }
        for (short j=0; j<strlen(argv[argc-1]); j++)
        cout << '-';
        cout << '\n';
        for (short j=0; j<strlen(argv[argc-1]); j++)
        cout << lc[p_place[argv[argc-1][j]]].val;
        cout << "\n\n";
        (*p_cpt)++;
      }
    }

  } while (std::next_permutation(p_arr,p_arr+lg));

  else
  for (register short i=p; i<=n; i++)
  {
    p_arr[p-1]=i-1;
    comb(i-1, p-1, p_arr, lg, p_place, lc, p_cpt, argc, argv);
  }

}