A more efficient approach to Verbal arithmetic / Alphametics?

Question

Perhaps most of you know the Send + More = Money. Well, I'm currently learning java and one of the exercises is I have to solve HES + THE = BEST.

Now, so far I can/should use if-for-while-do loops, nothing else. Although I'm sure there are different methods to solve it, that's not the point of the exercise I'm going through. I have to be able to use if-for-while-do loops the most efficient way.

My problem? I can't seem to think of an efficient way to solve it! I've come up with this, which solves the puzzle, but is perhaps the worst efficient way to do so:

public class Verbalarithmetics {

    public static void main (String args[]) {
     // Countint Variables
     int index_h = 0;
     int index_e = 0;
     int index_s = 0;
     int index_t = 0;
     int index_b = 0;

     // Start with h = 1 and increase until the else-if statement is true
     for(int h = 1; h <= 9; h++) { // h = 1, because first Symbol can't be zero
      index_h++;
       // Increase e so long until e equals h
       for(int e = 0; e <= 9; e++) {
        index_e++;
           if (e == h) {
              continue;
           }

           // Increase s so long until s equals h or e
           for(int s = 0; s <= 9; s++) {
            index_s++;
              if (s == h || s == e) {
                 continue;
              }//end if

              // Increase t so long until t equals h or e or s.
              for(int t = 1; t <= 9; t++) { // t = 1, because 1st Symbol cant be zero
               index_t++;
                if(t == h || t == e || t == s) {
                   continue;
                }// end if

                // Increase b so long until b equals h, e, s or t.
                for(int b = 1; b <= 9; b++) { // b = 1, weil das 1. Symbol nicht für eine 0 stehen darf
                 index_b++;
                    if (b == h || b == e || b == s || b == t) {
                        continue;
                    }// end if

           // x = 100*h + 10*e + s
           // y = 100*t + 10*h + e
           // z = 1000*b + 100*e + 10*s + t
                    // Check if x+y=z, if true -> Print out Solution, else continue with the upper most loop
                    else 
                     if (100*h + 10*e + s + 100*t + 10*h + e == 1000*b + 100*e +10*s + t) {
                      System.out.println("HES + THE = BEST => " + h + e + s + " + " + t + h + e + " = " + b + e + s + t);
                      System.out.println("With H=" + h + ", E=" + e + ", S=" + s + ", T=" + t + ", und B=" + b + ".");
                      System.out.println("It took " + index_h + 
                        " Loop-Cycles to find 'h' !");
                      System.out.println("It took " + index_e + 
                        " Loop-Cycles to find 'e' !");
                      System.out.println("It took " + index_s + 
                        " Loop-Cycles to find 's' !");
                      System.out.println("It took " + index_t + 
                        " Loop-Cycles to find 't' !");
                      System.out.println("It took " + index_b + 
                        " Loop-Cycles to find 'b' !");
                      System.out.println("This is a total of " + (index_h + index_e + index_s + index_t + index_b) + 
                        " Loop-Cycles");
                    }// end else if
                }//end for
              }//end for
           }//end for
        }//end for
     }//end for
    } 
}

It takes about 15000 odd loop-cycles in total to solve this puzzle. That's a lot in my opinion. Any pointers, please?

To the editiors: Would you pretty please refrain from adding in "homework" as a tag? This isn't homework. This is self-exercise. What? I can't read a book and do exercises according to it? It has to be homework?...seriously, stop it.

Answer 1

Efficiency goes out the window if the standard approach is to brute force it, as suggested here. The most efficient way that only uses loops probably involves calculating the exhaustive set of possibilities, storing them, then iterating through each one to see if it works.

Answer 2

Instead of looping through all values of the letters, loop through the possible values for S, E, and T. S + E % 10 should be T. Once you have a set of potential S,E,T solutions, find the loop through the possible E+H+(0 or 1, depending on if S+E is greater than 9)=S solutions...and so on, and so on.

Answer 3

The big question here is: can you (do you want to) logically deduce certain constraints and apply them to your algorithm or do you want to brute-force it? Assuming the former, some of them are pretty obvious:

• B = 1
• T can't be 0 (because it's first in THE), thus neither S nor E can be 0 either.
• T = E + S % 10

Thus you have S, E, H to loop through giving you at most 9 * 8 * 8 combinations which is 576. Add to that the fact that H + T must be greater or equal to 9 and you'll reduce this even further.

Update Here's a quick and ugly solution. It's based only on 3 constraints listed above.

public class Puzzle {
  public static void main(String[] args) {
    for (int S = 1; S<10; S++) {
      for (int E = 1; E<10; E++) {
        if (S==E) continue; // all letters stand for different digits
        for (int H = 1; H<10; H++) {
          if (H==E || H==S) continue; // all letters stand for different digits
          checkAndPrint(S, E, H);
        }
      } // for
    } // for
  } // main

  private static boolean checkAndPrint(int S, int E, int H) {
    int T = (S + E) % 10;
    int S1 = (E + H) + (S + E) / 10; // calculates value for 'S' in 'BEST' (possibly + 10)
    if (S1 % 10 != S) return false;
    int E1 = H + T + S1 / 10; // calculates value for 'E' in 'BEST' (possibly + 10)
    if (E1 % 10 != E) return false;
    System.out.println(H + "" + E + "" + S + " + " + T + "" + H + "" + E + " = 1" + E + "" + S + "" + T);
    return true;
  }
}

Answer 4

uhm you could do a lot in the form of optimisation in your approach.

first of all, get the maximum value for "BEST". assume "HES" has the highest possible value, 987, then "THE" would be X98 so the highest value for "THE" is 698 which gives 987+698=1685.

if "THE" has the highest value, THE would be 987 and HES would be 876 -> 876+987=1863, which is higher than 1685, so 1863 is an upper bound for "best". So you could have your program adjust the upper bound for "B" to 1 (which in this case already yields you the first digit..). the lower bound for BEST is easy, as it's 1023.

then you do something like this:

for(i=102;i<=987;i++)
{
    for(j=1023-i;j<=(1863-i < 987 ? 1863-i:987);j++)
    {
        //check if the solution matches and doesn't have duplicate digits
    }
}

this way you discard a lot of impossible combinations right away through the values in the inner for loop. and I bet there are similar ways to constrain the space of possible solutions more.

And the program is way less complex this way.

Answer 5

That class of problem is the poster child for query optimisation. Java isn't for that.

If you have fewer than a few tens of billion states, brute force it. It will take much less time to run a brute force search than it would to create an optimising query engine.

Answer 6

I am not an expert, but it could be worth looking at languages which manage constraints such as Prolog. There's a very similar problem here:

http://stackoverflow.com/questions/1786365/compute-a-list-of-distinct-odd-numbers-if-one-exists-such-that-their-sum-is-eq

Prolog is a different type of language but if you are doing this for your own education then it will certainly exercise your brain :-)

It will be possible to code general approaches to alphametics - not just the rather simple one here.

An alternative - which is not guaranteed to give a result - is to use an optimisation technique such as genetic algorithms. Guess a number of solutions, and compute how close they are to the correct solution, and then adjust them. You may get partial solutions by this method.