#include <stdio.h>
#include <stdlib.h>

/*
 * Tom Magliery
 * email:  mag@ncsa.uiuc.edu
 *
 * Generates a C program which will solve a given cryptarithm (is that what
 * what they're called?).  Anyway, I mean puzzles like this:
 *
 *                                 s e n d
 *                               + m o r e
 *                               ---------
 *                               m o n e y
 *
 * where each letter stands for a different digit.  That particular
 * puzzle has 1 "interesting" solution (neither m nor s=0), and 24
 * "uninteresting" ones.

   (Should modify the program to discard solutions with leading zeroes!
    Cryptarithmetic puzzle rules forbid that kind of solution - G)

 *
 * The input is a character string of the form "send + more = money".
 * It may have any number of addends (including 1 or 0, in which case
 * the appropriate '+' and '=' are omitted).  There must be exactly one
 * space on either side of each '+' and '='.  Strange, unpredictable,
 * and most importantly, *incorrect*, behavior will probably result if
 * you don't follow these rules.
 *
 * The generated program runs with no arguments.  It tries every possible
 * combination of digits and prints all that work, including ones with
 * leading zeroes in the addends and/or sum.
 *
 * The generated program is printed to standard output.  Redirect it to
 * a file with a ".c" extension and compile it.  Both this program and
 * the generated program are ANSI C.  It (they) may require some hacking
 * to work with a non-ANSI compiler.
 *
 */

typedef struct {
                char symbols[11];
                int num_of_addends;
                char** addends;
                char* sum;
               } REC;


void ParseInput (char*, REC*);
void printHeader (REC*);
void printMain (REC*);
void printMatch (REC*);
void printPrint (REC*);
int index_of (char, char*);


main (int argc, char**argv)
{
   REC* pzl = (REC*) malloc (sizeof (REC));

   if (argc<2)
      fprintf (stderr, "No problem.  ;-)\n");
   else {
      ParseInput (argv[1], pzl);
      printHeader (pzl);
      printMain (pzl);
      printMatch (pzl);
      printPrint (pzl);
      }
}



void ParseInput (char* problem, REC* pzl)
{
   char** words;
   int i, index, length = strlen(problem), spaces=0;

   /* record the different symbols used in the problem */
   for (i=0; i<11; i++) pzl->symbols[i] = '\0';
   for (i=0; i<length; i++)
      if (problem[i] != ' ' && problem[i] != '+' && problem[i] != '=')
         if (index_of(problem[i], pzl->symbols) == -1) {
            if (strlen(pzl->symbols) == 10) {
               printf ("Error -- too many symbols in problem.\n");
               exit (37);
               }
            pzl->symbols[strlen(pzl->symbols)] = problem[i];
            }

   /* count the spaces */
   for (i=0; i<length; i++)
      if (problem[i]==' ') spaces++;

   /* there is one more word than the number of spaces */
   /* WARNING:  not robust -- assumes no two consecutive spaces */
   words = (char**) malloc ((spaces+1)*sizeof(char*));

   /* set pointers to individual words */
   words[0] = problem;
   index = 1;
   for (i=0; i<length; i++)
      if (problem[i] == ' ')
         words[index++] = &problem[i+1];

   /*  make words null-terminated */
   for (i=0; i<length; i++)
      if (problem[i] == ' ')
         problem[i] = '\0';

   /* # of addends is always half # of spaces */
   pzl->num_of_addends = spaces/2;

   /* construct the list of addends */
   pzl->addends = (char**) malloc (pzl->num_of_addends * sizeof(char*));
   for (i=0; i<pzl->num_of_addends; i++)
      pzl->addends[i] = words[2*i];

   /* sum is the last 'word' on the list */
   pzl->sum = words[spaces];
}



void printHeader (REC* pzl)
{
   int i;
   printf ("/*\n");
   printf (" * Automatically-generated program to solve the");
   printf (" following cryptarithm:\n");
   printf (" *      ");
   for (i=0; i<pzl->num_of_addends; i++) {
      printf ("%s", pzl->addends[i]);
      printf ("%s", i<pzl->num_of_addends-1 ? " + " : " = ");
      }
   printf ("%s\n", pzl->sum);
   printf (" */\n");
}



void printMain(REC* pzl)
{
   printf ("#include <stdio.h>\n");
   printf ("#include <stdlib.h>\n");
   printf ("#define M %d\n", strlen(pzl->symbols));
   printf ("int tuple[10];\n");
   printf ("int Used[10] = {0,0,0,0,0,0,0,0,0,0};\n");
   printf ("void perm(int*, int);\n");
   printf ("int match();\n");
   printf ("void print();\n");
   printf ("main () {\n");
   printf ("   perm (Used, M);\n");
   printf ("}\n");
   printf ("void perm (int Used[10], int Size) {\n");
   printf ("int i;\n");
   printf ("if (Size == 1) {\n");
   printf ("   for (i=0; i<10; i++)\n");
   printf ("      if (!Used[i]) {\n");
   printf ("         tuple[M-Size] = i;\n");
   printf ("         if (match()) print();\n");
   printf ("         }\n");
   printf ("   }\n");
   printf ("else {\n");
   printf ("   for (i=0; i<10; i++) {\n");
   printf ("      if (!Used[i]) {\n");
   printf ("         Used[i] = 1;\n");
   printf ("         tuple[M-Size] = i;\n");
   printf ("         perm (Used, Size-1);\n");
   printf ("         Used[i] = 0;\n");
   printf ("         }\n");
   printf ("      }\n");
   printf ("   }\n");
   printf ("}\n");
}



void printMatch(REC* pzl)
{
   int a, i, len=strlen(pzl->sum), multiplier=1;

   printf ("int match () {\n");
   printf ("return !(");
   for (i=0; i<len; i++) {
      if (i>0) printf ("         ");
      printf ("%10d*(", multiplier);
      for (a=0; a<pzl->num_of_addends; a++) {
         if (i<strlen(pzl->addends[a])) {
            printf ("tuple[");
            printf ("%d",
                    index_of (pzl->addends[a][strlen(pzl->addends[a])-i-1],
                              pzl->symbols));
            }
         else
            printf ("       ");
         if (a < pzl->num_of_addends-1)
            printf ("%s", i<strlen(pzl->addends[a]) ? "]+" : "  ");
         else
            printf ("%s", i<strlen(pzl->addends[a]) ? "]" : " ");
         }
      printf ("-tuple[");
      printf ("%d", index_of (pzl->sum[len-i-1], pzl->symbols));
      printf ("])");
      printf ("%s", i<len-1 ? "+\n" : ");\n");
      multiplier *= 10;
      }
   printf ("}\n");
}



void printPrint(REC* pzl)
{
   int i, j;
   char* current_addend;

   printf ("void print () {\n");

   printf ("printf (\"");
   current_addend = pzl->addends[0];
   for (i=0; i < pzl->num_of_addends; i++) {
      for (j=0; j<strlen(pzl->addends[i]); j++)
         printf ("%%d");
      printf ("%s", i<pzl->num_of_addends-1 ? " + " : " = ");
      }
   for (j=0; j<strlen(pzl->sum); j++)
      printf ("%%d");
   printf ("\\n\",\n        ");

   for (i=0; i<pzl->num_of_addends; i++) {
      for (j=0; j<strlen(pzl->addends[i]); j++)
         printf ("tuple[%d], ", index_of(pzl->addends[i][j], pzl->symbols));
      printf ("\n        ");
      }
   for (j=0; j<strlen(pzl->sum); j++) {
      printf ("tuple[%d]", index_of(pzl->sum[j], pzl->symbols));
      printf ("%s", j<strlen(pzl->sum)-1 ? ", " : ");\n");
      }

   printf ("return;\n}\n");
}



int index_of (char ch, char* str)
{
   int i, len = strlen(str);
   for (i=0; i<len; i++)
      if (str[i] == ch)
         return i;
   return -1;
}