Recursive Programming Brainteaser

Substitue a number for each character so that when you add the first *word* to the second *word* you get the third *word* as the result.

...DONALD
.+GERALD
..-------
...ROBERT

there is only one answer (that I know of) out of a million possibilities. I solved it by brute force on the same day that my mathematician friend did, but forget the answer.

I have a few hints in case anyone wants them.

T = an even number
You can carry the one to the left
Each character is a different digit
Digits used are 0-9

(can't left justify leading spaces.)

answer is in format
111111+222222=333333
dddddd+ccccccc=ffffff

Have fun :D

Quote:

---

Originally posted by dglienna
T = an even number

---

That's quite obvious, since D + D = T (or D + D = 10 + T)


BTW, what's recursive about this? Are we supposed to find a recursive solution?

it appeared in a magazine article about recursive programming, but there was never any code posted. since QB didn't support it, I did it the old fashioned way of coming up with two tables, and using QB to do the calculation until it came up with the answer.

I'd like to see the code of a recursive solution. :D

now that it is supported, I'd have to think about how to accomplish it recursively...

Quote:

---

That's quite obvious, since D + D = T (or D + D = 10 + T)

---

wouldn't want to give away too many hints :D

I *do* have the correct answer, if anyone needs it.

Why does it have to be recursive?

it doesn't. the original article listed it as an example in recursion. I'm having trouble finding a way to solve it (again) recursively, that's why I posted it as recursive.

Probably a solution with which you could solve this in a recursive way is brute-force all combinations. Start with the lowest digit, then call the function again for the digits to the left :dunno:

I wouldn't need recursion to do that. In fact, that's exactly what I did to solve it years ago. I think that I used Paradox's PAL to write a script that processed two tables of all of the choices, and added the numbers together until it found one that resulted in the total. I belive that there were a couple that matched the criteria, but only one that had the right numbers.

Solving it by hand was tougher. Had a table of numbers for each letter, and just crossed out ones that didn't work. That is the same way my math-teacher buddy solved it.

I still haven't come up with an algorithm that would cycle thru it, but I think about it from time to time.

You could probably create a set of rules that will recursively call other functions (much like a recursive descent parser.) Other than that, I do not know a better recursive approach to this.

I'm thinking of trying each number, starting with the most frequently used one(s) and filling the rest into the other positions, and then checking each pair, and then either proceeding for the next pair, or eliminating it. Kind of have it figured out in my head. May start coding pretty soon.
I have the answer, so it is still just for fun.
I guess nobody else cares about it? :D

All the letters are equal to 0.
There, I solved it.

But actually:
Make a program which has a module-level array with 10 elements.
Make a function which takes an array index, and calls itself 10 times (with the next array's index) for the values 0 through 9 unless it's at the last index.
Check for the answer at each value.

Brute force recursion.

the answer requires the use of all of the digits 0-9 to be used in the equation. setting d=1 means t=2, and also that 1 will be used two other times. 1xxxx1 + xxxxx1 = xxxxx2, so that means that the other 14 letters can only be 0-8. if you pick l=3, then r=6 and it must be 6 in 2 other places, leaving 0,4,5,7,8,9 for the remaining letters, etc... 1xxx31 + xx6x31 = 6xxx62
still not seeing an algorithm :(

of course if l were 6, then r woud be 2 carrying the 1.
2 was already used, so it would fail.

Well you didn't say that to start with, so how was I to know? I'll see if I can whipe something up... the fact that the digits can't be the same can cut a lot of time.

i don't know whether to make each word out of numbers and fill in the rest, and then do the math until it doesn't work, and then change the numbers. Can't find a way to do it systematically.
might have to just loop numbers until they add up, and then check to see if the digits are of the right sequence. (this could be done recursively, i'd imagine) :D

maybe subtracting 1 from the answer, and adding one to one of the operands may work recursively, with calculations inbetween?

I've come up with a method, and it's running right now. Not sure how to stop it, so its running in debug mode and breaking when the numbers add up. So far about 30 times. Just checking to make sure that it will find the answer when all of the numbers are different.


example

113491+690491=811982

which is good for 3 more clicks (with beeps)

takes care of carrying the numbers, so I'll just wait until it comes up with the final answer, and then polish it...

just realized that i didn't update the textbox for the answers that I posted before, so they may just NOT add up, either.

These should:

118971+294971=413942
522985+197985=720970 (may be coming close???)


Yup. They do, so it should give the right answer.

This will be one for Code It Better

[i should have come up with a way to check that each digit is unique in respect to its position/letter]

it sure is cooking my laptop. it should shut down if it gets too hot!

it better :eek2:

just about gave it away. still running, though...

things cool down when the fan opening isn't sitting over my leg


:rolleyes:

It came up with the right answer!!!

Unfortunately, it just keeps on running. Without a way to check for duplicates, there are too many answers.

Posting in CODE IT BETTER!

Quote:

---

Each character is a different digit

---

Quote:

---

118971+294971=413942
522985+197985=720970 (may be coming close???)

---

Are you saying that this is an answer to your problem? :confused:

Quote:

---

Originally posted by Darkwraith
Are you saying that this is an answer to your problem? :confused:

---

I think he brute forced every possible NUMBER combination then checked if they matched the letters. :rolleyes:

I'm going to try a genetic algorythm

271532 + 406532 = 678069
678064 = 678069

Pretty close, I need to redesign my fitness algorythm so it distributes right... the problem is I don't know what to do it on. Since we're picking digits being off by a 100 is the same as being off by 10, but 110 is twice as bad as 100 or 10.... :eek:

that was not the answer. I posted some code in code it better, and had no response. i used the brute force method, and it took a loooooong time to run.

Quote:

---

522985+197985=720970

---

O an N cannot both be 2 if it is also equal to E

D 5 G 1 R 7
O 2 E 9 O 2
N 2 R 7 B 0
A 9 E 9
L 8 R 7
D 5 T 0

Quote:

---

Originally posted by dglienna
that was not the answer. I posted some code in code it better, and had no response. i used the brute force method, and it took a loooooong time to run.

---

I said it was close. I also said it was hard to find because we're guessing digits... not exaclty suited for my fitness algorythm.

kind of ironic, but i was stuck at the same solution for a while.
you'll kick yourself when you discover the problem/solution which will then resolve the answer. good luck! :D

I haven't even tried to solve it, I was just using it to test my GA. lol

I'd brute force it right now but I'm at work.

I am trying to bring the order of the algorithm down. Right now, at most, my algorithm should (what a wonderful word, should) only go through 10! possibilities.

Hey, its better than 10^10 possibilities....

I'm trying the brute force (with a minor check for T to be even) but I've hit a brick wall. For some reason I cannot seem to get a chunk of code written that given a length of string ("0123456789") can come out with all the possible combinations.

I was planning to shove these values (on each of the lines) into an array which matches the letter to one of these numbers. Then I have a function/sub to convert each Name into its numerical equivalent, then just add one to the other and compare against Roberts total.

Only... As I said, not getting the possible combinations. I know its a crap method, but it I get that combination bit sorted I can wait for 3 days whilst it processes ;)


Vince

I don't understand the method. Please post some of your code.

I created a generic solver in Java. I am processing the 10! numbers until I hit the first possible combination.

It is recursive.

526485 + 197485 = 723970

BTW, this took less than an hour to process and it was the 1,922,457th possibility.

[edit] Just as a note, this is the ONLY solution.

Quote:

---

Originally posted by Darkwraith
526485 + 197485 = 723970

BTW, this took less than an hour to process and it was the 1,922,457th possibility.

---

What did you do to minimize the possiblities?
We know there were 3-4 letters that had to be even, and we know that if a digit already exists, there's no reason to check 10 times for it. (that's probably where you got your 10!, the digit)

But did you optimize for the evens?

I did it the smart brute force way. I only had 10! orders to go through, so it was not really necessary to optmize.

If you want to optimize, though, you have a few rules which you can use:

(A + A + 0) -> B % 2 = 0
(A + A + 1) -> B % 2 = 1
(A + B + 0 = B) -> A = 0

The third parameter represents the carry. As you can see, these rules are not very helpful and are very specialized. Therefore, I dropped the whole rule thing and went brute force through it.

Now if you wanted to make the brute force approach less feasible, then let us consider the equation:

IKBN JQGA + GBDQ HPLF = KANN BIDF

The new rule for this is:

digits are from 0 to F.

Now my approach will not work well because I now have (at most) 16! different possibilities.

We could even go up to 36! or 62! if you really want to discourage brute force methods.

that looks wicked. what would a=4 b=2 c=3 d=1
represented as abcd abcd ? 4231 4231 or what?

congratulations on the answer. Still looking for code to reduce 10^10. Not sure how, though. Maybe when you answer this, I could see how I would solve it to find out.

wanna post your code? put it in Code it Better after my code.
10! is definitely better.


I think that MartinLiss is going to start a new forum for puzzles. I wrote about this thread.

Quote:

---

that looks wicked. what would a=4 b=2 c=3 d=1
represented as abcd abcd ? 4231 4231 or what?

---

:confused:

Quote:

---

wanna post your code? put it in Code it Better after my code.

---

http://www.vbforums.com/showthread.p...hreadid=301588

I cleaned it up a bit so that it looked presentable. :)

I thought that Netscape would run Java, but it opens in Notepad.
Go Figure. Will try IE, but I doubt it. Same thing.
Any suggestions?

Are those words 8 characters with a space in-between? I thought that they may be something different.

Quote:

---

I thought that Netscape would run Java, but it opens in Notepad.
Go Figure. Will try IE, but I doubt it. Same thing.
Any suggestions?

---

A few things about Java: (1) Java is not a scripting langague. You have to to have a compiler. (2) My project is not an applet. When you compile it, you will have to type in a command like:

Code:

---

java VBF001 DONAND GERALD ROBERT

---

to actually execute it.

Quote:

---

Are those words 8 characters with a space in-between?

---

Its a habit that I picked up from my work in 80x86 assembler. I break up blocks of digits into 4's so that it is easier to read. I really should have split them up in groups of 2, but I did 4 instead. What you are seeing are 3 eight digit hex numbers.

hmmm. that does complicate things a bit. will have to think about that for a while. more when I get back.

I think as Darkwraith said that the only solution is:

526485 + 197485 = 723970

I do not know about the algorithm, but doing it manually took only 10 minutes.

Some hints I used were that:
1. E can be either 0 (no carry over) or 9 (carry over 1) - As adding E and O gave back O.
2. T is even.
3. D and G cannot be 0 as they are the most promonent digit.
4. R cannot be less than 3 as it is D + G which are two different non-zero numbers.

Case 1: E = 0
1. Implies A = 5.
2. There is no carry over from 2nd column implies L < 5.
3. L > 1 as R > 2 and if R = 3, then L = 1, but then D and G can be assigned only 1 and 2 to get 3, which cannot happen. So L can be only 2, 3 or 4.

After a few calculations you can figure out that with E = 0, you cannot find a solution.

Case 2: E = 9
1. Implies A = 4.
2. There will be carryovers from 2nd, 4th and 5th columns.
3. Thus L > 4.
4. As R > 3, so L > 6.
5. So L is either 7 or 8.

After a few calculations you can figure out the numbers as the possibilities will keep on reducing.

I just made a 10 X 10 table with the digits 0 - 9 as rows and different letters as columns. Just kept on crossing the values which a letter cannot take. It is damn easy to do it.

Any comments are welcome. If needed, I can explain any of the above statements or write full explanation.

Quote:

---

Case 2: E = 9
1. Implies A = 4.
2. There will be carryovers from 2nd, 4th and 5th columns.
3. Thus L > 4.
4. As R > 3, so L > 6.
5. So L is either 7 or 8.

---

I see the 2nd and the 4th, but how did you deduce the 5th is a result of a carry-over?


Good going, if you didn't start with the answer and reverse-engineer it (or hear of Steve Ciarcia's Ask Byte) :D

As far as the table goes,
I think this that is the way it was explained by the high-school math-teaching friend that solved it before.

OMG - I had no idea that you just had to GOOGLE the problem.

http://www.google.com/search?sourcei...ERALD%3DROBERT

No, mine is a little bit more sophisticated than that. Its not engineered to one problem. Its engineered to all problems that involve at most 10 symbols where each symbol is distinct.

I was hoping on finding a rule-based way of doing this, but like I said, I did not have enough rules to make it worth while.

[edit] BTW, I did put a note on my post that contained the answer that said that there was only one solution.

I could probably compile it and put the bytecode up here if you want.

I don't need an .exe, but I was considering how I could use the java code. I thought that it didn't get compiled, and that Netscape would run it, but I found out otherwise.

dglienna, this is the explanation you wanted.

In case where I assumes, E = 9 (or wharever is that symbol), there will be a carry from 5th column as well because we know that there was a carry over from 4th column and thus 9 + 1 will itself become 10. So 1 has to carry.


Also it was reverse engineering, but that is what you can do without using the brute force or computational power of computer. I think atleast it is a better way than checking far all possible permutations and finding. This way no one can improve their programming skills just writing some loops and if conditions.

The program using recursion is not very easy but also not something like a challenge.

I also would be really happy to see a general algorithm for any 10 symbol sequence. I think any such algorithm will have to use either the table or the recursion.

In the end I would say that though this was like a high school math teacher, but this is the best and the most methodical way doing it by just pen and paper. You can see the results. I took some 10 minutes. I wonder how many of great programmers among you took less than that in writing code and executing.

Quote:

---

In the end I would say that though this was like a high school math teacher, but this is the best and the most methodical way doing it by just pen and paper. You can see the results. I took some 10 minutes. I wonder how many of great programmers among you took less than that in writing code and executing.

---

I solved for any equation meeting the aforementioned criteria that you could throw at me. You only solved for one. ;)

OIC 654321. I was thinking 123456.
still infinitely easier once you have the answer.

SEND + MORE = MONEY is the only other one that I know.

solved it by hand in about 5 minutes. didn't use a 2, though.
it wasn't anywhere as hard as the first one.

http://www.geocities.com/Athens/Agor...uzzlemenu.html

thanks for the link. i missed that one.

How about trying one that involves multiplication? :)

creating one, or solving one?

Well, if you create one, would that mean that you have to solve it first?

it would not be fair to post a challenge if you don't have the answer already.

[Challenge rule #739]

:D

Then how would you know if your problem had a solution?

you have to define a set of numbers to match each letter, and then use only those letters to use numbers that make an equation, or vice-versa. My puzzle used all of the numbers from 0 to 9. There was a link to a site that contained a lot of puzzles. Take a look there.

:D