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?

Troopship

Answer 1

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;
  }
}

Vish

Ah, now I understand what Brian Schroth wrote. I've been trying to figure out his answer.<br/> Indeed I came to the conclusion B = 1, T = 1 and H = 1 at least (means can't be 0), because each and every one of those leters are first in every "word". Well, T = E + S % 10 that I didn't conclude, interestint though.<br/> I'm going try this. Thanks for the pointers folks! – Split

If you can logically deduce things, the simplest solution is in 1 iteration- set each thing to the correct value, since the whole solution can be logically deduced, and call it a day! I think if you're going to do it algorithmically, you need to do all the logic algorithmically. So deducing that B = 1 is fine, but you should include lines of code that calculate it to be 1 instead of just defining it as 1. Of course, it's a self-challenge, so you can do whatever you want! – Ancell

Brian - there's isn't necessarily a single solution to puzzles like this. This one, in particular, has 6. While you can find them out manually, it does involve actually iterating and checking - and your CPU would likely do it faster :-) – Vish

Answer 2

Maybe you might want to look this repository : it is a solution to solve verbal-arithmetic problems using JavaFX. Firefly Algorithm for Verbal-arithmetics problem [GitHub]

Percentage

Answer 3

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.

Ancell

Answer 4

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:

Compute a list of distinct odd numbers (if one exists), such that their sum is equal to a given number

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.

Formate

Answer 5

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.

Carriole

Hm, I thought maybe there's some different, somewhat more efficient approach with control flow statements to this HES+THE=BEST verbal arithmetic. Because in my eyes 15000 and odd loop cycles for the solutions is a lot. Maybe I'm just wrong, I dunno. Efficiency comes later, I was just wondering if perhaps there is another way.. – Split

Answer 6

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.

Nipple

Your solution gives 885 iterations for outer loop and from 66 to 1827 iterations for inner loop; that's definitely not the most optimal approach. Also, while the logic you describe is indeed simple and clear the two "for" loops are not; "check" function based on this approach would likely not be very straightforward either. – Vish

oh, i know that this is in no way a final solution, if i were to solve this problem, I'd search for other ways to constraint the iterations. Also I'd use the Min() function of my language of choice, I just added the (granted ugly) inline conditional because he meant he can't use functions. so well, my whole post was rather meant as a nudge in the direction of a possible solution. the puzzle wouldn't be much fun if I just post a complete solution. And NoCanDo was clearly asking for "pointers" not for final solutions :) – Nipple

Answer 7

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.

Acciaccatura