• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 2504
  • Last Modified:

coding puzzles

1)       N O S I E R
    +    A S T R A L
        ----------------
          7 2 5 6 1 3
In the addition above ,the sum represents a word.

each letter represents a single digit and no letter represents 0.
what is the word represnted by 7 2 5 6 1 3?

2) Each alphabet stands for one digit in the following multiplication.

      T H I S
      x     I S
    ---------
    X F X X
    X X U X
------------
X X N X X
------------

What is the maximum value T can take?

3)replace each letter by a digit.
each letter muse be represnted by the same digit and no beginning leeter of a word can be 0.

     O N E
     O N E
     O N E
     O N E
    --------
     T E N



PLEASE EXPLAIN THE SOLUTIONS IN DETAIL SO THAT I M ABLE 2 SOLVE SUCH VARIETY OF PROBLEMS.

0
shilpi84
Asked:
shilpi84
  • 8
  • 5
  • 2
  • +1
3 Solutions
 
ozoCommented:
#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;
}
0
 
shilpi84Author Commented:
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.
0
 
ozoCommented:
/*
 * 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;
}
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
ozoCommented:
    O N E
     O N E
     O N E
     O N E
    --------
     T E N

if E=0 then N=0, assuming N != E, E != 0
if E=1 then N=4, 41*4 = 164, 6!=1 so E != 1
if E=2 then N=8, 82*4 = 328, O=0, T=3 or O=1, T=7
if E=3 then N=2, 23*4 = 92, 9!=3 so E != 3
if E=4 then N=6, 64*4 = 256, 5!=4 so E != 4
if E=5 then N=0, 05*4 = 20, 2!=5 so E != 5
if E=6 then N=4, 46*4 = 184, 8!=6 so E != 6
if E=7 then N=8, 87*4 = 348, 4!=7 so E != 7
if E=8 then N=2, 28*4 = 112, 1!=8 so E != 8
if E=9 then N=6, 69*4 = 276, 7!=9 so E != 9
so the only solutuons are O=0 N=8 E=2 T=3 and O=1 N=8 E=2, T=7
Assuming O != 0, O=1 N=8 E=2 T=7
0
 
shilpi84Author Commented:
thanks ozo .please help me with the others 2.
0
 
mlmccCommented:
2) Each alphabet stands for one digit in the following multiplication.

      T H I S
      x     I S
    ---------
    X F X X
    X X U X
------------
X X N X X


I and S are not 0 - the appropriate line would be 0 in the intermediate multiplication
I and S are not 1 since the intermediate multiplication has a different digit (F and U)
Since I x THIS has 4 digits, I x T <=9
Since S x This has 4 digits, S x T <= 9
This only works if I,S,T

Only values that work are
    1 x any number thus T can be 1
    2 x 3 and 2 x 4  Thus T can be 2 since I and S must be different.

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

So T must be 1

mlmcc

   
         
0
 
ozoCommented:
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?
0
 
Harisha M GCommented:
Hi, from http://perplexus.info/show.php?pid=726&op=sol

First, since there are no zeroes and all digits are distinct, O + S cannot be 2. Thus, O + S is either 11 or 12, but there is a carry digit in either case. So, N + A = 6.

Similarly, E + A cannot be 1; either E + A = 10 or E + A = 11.

Suppose E + A = 11. Then, R + L = 3 (with no carry digit), so R and L are 1 and 2 in some order. Also, I + R = 5 (there is a carried 1 into that column, and I cannot be big enough to make the column total 15). Additionally, if E + A = 11, and N + A = 6, then N + 5 = E. So, N cannot be 5 or 6 (that would make E 10 or 11). Also, N is not 1 or 2 (R and L are). If N = 3, then A = 3 (N + A = 6), and if N = 4, A = 2, but again either L or R is 2. Therefore, the assumption that E + A = 11 must be false.

So, E + A = 10, and there is a carry digit from the ones column, so R + L = 13.

Since N + A = 6 and E + A = 10, N + 4 = E. So, N cannot be 6 (E would be 10). If N = 3, then A = 3, which is not possible; N (or A) cannot be 3). If N = 1, then A = 5, but if N = 1, E = 5, which is also not possible.
So, there are three valid possibilities so far for N, A, and E:
N = 2, A = 4, E = 6;
N = 4, A = 2, E = 8; or
N = 5, A = 1, E = 9.

Since R + L = 13, R and L must be (in some order) 4 and 9, 5 and 8, or 6 and 7. However, each of the possibilities for N, A, E includes a 4 or a 9, so R and L must be 5 and 8 or 6 and 7.

Therefore, the smallest value R can take is 5, but since there is a carry digit into the I + R = 6 column, and I cannot be zero, I + R must equal 15 (not 5). R cannot be 5 (I would have to be 10).

Since R + I = 15 and R + L = 13, L + 2 = I.
Therefore, there are three sets of possible values for R, L, and I:
R = 6, L = 7, I = 9;
R = 7, L = 6, I = 8; or
R = 8, L = 5, I = 7.

Comparing the sets of values for N, A, E with the possibilities for R, L, I, we can pair them up.
If E = 6, R or L cannot be six, so the first set for N, A, E is only possible with the third group of R, L, I.
Similarly, if E = 8, neither I nor R can be 8, so the second N, A, E is only possible with the first R, L, I.
Finally, if N = 5, L cannot be 5, and if E = 9, I is not 9, so the third N, A, E matches the second R, L, I.

There are three possibilities, namely:
N = 2, A = 4, E = 6, R = 8, L = 5, I = 7;
N = 4, A = 2, E = 8, R = 6, L = 7. I = 9; or
N = 5, A = 1, E = 9, R = 7, L = 6, I = 8.

There are three variables left to look at (S, T, O), and two possibilities for the sums of the remaining columns. Either S + T = 4, O + S = 12, and T + 8 = O, or S + T = 14, O + S = 11, and O + 3 = T.

If, in the first case, T + 8 = O, the only possible values are T = 1 and O = 9, with S = 3.
We need to look at the above three cases for the other six letters to see if there is one in which those values have not yet been assigned, and we find that the first set fits.
So, one possible set of values is:
N = 2, A = 4, E = 6, R = 8, L = 5, I = 7, T = 1, O = 9, S = 3.
Given these values, 725613 becomes INLETS, which is indeed a word.

Just to be thorough, check the second case above, wherein S + T = 14, O + S = 11, and O + 3 = T. The greatest O can be is 6, but since 6 is already represented in each of the above possibilities for the other six letters, O can't be six. If O is 5, T is 8, but all of the choices above have a letter for 5 or 8 already as well. Similarly, 4 and 7, 3 and 6, or 2 and 5 are not possible either. If O = 1 and T = 4, S would have to be 10 (to make O + S = 11); so we see that there are no remaining possibilities for the value of O.

Thus, the unique solution is as follows:
T = 1
N = 2
S = 3
A = 4
L = 5
E = 6
I = 7
R = 8
O = 9
and the word in question is INLETS.



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

mlmcc
0
 
Harisha M GCommented:
Answer is T can be at the most, 4 but I don't know how :)
0
 
ozoCommented:
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
0
 
Harisha M GCommented:
Am I missing something ? What does X mean ? Shouldn't that be same digit ?
0
 
ozoCommented:
I interpreted it as X can be anything.
There is no solution all X are the same digit.
0
 
Harisha M GCommented:
OK :)
0
 
Harisha M GCommented:
  4312
   x  12
________
   8624
 4312
________
 51744

Can also be a solution then ?
0
 
ozoCommented:
I thought U had to be different from I, but if we make an exception for X, then maybe there are other exceptions.
0
 
ozoCommented:
100096 seems to be a mistake in my list
0

Featured Post

What Security Threats Are We Predicting for 2018?

Cryptocurrency, IoT botnets, MFA, and more! Hackers are already planning their next big attacks for 2018. Learn what you might face, and how to defend against it with our 2018 security predictions.

  • 8
  • 5
  • 2
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now