C#: Changing Values In an Array

[jellofaceman]

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 0-9 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.:

1A.
...
va[0]=1;
va[1]=2;
va[2]=3;
etc...

1B.
...
for(va[9]=0; va[9]<10; va[9]++)
{
   for(va[8]=0; va[8]<10; va[8]++)
   {
      for(va[7]=0; va[7]<10; va[7]++)
      {
         for(va[6]=0; va[6]<10; va[6]++)
         {
            for(va[5]=0; va[5]<10; va[5]++)
            {
               for(va[4]=0; va[4]<10; va[4]++)
               {   
                  for(va[3]=0; va[3]<10; va[3]++)
                  {
                     for(va[2]=0; va[2]<10; va[2]++)
                     {
                        for(va[1]=0; va[1]<10; va[1]++)
                        {
                           for(va[0]=0; va[0]<10; va[0]++)
                             //Below this: For loops that give words values

 

[uart]

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 let's 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.

 

[jellofaceman]

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

 

[uart]

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

Ok, one way to handle this is to have a single index variable (single for loop) running through the total number of possible combinations, and then use integer division/modulo to reconstruct the variable combinations corresponding to each particular value of the loop variable.

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

 

[Michael Redei]

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:

• Nested for loops
  • PRO: May be easier to understand for someone who doesn't know the program yet.
  • CON: Looks uglier though.
  • CON: Base 10 is hardwired into the structure of the looping construct.
  • CON: Tests 10^10 possibilities when only 10! ~ 3.6 x 10^6 are needed.
• Single for loop
  • PRO: More elegant.
  • PRO: Can be used for bases other than 10.
  • PRO: One loop is faster than 10 nested loops.
  • CON: Still tests 10^10 possibilities.

If speed is most important to you, you need to reduce the number of tests from 10^10 to 10!. That's possible with the 10 nested for loops:

for(va[9]=0; va[9]<10; va[9]++)
{
   for(va[8]=0; va[8]<10; va[8]++)
   {
      if (va[8] == va[9])
         continue;
      for(va[7]=0; va[7]<10; va[7]++)
      {
         if (va[7] == va[9])
            continue;
         if (va[7] == va[8])
            continue;
         for(va[6]=0; va[6]<10; va[6]++)
         {
            if (va[6] == va[9])
               continue;
            if (va[6] == va[8])
               continue;
            if (va[6] == va[7])
               continue;
            for(va[5]=0; va[5]<10; va[5]++)
            {
               // etc.

This is not possible for the single loop (as far as I can tell), so whatever you win in speed by having just one loop, you lose by having to execute it more often.

 

[jellofaceman]

@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?

//q, r, and s are the max size of each word 10^(#of letters in word-1) 
for(m=0; m<=q; m++)
{
  wordsum1=m; //assign value of word 1
  for(n=0; n<=r; n++)
  {
    wordsum2=n; //assign value of word 2
    for(t=0; t<=s; t++)
    {
     wordsum3=t; //assign value of word 3
    ...

 

[rcgldr]

I will need to write a code like the one below to add all of the values together (SEND+MORE=MONEY), right?

For this problem, there 8 letters to solve for: {D, E, M, N, O, R, S, Y}, with each having an unique value 0 through 9. If you want to use nested loops, you only need 8 levels of loops (not 10). Then for the inner most loop, you'll need to figure out how to determine if a potential set of 8 digits is a "valid" solution to the problem you're trying to solve.

 

[jellofaceman]

Alright, I just took some time to re-read 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?:

...
for(l=0; l<count4; l++)
//for all values of my unique letter array check if 
//the corresponding letter in word 1 is =
   {
      wordt1=0;
      for(k=0; k<count1; k++)
      { 
        //if the letter in word 1= the corresponding letter in unique array
        if(word1[k]==searcharray[l]) 

        { 
           // assign a temporary value to that number and give it a decimal position
           wordt1= pwr(va[l],(count1-(k+1))); 
        }
      }
      wordsum1=(wordsum1+wordt1); //add this to the total value of the word

   }

...

int pwr( int a, int b)
{
    int x;
    
    if(b==0)
       x=a;
    if(b==1)
       x=a*10;
    if(b==2)
       x=a*100;
    if(b==3)
       x=a*1000;
    if(b==4)
       x=a*10000;
       
 return x;
}

 

[rcgldr]

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.

 

[jellofaceman]

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

 

[rcgldr]

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 8-10 digits when there are only 4 digits in the word.

Using the send + more = money example, my guess is that after you generate a set of 8 digits, you don't have code to select the digits corresponding to the letters in the words and then to convert the "words" into integers.

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?

 

[jellofaceman]

my guess is that after you generate a set of 8 digits, you don't have code to select the digits corresponding to the letters in the words and then to convert the "words" into integers.

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?

As far as I can tell that is what I am doing. I must be wrong. Right below I describe the meaning of each line for my "check", below that I have the code combined. Unfortunately, this assignment isn't just the specific case of SEND+MORE=MONEY. It needs to be more general to words with as many as 10 characters.

for(l=0; l<count4; l++)//for every unique letter
 {
   wordt1=0;  //initialize wordt1 at zero to prevent unwanted calculations
   for(k=0; k<count1; k++)
   {
      if(word1[k]==searcharray[l])
    /* here I check if the characters in SEND have a corresponding
       value in my unique character array */
        {
           wordt1= va[l]*pwr((count1-4));
           /*if they do I assign a temporary number that will be
              added to the value of the word
          */
        }
       wordsum1=(wordsum1+wordt1);/*while there are still characters in the word
       add them to the final value of the word*/
       }
      }

I do the same thing for all three words then:

if(wordsum3==wordsum1+wordsum2)
   printf( "%i + %i = %i\n", wordsum1, wordsum2, wordsum3);

Here's the latest combined version of my code:

for(a=0; a<10; a++)
{
for(b=0; b<10; b++)  
{ 
for(c=0; c<10; c++)
{
for(d=0; d<10; d++) 
{
for(e=0; e<10; e++)
{
for(f=0; f<10; f++) 
{
for(g=0; g<10; g++)
{
for(h=0; h<10; h++) 
{
for(i=0; i<10; i++)
{
for(j=0; j<10; j++)
{

va[0]=*pa;
va[1]=*pb;
va[2]=*pc;
va[3]=*pd;
va[4]=*pe;
va[5]=*pf;
va[6]=*pg;
va[7]=*ph;
va[8]=*pi;
va[9]=*pj;

if(a!=b && a!=c && a!=d && a!=e && a!=f && a!=g && a!=h && a!=i && a!=j)
{
if(b!=c && b!=d && b!=e && b!=f && b!=g && b!=h && b!=i && b!=j)
{
if(c!=d && c!=e && c!=f && c!=g && c!=h && c!=i && c!=j)
{
if(d!=e && d!=f && d!=g && d!=h && d!=i && d!=j)
{
if(e!=f && e!=g && e!=h && e!=i && e!=j)
{
if(f!=g && f!=h && f!=i && f!=j)
{
if(g!=h && g!=i && g!=j)
{
if(h!=i && h!=j)
{
if(i!=j)
{

for(l=0; l<count4; l++)
 {
   wordt1=0;
   for(k=0; k<count1; k++)
   {
      if(word1[k]==searcharray[l])
        {
           wordt1= va[l]*pwr((count1-4));
        }
      }
         
   wordsum1=(wordsum1+wordt1);
   }
   //printf("Wordsum1: %i\n", wordsum1);
   
 for(m=0; m<count4; m++)
   {
      wordt2=0;
      for(n=0; n<count2; n++)
      {
      if(word2[n]==searcharray[m])
        { 
           wordt2=va[m]*pwr((count2-4));
        }
      }
      wordsum2=(wordsum2+wordt2);
      
   }
  //printf("Wordsum2: %i\n", wordsum2);
for(m=0; m<count4; m++)
   {
      wordt3=0;
      for(n=0; n<count3; n++)
      {
      if(word3[n]==searcharray[n])
        {  
           wordt3=va[n]*pwr((count3-4));
        }
      }
      wordsum3=(wordsum3+wordt3);
      
   }
   //printf("Wordsum3: %i\n", wordsum3);
if(wordsum3==wordsum1+wordsum2)
   printf( "%i + %i = %i\n", wordsum1, wordsum2, wordsum3);
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}

 

[rcgldr]

va[0]=*pa;
va[1]=*pb;
va[2]=*pc;
va[3]=*pd;
va[4]=*pe;
va[5]=*pf;
va[6]=*pg;
va[7]=*ph;
va[8]=*pi;
va[9]=*pj;

Why isn't this just va[0] = a; va[1] = b; ... , va[9] = j; , and what are you using va for? Also for send + more = money, you only have 8 letters, so there's no need to generate permutations of a list of 10 digits. The goal in this case should be to generate all the permuations of 10 digits taken 8 at a time, then for each permutation, substitute digits for letters of the words, convert the words to their integer equivlents and then determine the sum to check for a possible answer. Using the method you've shown, you only need to iterate a through h, from 0 to 9.

for(l=0; l<count4; l++)
 {
   wordt1=0;
   for(k=0; k<count1; k++)
   {
      if(word1[k]==searcharray[l])
        {
           wordt1= va[l]*pwr((count1-4));
        }
      }
   wordsum1=(wordsum1+wordt1);
   }
   //printf("Wordsum1: %i\n", wordsum1);

I don't see where wordsum1 is initialized. What are word1[] and searcharray[]? The letter to digits conversion is {D, E, M, N, O, R, S, Y} = {a, b, c, d, e, f, g, h}, or "D" == a, "E" == b, ..., "S" == g, "Y" == h. Rather than trying to make the check part generic, you could just hard code the calculation for each word. For example, "YES" => h*100 + b*10 + g. Given this, how would you write the code to calculate the values for "SEND", "MORE", and "MONEY"?

 

[jellofaceman]

1. Why isn't this just va[0] = a; va[1] = b; ... , va[9] = j; , and what are you using va for?

2. for send + more = money, you only have 8 letters, so there's no need to generate permutations of a list of 10 digits. The goal in this case should be to generate all the permuations of 10 digits taken 8 at a time, then for each permutation, substitute digits for letters of the words, convert the words to their integer equivlents and then determine the sum to check for a possible answer. Using the method you've shown, you only need to iterate a through h, from 0 to 9.

3. I don't see where wordsum1 is initialized.

4. What are word1[] and searcharray[]?

5. Rather than trying to make the check part generic, you could just hard code the calculation for each word.

1. I'm not sure why I had pointers instead of just directly plugging in the values. It's changed now.

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?

 

[rcgldr]

Word1[] is the array that contains the characters for the first word input. Searcharray[] contains the unique letters from all three word inputs. Is that possible without making things really complicated... considering I'll be plugging in different words?

You don't really need word1[] or searcharray[]. Trying to make a generic solution is overly complicated. I'm assuming for each problem that the equation, the number of words, the number of letters per word, and the total number of unique letters is going to be different.

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.

 

[jellofaceman]

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?

for(va[0]=1; va[0]<10; va[0]++)
	for(va[1]=0;va[1]<10; va[1]++)
	   for(va[2]=0; va[2]<10; va[2]++)

 

[rcgldr]

For example, below, if I only had 2 unique letters I wouldn't need the third 'for' loop. How would I skip it?

For now only use the number of loops that equals the number of letters, for two letters, just two loops.

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.

 

[jellofaceman]

For now only use the number of loops that equals the number of letters, for two letters, just two loops.

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.

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

 

[rcgldr]

If you've got to dig through old files to figure it out.

I found my example programs, but these involve algorithms that are non-obvious and beyond what you'd be expected to know in class. I'm not sure how the professor expected students in your class to generate combinations and permulations other than the brute force method of using nested loops, which you already did, or a single loop with division and modulo to create a set of digits which was sugggested in this thread.

The issue with permutation algorithms is that the code itself isn't difficult to follow, but understanding why these work is much more complicated. Once you're done with this assignment, you can do a web search for "next permutation", which should get you a few web sites that show various algorithms for doing this. (Note - all of the recursive algorithms I could find generate all the permutations, but not in sequential order). I assume that in your class, the students are supposed to create their own algorithms as opposed to using algorithms they find at various web sites or references, unless the class uses a textbook that includes the algorithms the students are supposed to use.

 

[jellofaceman]

I'm not sure how the professor expected students in your class to generate combinations and permuations other than the brute force method of using nested loops, which you already did...

I assume that in your class, the students are supposed to create their own algorithms as opposed to using algorithms they find at various web sites or references...

The assignment actually tells us that we need to use a brute force method to solve the puzzles. It vaguely describes an algorithm we can implement to accomplish this; finding unique letters, assigning them all possible values 0-9, checking the value of the words against each other.

I'll have to take a look at the "next permutation" approach once school has slowed and I get time. I'd like to know another way of solving this.

Thanks again for all your help!

 

[rcgldr]

I'll have to take a look at the "next permutation" approach once school has slowed and I get time. I'd like to know another way of solving this.

The iterative code for next permutation is less than 20 lines of code (plus a 3 line swap function and a function called each time a permuation is generatred). The code and the algorithm are easy to follow. The issue is you'll need step through the code a few times to understand why it works. The recursive versions are even smaller, but they don't produce the permutations in "order".