# Cryptarithmetic Problem

Page 1 of 1

## 9 Replies - 14328 Views - Last Post: 10 January 2013 - 10:29 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=306651&amp;s=7ed1d5cf771925f168663adbdf479aac&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 ZacCarlson

Reputation: -7
• Posts: 146
• Joined: 08-October 12

# Cryptarithmetic Problem

Posted 10 January 2013 - 09:49 PM

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.

Is This A Good Question/Topic? 0

## Replies To: Cryptarithmetic Problem

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12267
• Posts: 45,362
• Joined: 27-December 08

## Re: Cryptarithmetic Problem

Posted 10 January 2013 - 09:57 PM

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.

### #3 raghav.naganathan

• Perfectly Squared ;)

Reputation: 410
• Posts: 1,449
• Joined: 14-September 12

## Re: Cryptarithmetic Problem

Posted 10 January 2013 - 09:58 PM

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

### #4 ZacCarlson

Reputation: -7
• Posts: 146
• Joined: 08-October 12

## Re: Cryptarithmetic Problem

Posted 10 January 2013 - 10:02 PM

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.

### #5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12267
• Posts: 45,362
• Joined: 27-December 08

## Re: Cryptarithmetic Problem

Posted 10 January 2013 - 10:05 PM

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?

### #6 ZacCarlson

Reputation: -7
• Posts: 146
• Joined: 08-October 12

## Re: Cryptarithmetic Problem

Posted 10 January 2013 - 10:06 PM

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.

### #7 ZacCarlson

Reputation: -7
• Posts: 146
• Joined: 08-October 12

## Re: Cryptarithmetic Problem

Posted 10 January 2013 - 10:15 PM

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.

### #8 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12267
• Posts: 45,362
• Joined: 27-December 08

## Re: Cryptarithmetic Problem

Posted 10 January 2013 - 10:19 PM

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.

### #9 ZacCarlson

Reputation: -7
• Posts: 146
• Joined: 08-October 12

## Re: Cryptarithmetic Problem

Posted 10 January 2013 - 10:28 PM

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

### #10 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12267
• Posts: 45,362
• Joined: 27-December 08

## Re: Cryptarithmetic Problem

Posted 10 January 2013 - 10:29 PM

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