coding puzzles

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

/*
 * Tom Magliery
 * National Center for Supercomputing Applications
 * 605 E. Springfield
 * Champaign, IL 61820
 * 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.
 *
 * 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;
}

ozo i do not neeed a program nor am i able 2 understand anything.i have a written test 4 a placeement company i m trying 2 figure out how 2 solve such puzzles.

/*
 * Automatically-generated program to solve the following cryptarithm:
 *      one + one + one + one = ten
 */
#include <stdio.h>
#include <stdlib.h>
#define M 4
int tuple[10];
int Used[10] = {0,0,0,0,0,0,0,0,0,0};
void perm(int*, int);
int match();
void print();
main () {
   perm (Used, M);
}
void perm (int Used[10], int Size) {
int i;
if (Size == 1) {
   for (i=0; i<10; i++)
      if (!Used[i]) {
         tuple[M-Size] = i;
         if (match()) print();
         }
   }
else {
   for (i=0; i<10; i++) {
      if (!Used[i]) {
         Used[i] = 1;
         tuple[M-Size] = i;
         perm (Used, Size-1);
         Used[i] = 0;
         }
      }
   }
}
int match () {
return !(         1*(tuple[2]+tuple[2]+tuple[2]+tuple[2]-tuple[1])+
                 10*(tuple[1]+tuple[1]+tuple[1]+tuple[1]-tuple[2])+
                100*(tuple[0]+tuple[0]+tuple[0]+tuple[0]-tuple[3]));
}
void print () {
printf ("%d%d%d + %d%d%d + %d%d%d + %d%d%d = %d%d%d\n",
        tuple[0], tuple[1], tuple[2],
        tuple[0], tuple[1], tuple[2],
        tuple[0], tuple[1], tuple[2],
        tuple[0], tuple[1], tuple[2],
        tuple[3], tuple[2], tuple[1]);
return;
}

thanks ozo .please help me with the others 2.

Try T = 2, S = 3, and I = 4
3 x H <= 20 thus H is 5 or 6 but 4 x H >= 20 and 4 x 2 = 8 + carry 2 or 10

Why cant H be 0 or 1?

Cause I was tired.  You are correct H can be 0 or 1 thus T could be 1 or 2

mlmcc

Answer is T can be at the most, 4 but I don't know how :)

The possibilities seem to be
 1047
 x 47
 ____
 7329
4188
_____
49209

 1054
 x 54
 ____
 4216
5270
_____
56916

 1057
 x 57
 ____
 7399
5285
_____
60249

 1058
 x 58
 ____
 8464
5290
_____
61364

 1065
 x 65
 ____
 5325
6390
_____
69225

 1075
 x 75
 ____
 5375
7525
_____
80625

 1087
 x 87
 ____
 7609
8696
_____
94569

 1253
 x 53
 ____
 3759
6265
_____
66409

 1326
 x 26
 ____
 7956
2652
_____
34476

 1346
 x 46
 ____
 8076
5384
_____
61916

 1365
 x 65
 ____
 6825
8190
_____
88725

 1465
 x 65
 ____
 7325
8790
_____
95225

 1542
 x 42
 ____
 3084
6168
_____
64764

 1564
 x 64
 ____
 6256
9384
_____
100096

 1645
 x 45
 ____
 8225
6580
_____
74025

 1753
 x 53
 ____
 5259
8765
_____
92909

 1843
 x 43
 ____
 5529
7372
_____
79249

 1852
 x 52
 ____
 3704
9260
_____
96304

 1935
 x 35
 ____
 9675
5805
_____
67725

 1942
 x 42
 ____
 3884
7768
_____
81564

 1943
 x 43
 ____
 5829
7772
_____
83549

 2043
 x 43
 ____
 6129
8172
_____
87849

Am I missing something ? What does X mean ? Shouldn't that be same digit ?

I interpreted it as X can be anything.
There is no solution all X are the same digit.

OK :)

  4312
   x  12
________
   8624
 4312
________
 51744

Can also be a solution then ?

I thought U had to be different from I, but if we make an exception for X, then maybe there are other exceptions.

100096 seems to be a mistake in my list