Recursive Programming Brainteaser

[dglienna]

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

[riis]

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?

[dglienna]

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.

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

[dglienna]

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

wouldn't want to give away too many hints

[dglienna]

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

[Darkwraith]

Why does it have to be recursive?

[dglienna]

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.

[riis]

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:

[dglienna]

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.

[Darkwraith]

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.

[dglienna]

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?

[alkatran]

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.

[dglienna]

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.

[alkatran]

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.

[dglienna]

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)

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

[dglienna]

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...

[dglienna]

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

[dglienna]

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

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

[dglienna]

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!

[Darkwraith]

Each character is a different digit

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

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

[alkatran]

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

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

I'm going to try a genetic algorythm

[alkatran]

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....

[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.

[dglienna]

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

[alkatran]

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.

[dglienna]

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!

[alkatran]

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.

[Darkwraith]

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....

[Ecniv]

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

[dglienna]

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

[Darkwraith]

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

It is recursive.

[Darkwraith]

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.

[alkatran]

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?

[Darkwraith]

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.

[Darkwraith]

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.

[dglienna]

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.

[Darkwraith]

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

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.

[dglienna]

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.

[Darkwraith]

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:

java VBF001 DONAND GERALD ROBERT

to actually execute it.

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.

[dglienna]

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