1. ## Cryptoarithmetic solver

I've been working on this project for a couple days now and i can't figure out how to make the program exhaust(brute force) through all the possibilities. The aim of the project is to read 3 words whose have up to 10 unique letters and find out what each letter equals. So far i am able to read words and store them and check for all the letters that dont repeat, i can also assign numbers but am not able to exhaust all paussible permutations i can only assign each letter a number once.
I am using send+more=money as base so my output is:
unique letters=sendmory
and the values assigned are:
send
1234
more
5672
money
56328
Any help or ideas to get me going would be greatly appreciated.
Code:
```#include <stdio.h>
#include <ctype.h>
#include <math.h>
#define N 10
long int assignv1(char uletter[], int nletter, int value[], char word1[], int nword1);
long int assignv2(char uletter[], int nletter, int value[], char word2[], int nword2);
long int assignv3(char uletter[], int nletter, int value[], char word3[], int nword3);
int main(void)
{
char word1[N], word2[N], word3[N],uletter[N];
int nword1, nword2, nword3,nletter,nuletter, value[N]; //counter of letters in words
int i,j=0, k, l,flag;d
long int value1=0,value2=0,value3=0;

printf("Please input the first in capital letters\n");
for(i=0;i<N;i++)
{
word1[i]=getchar();
if(word1[i]=='\n')
break;
}
nword1=i;

printf("Please input the first in capital letters\n");
for(i=0;i<N;i++)
{
word2[i]=getchar();
if(word2[i]=='\n')
break;
}
nword2=i;

printf("Please input the first in capital letters\n");
for(i=0;i<N;i++)
{
word3[i]=getchar();
if(word3[i]=='\n')
break;
}
nword3=i;
nletter=nword1+nword2+nword3;

/*_______________________________________________________________________*/

//count unique letters
uletter[0]=word1[0];
nuletter=1;

for(i=1;i<nword1;i++)
{
flag=0;
for(j=0;j<nuletter;j++)
{
if(word1[i]==uletter[j])
flag=1;
}
if(flag==0)
{
uletter[nuletter]=word1[i];
nuletter++;
}
}
for(i=0;i<nword2;i++)
{
flag=0;
for(j=0;j<nuletter;j++)
{
if(word2[i]==uletter[j])
flag=1;
}
if(flag==0)
{
uletter[nuletter]=word2[i];
nuletter++;
}
}

for(i=0;i<nword3;i++)
{
flag=0;
for(j=0;j<nuletter;j++)
{
if(word3[i]==uletter[j])
flag=1;
}
if(flag==0)
{
uletter[nuletter]=word3[i];
nuletter++;
}
}
printf("number of letters=%i\n",nletter);
printf("number of unique letters=%i\n",nuletter);
for(i=0;i<nuletter;i++)
printf("%c\n",uletter[i]);
/*_______________________________________________________________________*/
j=0;
for(i=0;i<N;i++)
{
j++;
value[i]=j;
}
value[9]=0;

for(k=0;k<N;k++)
{
i++;
j++;
value1=assignv1(uletter, nletter, value, word1, nword1);
value2=assignv2(uletter, nletter, value, word2, nword2);
value3=assignv2(uletter, nletter, value, word3, nword3);
if (value1+value2==value3)
{
printf("%li\n",value1);
printf("%li\n",value2);
printf("%li\n",value3);
}
}

return 0;
}

long int assignv1(char uletter[], int nletter, int value[], char word1[], int nword1)
{
int i,j;
long int value1=0;

for(i=0;i<nword1;i++)
{
for(j=0;j<nletter;j++)
{
if(word1[i]==uletter[j])              //Inputing value to unique letter
{
value1+=value[j]*pow(10, (nword1-i-1));
}
}

}
return value1;
}
long int assignv2(char uletter[], int nletter, int value[], char word2[], int nword2)
{
int i,j;
long int value2=0;
for(i=0;i<nword2;i++)
{
for(j=0;j<nletter;j++)
{
if(word2[i]==uletter[j])              //Inputing value to unique letter
{
value2+=value[j]*pow(10, (nword2-i-1));
}
}

}
return value2;
}
long int assignv3(char uletter[], int nletter, int value[], char word3[], int nword3)
{
int i,j;
long int value3=0;

for(i=0;i<nword3;i++)
{
for(j=0;j<nletter;j++)
{
if(word3[i]==uletter[j])              //Inputing value to unique letter
{
value3+=value[j]*pow(10, (nword3-i-1));
}
}

}
return value3;
}```

2. What are these "plausible permutations"? What exactly are you trying to "brute force"?

In the example you gave, the unique letters are S E N D M O R Y, which map to 1-8 respectively. What is the cipher text your program gets? What other info are you given to decrypt it? Also, could you explain what the assignv1, assignv2 and assignv3 functions are supposed to be doing? It's not clear from the name, the logic seems arbitrary, and there are no comments to help out either.

Perhaps you could explain a little more, or post the actual problem description (homework assignment?), or a link to it. Also, maybe you could provide some sample runs, showing exactly what should be on the screen, input and output.

One more thing, you always ask for the "first" word. You should change the prompts to say "second" and "third".

3. The assignment is to:
1. Read in the three words and count how many unique letters are in the three words. The inputs are
limited to capital letters. If the number is more than 10, ask the user to type in different words.
2. Using the brute force method, assign digits 0-9 to the unique letters, and determine the multi-digit
number that each word represents. Verify if the first two multi-digit numbers added together is equal
to the third.
3. Sort out the multiple solutions and determine the number of unique solutions. This can be done during
the solution finding process. If unique solution exists, output it. If no solution or multiple solution,
output the number of solutions.

The assign functions are to assign a value to each letter.
I'm trying to make a program that solves verbal arithmetic like "SEND+MORE=MONEY". We had to make a program that solves any just that problem like the one below, but this one is supposed to be more broad being able to take any input.
Code:
```#include <stdio.h>

int main(void)
{
long S, E, N, D, M, O, R, Y;
long SEND, MORE, MONEY;
int count=0;

for(S=0;S <= 9; S++)
for(E=0;E <= 9; E++)
for(N=0;N <= 9; N++)
for(D=0;D <= 9; D++)
for(M=0;M <= 9; M++)
for(O=0;O <= 9; O++)
for(R=0;R <= 9; R++)
for(Y=0;Y <= 9; Y++)
if(M != 0)
if(S != E && S != N && S != D && S != M && S != O && S != R && S != Y)
if(E != N && E != D && E != M && E != O && E != R && E != Y)
if(N != D && N != M && N != O && N != R && N != Y)
if(D != M && D != O && D != R && D != Y)
if(M != O && M != R && M != Y)
if(O != R && O!= Y)
if(R != Y)hj
{
SEND=1000*S+100*E+10*N+1*D;
MORE=1000*M+100*O+10*R+1*E;
MONEY=10000*M+1000*O+100*N+10*E+1*Y;
if(SEND+MORE == MONEY)
{
printf("SEND is:  %li %1li %1li %1li   %8li \n", S,E,N,D, SEND);
printf("MORE is:  %li %1li %1li %1li   %8li \n", M,O,R,E, MORE);
printf("MONEY is: %1li %1li %1li %1li %1li  %7li \n", M,O,N,E,Y, MONEY);
count++;
}
}
printf("count is: %i \n", count);

return 0;
}```

4. This is verbal arithmetic.

Given D unique digits and L unique letters, D >= L, there are D! / (D - N)! unique mappings from digits to letters -- alternatives an exhaustive brute force search must try. My preferred approach to construct each mapping is very simple: number the mappings (using nonnegative integers) from 0 to D! / (D - N)! - 1, inclusive.

(If you think about it, it should be pretty obvious. The first letter can map to any digit, the second letter to any digit but the one the first one mapped to, and so on; thus there are D × (D - 1) × (D - 2) × ... × (D - N + 1) possible mappings. The terms do not go down to 1 if there are more digits than letters, because there are 1 × 2 × ... × (D - N) irrelevant combinations of those excess digits. This is basic combinatorics.)

If integer m describes such a mapping, then the mapping from letters to digits, digit[0] specifying the digit the first letter maps to, up to digit[L-1], which specifies the digit the last letter maps to, can be computed as follows:
Code:
```digit[0..L-1] = the original digits, i.e. { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

for (i = 0; i < L; i++) {

/* Extract next digit, [0, D-i) from m. */
d = m % (D - i);
m = m / (D - i);

/* Swap digit[i] and digit[d+i]: */
temp = digit[i];
digit[i] = digit[d+i];
digit[d+i] = temp;
}```
The above is a basic permutation loop. Moreover, m will be zero after the loop if the original value was within the upper limit. (If it is nonzero after the loop, the original value was >= D! / (D - N)! , so you don't actually need to compute the factorial, or even worry about it, really. Just have an endless output search loop, which is aborted if (when) m is nonzero after the above code snippet.)

In practice, you'd wrap the above in a loop, say for (permutation = 0UL; ; permutation++), and initialize m = permutation and the values in the value array for each iteration. (It is a very common bug to forget to re-initialize the value array, and wonder why it won't find the solution in some cases.) If m is nonzero after the above snippet, you break out of the outer for loop. Otherwise you compute the value corresponding to each letter sequence, and check if the arithmetic matches.

Note that you must also ignore those cases where the first letter of any word maps to zero, as the Wikipedia page linked above mentions. If you don't, for decimal digits mapped to SEND + MORE = MONEY you'll also get 24 other solutions:
Code:
```S=2 E=8 N=1 D=7 M=0 O=3 R=6 Y=5: 2817 + 0368 = 03185
S=2 E=8 N=1 D=9 M=0 O=3 R=6 Y=7: 2819 + 0368 = 03187
S=7 E=5 N=3 D=9 M=0 O=8 R=1 Y=4: 7539 + 0815 = 08354
S=8 E=3 N=2 D=4 M=0 O=9 R=1 Y=7: 8324 + 0913 = 09237
S=5 E=8 N=4 D=9 M=0 O=6 R=3 Y=7: 5849 + 0638 = 06487
S=8 E=5 N=4 D=2 M=0 O=9 R=1 Y=7: 8542 + 0915 = 09457
S=3 E=8 N=2 D=9 M=0 O=4 R=5 Y=7: 3829 + 0458 = 04287
S=5 E=7 N=3 D=1 M=0 O=6 R=4 Y=8: 5731 + 0647 = 06378
S=7 E=6 N=4 D=9 M=0 O=8 R=1 Y=5: 7649 + 0816 = 08465
S=6 E=8 N=5 D=3 M=0 O=7 R=2 Y=1: 6853 + 0728 = 07581
S=7 E=5 N=3 D=1 M=0 O=8 R=2 Y=6: 7531 + 0825 = 08356
S=8 E=4 N=3 D=2 M=0 O=9 R=1 Y=6: 8432 + 0914 = 09346
S=5 E=7 N=3 D=2 M=0 O=6 R=4 Y=9: 5732 + 0647 = 06379
S=6 E=5 N=2 D=4 M=0 O=7 R=3 Y=9: 6524 + 0735 = 07259
S=6 E=4 N=1 D=9 M=0 O=7 R=2 Y=3: 6419 + 0724 = 07143
S=3 E=7 N=1 D=2 M=0 O=4 R=6 Y=9: 3712 + 0467 = 04179
S=7 E=3 N=1 D=6 M=0 O=8 R=2 Y=9: 7316 + 0823 = 08139
S=3 E=8 N=2 D=1 M=0 O=4 R=6 Y=9: 3821 + 0468 = 04289
S=6 E=4 N=1 D=5 M=0 O=7 R=3 Y=9: 6415 + 0734 = 07149
S=7 E=6 N=4 D=3 M=0 O=8 R=2 Y=9: 7643 + 0826 = 08469
S=7 E=5 N=3 D=4 M=0 O=8 R=2 Y=9: 7534 + 0825 = 08359
S=7 E=4 N=2 D=9 M=0 O=8 R=1 Y=3: 7429 + 0814 = 08243
S=6 E=8 N=5 D=1 M=0 O=7 R=3 Y=9: 6851 + 0738 = 07589
S=3 E=7 N=1 D=9 M=0 O=4 R=5 Y=6: 3719 + 0457 = 04176```
The correct (well-known) solution is of course
Code:
`S=9 E=5 N=6 D=7 M=1 O=0 R=8 Y=2: 9567 + 1085 = 10652`
The solution I've described here is obviously not the only way to solve such problems, but I've found this very robust. In particular, it is much easier to implement than any recursive techniques you might try. It is also not in any way limited to this particular problem, either. See Wikipedia articles on permutation and combinatorics for further background and useful links.

A generic test implementation (not just decimal digits, but any set of digits in any radix; full overflow checking, basically otherwise the answer to your exercise problem) took me about 167 lines of code, plus whitespace and comments, of which about a third was the actual search and result output, and the rest was parsing the input strings and command-line parameters (radix and the digits -- my program took all inputs from the command line, instead of prompting for them). It took a few minutes of deep thought to get the combinatorics straight and to simplify the letter-to-digit mappings, but after I started coding it, didn't encounter any really tricky spots. It was pretty straightforward.

Hope this helps. Questions?

5. EDIT: Woah! I read this a while back, but had to run out for a while. I thought I refreshed this page and still didn't see a reply, so I wrote this. Nominal has a much better answer. I didn't even know verbal arithmetic was "a thing" (or I did, but forgot).

Thanks, that's much clearer. This looks a tough, but interesting. It will take you a while. It would take me a while too. It's also hard for me to judge what advice or techniques to suggest because I don't know your still level. For example, have you learned linked lists? Do you know what dynamic programming is?

One quick thing to get out of the way. If I understand correctly, you should only need one "assignv" function, since the operations are the same, only the array you compute changes. You could probably do this much more easily with a temp array, a single for loop and the strtol or strtoll function, instead of the two loops and calculations with pow that you currently have.

As for permuting the numbers, Google for permutation algorithms and do a bit of reading. Try implementing one that works with only a fixed size string, something short like 3 characters, that you can easily verify by looking. Once you get that down, work on expanding it to work with strings of any length from 2-10. That is, work towards one algorithm, that will correctly permute an array of any length up to your max. There is a "simple" way that comes to mind, but it's really ugly. It involves passing in the length of the string to permute, and having a bunch of nested for loops (and possibly if statements if you don't work the condition into the for loop). Figure out your permutation algo in a separate little program, so you don't have to worry about letter-number mappings and whether the words "sum up" correctly. Then merge it into your current program.

Don't even worry about removing duplicate solutions until you're sure your program finds all the valid solutions correctly.

6. That's interesting that you're being asked to solve it by brute force, because this is one of the classic brain teasers that is solvable with just a bit of thinking.
For example, to start with, the first thing to realise is that M must be 1 because the result is one digit longer than both operands.
As much as you need to do it by brute force, I'd advise you to have a go at it by hand first as well. It's a fun problem, and there are various other variants of it.
Answer here if you give up: Math Forum - Ask Dr. Math

7. I'm still a beginner at programming, i know the basic loop structures while, for, and do loops. I know a bit about arrays, vectors, and very very little about file pointers. Thank you all for all the great advice i will read up and get back to you whenever i finish. Any other suggestions would be wonderful too though. Also i have worked the problem out already, and know the answer, but the program is supposed to solve any verbal arithmetic that is input. Other examples would be base+ball=games, cracks+hacks=error. and others

8. Originally Posted by anduril462
If I understand correctly, you should only need one "assignv" function, since the operations are the same, only the array you compute changes.
Fully agreed, and a very good point, too.

Certain type of laziness -- "smart lazyness" ? -- is good in a programmer. If there is an operation that is done more than once (or even if it is just done once but is logically a separate operation), it is almost always a good idea to write it as a separate function.

There is no need to duplicate the exact same code, however. Your functions only differ by the names of the parameters and local variables, so they are actually identical. The parameters and local variables are only visible inside the function (more generally, visible within that scope), so there is absolutely no need to create a copy of a function with the only differences being in parameter or local variable names.

If I may, I'd recommend you revisit functions, function parameters, and local variables and variable scope, if you don't see why you only need one version of the assignv function.

Originally Posted by anduril462
You could probably do this much more easily with a temp array, a single for loop and the strtol or strtoll function, instead of the two loops and calculations with pow that you currently have.
To be honest, I found that way -- using the string itself when computing the corresponding value -- too fragile for me.

I mean, I think it would be likely that any code I'd write along those lines would contain bugs; I'd rather have something more straightforward, to lessen the likelihood of bugs in my code.

I found it simpler to first convert the words into integer arrays, with first unique letter replaced with zero, second unique letter replaced with one, and so on, also saving the mapping from integers back to letters for display purposes:
Code:
```/* Mapping from letters A [0] to Z [25] to index: */
int letter_index[26];

/* Mapping from index to letter -- really, [10] should be enough. */
int letter_char[26];```
In the case of SEND+MORE=MONEY, the unique letters are S E N D M O R Y, i.e.
Code:
```letter_index['S' - 'A'] = 0; letter_char[0] = 'S';
letter_index['E' - 'A'] = 1; letter_char[1] = 'E';
letter_index['N' - 'A'] = 2; letter_char[2] = 'N';
letter_index['D' - 'A'] = 3; letter_char[3] = 'D';
letter_index['M' - 'A'] = 4; letter_char[4] = 'M';
letter_index['O' - 'A'] = 5; letter_char[5] = 'O';
letter_index['R' - 'A'] = 6; letter_char[6] = 'R';
letter_index['Y' - 'A'] = 7; letter_char[7] = 'Y';
letters = 8; /* L in my previous post */```
and the arrays matching the words are
Code:
```first_array[4]  = { 0, 1, 2, 3 };    /* SEND */
second_array[4] = { 4, 5, 6, 1 };    /* MORE */
third_array[5]  = { 4, 5, 2, 1, 7 }; /* MONEY */```
(If you initialize the letter_index array to -1, you can easily detect whether a letter is new or already defined. You can do it in a single pass over each string, too.)

The nice thing in this approach is that if you have constructed a digit array like I explained in my previous post, you can compute the value corresponding to that digit permutation trivially:
Code:
```array = an array like above (first_array, second_array, third_array)
length = length of the array (4 or 5 here)

value = 0
for (i = 0; i < length; i++)
value = 10 * value + digit[array[i]];```
The first digit specified by the array is the most significant, and ends up being multiplied by 10length-1 during the loop. The array entries specify the letter indexes, which are of course indexes to the digit array. In other words, i specifies which character (position) in the word we are examining, array[i] tells us the letter index, and digit[array[i]] the digit that that letter corresponds to using the current permutation.

If this permutation happens to be a solution, then
Code:
```for (i = 0; i < letters; i++)
printf("Letter %c = %d\n", letter_char[i], digit[i]);```
prints the mapping. (If I explained myself correctly, you probably knew this already; I just wanted to be explicit in case it was unclear thus far.)

Because the permutation I described in my earlier post, you will not see duplicate results. This technique inherently avoids duplicate solutions, by skipping those cases that would only permute the unused digits.

Aside from a few details like how to parse the parameters and convert the strings to the arrays described above, how to output the results, and overflow checks I used, these two posts actually describe all the code I wrote for my test program, I believe.

It takes quite a bit of thought to wrap your mind around the technique, but after you grok it, the code itself should be very straightforward.

I really don't want to show any actual C code, because this is a very useful technique to understand, and it would be too tempting to just use the working code without understanding the ideas behind it. But, I'm sure my explanation is quite poor. If you point out any spots in the logic you have difficulty understanding, just say so; I'd be happy to try to explain it in some other way.

However, this approach is not really compatible with your current code: you'd have to basically rethink your code, and just about rewrite it. It is more than a little frustrating, I agree, but I think the effort is worth it: I've solved quite a few combinatorial problems with this approach. And the other approach I've used for the other combinatorial problems, is actually a very close cousin. (I have posted an example of that one too on this forum recently.)

Now that I re-read this thread, I do have a small fear that there are too many new details in my approach for you to understand them all in the limited time you have before turning in your exercises. All I can say is that in my experience, this approach is worth the effort needed to understand it.

9. Originally Posted by Raśl Cipriano
Other examples would be base+ball=games, cracks+hacks=error. and others
Code:
```base  + ball = games: b=7 a=4 s=8 e=3 l=5 g=1 m=9:  7483 + 7455 = 14938
crack + hack = error: c=4 r=2 a=6 k=1 h=9 e=5 o=8: 42641 + 9641 = 52282```
but none for cracks+hacks=error or hacks+error=cracks.

roof + walls = house has four solutions,
Code:
```1. r=5 o=2 f=1 w=3 a=7 l=6 s=9 h=4 u=8 e=0: 5221 + 37669 = 42890
2. r=7 o=2 f=6 w=8 a=5 l=1 s=4 h=9 u=3 e=0: 7226 + 85114 = 92340
3. r=5 o=2 f=6 w=8 a=7 l=1 s=4 h=9 u=3 e=0: 5226 + 87114 = 92340
4. r=7 o=2 f=1 w=3 a=5 l=6 s=9 h=4 u=8 e=0: 7221 + 35669 = 42890```
and nominal + animal = errored has two solutions,
Code:
```n=2 o=8 m=1 i=9 a=6 l=5 e=3 r=4 d=0: 2819265 + 629165 = 3448430
n=4 o=7 m=6 i=3 a=2 l=9 e=5 r=0 d=8: 4763429 + 243629 = 5007058```