
#1
Nov3012, 01:05 AM

P: 12

1.Before I start it is important to say that I only have two months programming experience so my capabilities are limited. I have been working on a C# code to solve general case verbal arithmetic problems, but I ran into some trouble with one part of the algorithm. If you are not familiar with verbal arithmetic, here's some details: http://en.wikipedia.org/wiki/Verbal_arithmetic.
Part of the solution process (for me, anyway) involves using for loops to change the values in an array. I then use those values to calculate the value of each word. For example, I set up an array with the corresponding values M=1, O=0, R=8, E=5 and calculate (using another function) MORE=1085. I want to generate and test each value from 09 for each letter combined together (code 1B below gives a better idea of what I mean). Unfortunately, I'm not having any success using for loops. When I define the array by itself (see 1a. below for example) I have no trouble reading the values. When I use a for loop(1b below), however, the program fails to give any results besides 0+0=0. Anyway, any suggestions or pointers for how I could approach the code differently? Also, help with my lack of experience in mind would be appreciated. I'm not familiar with much more than loops, some basic pointers, operators, and functions.:




#2
Nov3012, 07:58 AM

Sci Advisor
P: 2,751

Hi jello*, I think I know what is the problem you're running into, but unfortunately your thread title doesn't describe it very well. So lets see if we can define the problem a little better first.
 You want to be able to solve word arithmetic problems by using an "exhaustive search" method of substituting/testing all possible combinations of digits.  For a given simple problem, like the "send+more=money" one linked, you can use eight nested "for" loops to solve it pretty easily.  When you try to generalize the above solution you find that much of the specific problem is in effect "hard coded" into those nested "for" loops. This is where you're stuck. Ok I'm kind of reading between the lines here, but does the above describe the problem you're coming up against? BTW. If this is your problem then yes, there are algorithms other than "hard coded" for loops to deal with this. 



#3
Nov3012, 11:21 AM

P: 12

Thank you for putting into words what I couldn't seem to. That is exactly my problem.




#4
Nov3012, 11:40 AM

Sci Advisor
P: 2,751

C#: Changing Values In an ArrayFor example, say we had 5 variables  A,B,C,D and E  that could each take on the value of any digit 0 through to 9. We can calculate that there are 10^5 = 100000 possible combinations, so we use a single loop with the index variable (say k) running from 0 through to 99999. Each possible value of the index variable corresponds to a particular set of values for A, B, C, D and E. For example k=12345 corresponds to A=1, B=2, C=3, D=4, E=5, and so on. Using integer divides and modulos we can construct A,B,C,D and E from k. While this is most easy to understand when the number of choices is ten (and you can "see" the values in the decimal digits), it is equally applicable to any base with appropriate integer division/modulo operations. 



#5
Nov3012, 12:11 PM

P: 181

I've written a few programs that solve such puzzles, using both the "nested for loops" and the "single loop and modulo" approaches. Both work, and so I think your testing code (what is inside the 10th for loop) may be at fault.
Here's some advantages and disadvantages I've found with both approaches:




#6
Nov3012, 12:46 PM

P: 12

@Uart
That makes for a much shorter and far clearer code than what I had. You really helped me out. Thank you! With that coded I've now got the task of finding unique solutions...I may be back for a little more help. Thank you again! Edit: @ Michael Redei Thank you for the insight. I read and responded to your post incorrectly before, sorry about that. Now, I just came up with another question. I will need to write a code like the one below to add all of the values together (SEND+MORE=MONEY), right?




#7
Nov3012, 01:38 PM

HW Helper
P: 6,925





#8
Nov3012, 05:17 PM

P: 12

Alright, I just took some time to reread all the posts in more detail. I was at school and trying to skim read, which was a poor choice. I apologize to those whose posts I responded to with nonsense.
I used "continue" like Michael used above for my for loops, it worked well when shrinking the number of calculations the program performs, but now when I try to calculate the values in the words I'm not getting any solutions. When I test my code out in a specific case it works fine, but I'm still not getting anything in a general case. I keep getting huge numbers that shouldn't even be possible combinations. Also, I was vague about what problem I'll be applying the code to, but it'll be a couple more problems other than SEND+MORE=MONEY. Is there a problem with this code?:




#9
Nov3012, 07:48 PM

HW Helper
P: 6,925

Each time you create a test set of 8 digits for {D, E, M, N, O, R, S, Y}, you need to create a test to convert SEND, MORE, and MONEY to integers, and then check if SEND + MORE = MONEY. You can use a similar method for other equations based on words.
Instead of using multiple if ... continues, you could use an inner loop / if to check for duplicate digits, but that requires using a goto in order to break out of the inner loop to the end of the current loop. 



#10
Dec112, 02:49 AM

P: 12

None of the methods involving nested for loops and hard coding seem to work. I tried it with continue, without continue, using the ! operator, replacing values with pointers, replacing values with variables, etc.
I wrote a code to test if word 1 + word2 = word3 and it works when I define the array myself, just like the codes that calculate the values of word 1, word2, and word 3. I checked to make sure my for loops were giving me single digits between 0 and 9. They were. As soon as I combine the codes, automating the population of the array for the tests, both codes stop working. When I print the values I'm getting 810 digits when there are only 4 digits in the word. Basically I'm stuck where I started. But I haven't tested out the single loop with integer division and modulus yet. I'll give a shot at that one. I've been working on this code from the time I woke up to the time I've gone to sleep the last two days, so I'm starting to get very frustrated as nothing seems to be working. 



#11
Dec112, 03:53 AM

HW Helper
P: 6,925

Start off with the initial case where {D, E, M, N, O, R, S, Y} = {0, 1, 2, 3, 4, 5, 6, 7}. This means D == 0, E == 1, M == 2, ... , Y = 7. Then "SEND" == 6130, "MORE" = 2451, and "MONEY" == 24317. The check will fail because SEND + MORE = 8581 which doesn't equal "MONEY" == 24317. Assuming this is homework, can you figure out the code to calculate the value of "SEND", "MORE", and "MONEY", based on substituting digits for letters? 



#12
Dec112, 11:22 AM

P: 12





#13
Dec112, 12:24 PM

HW Helper
P: 6,925





#14
Dec112, 12:52 PM

P: 12

2. Since my program has to be more general than just SEND+MORE=MONEY, do you think I should implement some limit to stop the loops once all the unique letters have been assigned numbers? 4. Wordsum1 is initialized with 10 positions at the beginning of the program (not shown), searcharray at 30 Word1[] is the array that contains the characters for the first word input. Searcharray[] contains the unique letters from all three word inputs In the specific case of SEND: word1[0]=S word1[1]=E word1[2]=N word1[3]=D For searcharray[] in SEND+MORE=MONEY: searcharray[0]=s searcharray[1]=e searcharray[2]=n searcharray[3]=d searcharray[4]=m searcharray[5]=o searcharray[6]=r searcharray[7]=y searcharray[8]=// searcharray[9]=// 5. Is that possible without making things really complicated... considering I'll be plugging in different words? 



#15
Dec112, 01:29 PM

HW Helper
P: 6,925

Assuming that you're always dealing with decimal numbers, then your generating all the perumutations of combinations of 10 digits taken n at a time, where n is the total number of different letters, so even the basic looping approach you have is affected by the number of different letters. Although the letter order isn't important, I would use the letters in alphabetical order, just to have some consistency in the way these programs work. If you wanted a somewhat "generic" solution, you could create an table of 256 pointers, indexed by the ASCII character value, most of which would be NULL pointers, and 8 of which would be pointers to a, b, c, ... h. Using my ordering, then table["D"] = &a, table["E"] = &b, ..., table["Y"] = &h. Then if you can implement C type strings in C# (variable length ASCII strings terminated by zero), you could create a generic function to convert a word string into an integer value. If not, then define words by having the first byte be a count for the number of letters, followed by a string of letters. You'd still be stuck with an equation that would probably be different for each problem. There are also alternate ways other than nested loops of generating combinations, then permutations for each combination, for 10 digits taken n at a time, but these methods are a bit complex, and uneeded for these word type problems. 



#16
Dec112, 07:59 PM

P: 12

I changed some things around following some of your advice and now I've got it working in general cases. I was able to calculate the two puzzles I need to (BASE+BALL=GAMES and SEND+MORE=MONEY) using the algorithm I've got. However, it takes a very long time for the solutions to be found. When I eliminate the unnecessary loops for each problem the solution process is much shorter.
Is continue the only/the easiest way I can prevent executing unnecessary loops here? For example, below, if I only had 2 unique letters I wouldn't need the third 'for' loop. How would I skip it?




#17
Dec112, 08:09 PM

HW Helper
P: 6,925

I'll have to search my old files for my combination and permutation stuff, and even though this code may be more generic, it may not be faster. I'll post an update later when I find this and figure it out. 



#18
Dec112, 09:27 PM

P: 12

If you've got to dig through old files to figure it out I won't put you through the trouble. I figured out how to use continue and I'm getting the correct answers with much faster computation times, only it is printing out the results twice for some reason. I have enough done at this point that I can take it in to my professor and work out that one last kink. Thank you so much for your help! I don't know that I would have finished this without hashing it out and getting ideas I wouldn't have thought of by myself. I really appreciate it. 


Register to reply 
Related Discussions  
returning values in array in c  Programming & Computer Science  4  
Fortran 77 making an array but changing the increment value  Programming & Computer Science  10  
How to search for duplicate values in an array of integers?  Programming & Computer Science  3  
converting from an array of function values to coordinate array of different length  Programming & Computer Science  3  
C prog: printing values from array of structures  Computing & Technology  36 