[ZacCarlson]

I'm given the assignment following this sentence, and I'm pretty sure I did it right however when I run the program I get nothing. You'll see my code as well:

In cryptarithmetic puzzles, mathematical equations are written using letters.
Each letter can be a digit from 0 to 9, but no two letters can be the same.
Customarily, distinct letters stand for
different digits
Here is a sample problem:


SEND + MORE = MONEY

A solution to the puzzle is S = 9, R = 8, O = 0, M = 1, Y = 2, E = 5, N = 6, D
= 7
S E N D
M O R E
+
------------
M O N E Y

That is,

9 5 6 7
1 0 8 5
+
------------
1 0 6 5 2






Write a program that finds solutions to the following cryptarithmetic puzzle:


TOO + TOO + TOO + TOO = GOOD

T O O
T O O
T O O
+
-----------
G O O D

#include<iostream>

using namespace std;

int main()
{
        int t, o, g, d;
        for (t = 0; t <= 9; t++){
                for (o = 0; o <= 9; o++)
                        for (g = 0; g <= 9; g++)
                                for (d = 0; d <= 9; d++){
                                        if ((t != o) && (t != g) && (t != d) && (o != g) && (o != d) && (g != d)){
                                                int too = t * 100 + o * 10 + o, good = g * 1000 + o * 100 + o * 10 + d;
                                                if (4 * good == too){
                                                        cout << "t = " << t << "o = " << o << "g = " << g << "d = "
                                                        << d << endl;
                                                        cout << "TOO = " << too << endl;
                                                        cout << "GOOD = " << good << endl;
                                                }
                                        }
                                }
        }
return 0;
}

Hey, I fixed it, I had the good and the too swapped at the end. It works now, so you can delete this post.

[macosxnerd101]

If you're using four nested loops for such a simple problem, you're doing too much brute forcing and not enough of being clever. Look at the problem:
3O = D (mod 10)
3O + r = O (mod 10)
3T + x = O (mod 10)

Then the carry over from that last column = G.

Here, the mod 10 indicates the remainder when divided by 10. So in order to carry from the first column, O has to be at least 4. Already you don't have to iterate from 0-3, so that saves you four iterations on your second loop, so 400 total iterations. That's a big savings.

Do a little bit of math like this upfront and it will help you narrow down a lot.

[raghav.naganathan]

Well, I tried out your code with the good and the too swapped...it still didn't show any output...are you sure it works?

Edit: Well, I'm sorry...it does...I had a typo

regards,
Raghav

This post has been edited by raghav.naganathan: 10 January 2013 - 11:38 PM

[ZacCarlson]

I don't understand so if you can, explain it more or show me an example. If not, I don't mind because this is our first assignment and he'll be lenient on it. But I don't know how to do it other than what I did and the way you told me confuses me.

[macosxnerd101]

It comes down to math. The letters are variables. We know that O + O + O has D as the last digit. From the second column, O + O + O has an O as the last digit. If O < 4, then they would produce the same last digit. Plug values in and try it for yourself. So O >= 4, meaning that the value of O + O + O >= 12, so a 1 will carry into the next column.

Does this make more sense?

[ZacCarlson]

raghav.naganathan, on 10 January 2013 - 09:58 PM, said:

Well, I tried out your code with the good and the too swapped...it still didn't show any output...are you sure it works?

regards,
Raghav

Yes, positive.

[ZacCarlson]

macosxnerd101, on 10 January 2013 - 10:05 PM, said:

It comes down to math. The letters are variables. We know that O + O + O has D as the last digit. From the second column, O + O + O has an O as the last digit. If O < 4, then they would produce the same last digit. Plug values in and try it for yourself. So O >= 4, meaning that the value of O + O + O >= 12, so a 1 will carry into the next column.

Does this make more sense?

I did the quote as to not confuse the response with the one I made above it. Anyways, it does make sense as I read it but I still don't know how to fix it.

[macosxnerd101]

Work it out by hand. See how the values on the second column correspond to those of the first. For the third column, you know the sum > 9, as the carry value = G. It's easier when you have an idea of what to expect how to implement a more efficient solution.

Anyways, that's the best advice I have without violating the spirit of the assignment.

[ZacCarlson]

Yes, I understand and I appreciate all your help. I'll maybe look at it more tomorrow. Thanks for your assistance.

[macosxnerd101]

If you do this right, you won't need loops for G or D. That will increase efficiency significantly.