USACO Crypt1 Problem!

[jhoojhoo]

Hello all. I am working on a USACO problem for practice. The question asks:

The following cryptarithm is a multiplication problem that can be solved by substituting digits from a specified set of N digits into the positions marked with *. If the set of prime digits {2,3,5,7} is selected, the cryptarithm is called a PRIME CRYPTARITHM.

   
/***  
      * * *
    x   * *
    -------
      * * *         <-- partial product 1
    * * *           <-- partial product 2
    -------
    * * * *
***/

Digits can appear only in places marked by `*'. Of course, leading zeroes are not allowed.
Note that the 'partial products' are as taught in USA schools. The first partial product is the product of the final digit of the second number and the top number. The second partial product is the product of the first digit of the second number and the top number.

Write a program that will find all solutions to the cryptarithm above for any subset of digits from the set {1,2,3,4,5,6,7,8,9}.

My code passes for 3 tests but fails on the fourth:
7
4 1 2 5 6 7 3
----- our output --------- (correct answer vs incorrect)
384
---- your output ---------
270
-------------------------
An example of one that passes:
5
2 3 4 6 8

Output: 1

By looking at this:

/***
      5 4 2
   x    3 1
    -------
      * * *         <-- partial product 1
    * * *           <-- partial product 2      4*3    1*4    1*4+4*3
    -------
    * x y z

***/

My approach is to loop through the values 1-5 in the diagram above, getting all permutations and testing if they pass the necessary conditions along the way. Only continuing if the elements we've plugged in so far make no contradictions and increment a counter if we pass the final conditional. The conditionals just check to see if the number is in our vector of given numbers to work with. I made sure to carry over any values that had to be carried over. Is there a flaw in this approach? I feel there is some gap in my approach that I am missing. If anyone could help it would be very appreciated! It mentions PRIME Cryparithm, perhaps this is a special case? Hmm , the fail case isnt a prime cryparithm either way.

In the most simple sense I am going through the grade school multiplication algorithm with partial products, and testing at each loop.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>

using std::vector;      using std::cin;
using std::cout;        using std::endl;

  int main()
{
     vector<int> numbers;
     int counter = 0;
     int s_one, s_two, s_three, s_four, s_five;
     int data_size;
     cin >> data_size;
     for (int i = 0; i < data_size; i++){
        int x;
        cin >> x;
        numbers.push_back(x);
    }
   
    sort (numbers.begin(), numbers.end());
   
    for (vector<int>::const_iterator iter = numbers.begin(); iter != numbers.end(); ++iter){
        cout << *iter << ' ';
    }
    cout << endl;

    // Start search.  5 Loops for each element as labeled in comment (1 through 5).
   for (int i = 0; i < numbers.size(); i++){
        s_one = numbers[i];
        cout << "Current count:  " << counter << endl;

        for (int j = 0; j < numbers.size(); j++){
            s_two = numbers[j];
            int carry1 = 0;     // Value to carry over.
            int mult1 = s_one * s_two;
           
            if (mult1 > 9){     // Calculate carry value if needed...
                carry1 = mult1/10;
                mult1 = mult1 % 10;
            }

            if (find(numbers.begin(),numbers.end(), mult1) != numbers.end()){

            for (int k = 0; k < numbers.size(); k++){
                s_three = numbers[k];
                int carry2 = 0;
                int mult2 = s_three * s_two;
               
                if (mult2 > 9){     // Calculate carry value if needed...
                    carry2 = mult2/10;
                    mult2 = mult2 % 10;
                }


                if (find(numbers.begin(),numbers.end(), mult2) != numbers.end()){
                for (int l = 0; l < numbers.size(); l++){
                    s_four = numbers[l];
                    int mult3 = s_three * s_four + carry2;
                    int mult4 = s_one * s_four + carry1;
                    int carry3 = 0, carry4 = 0;
                    
                    if (mult3 > 9){
                        carry3 = mult3/10;
                        mult3 = mult3 % 10;
                    }
                    if (mult4 > 9){         
                        carry4 = mult4/10;
                        mult4 = mult4 % 10;
                    }
                    
                    int sum1 = mult2 + mult4;
                    int sum_carry1 = 0;
                    
                    if (sum1 > 9){              
                        sum_carry1 = sum1/10;
                        sum1 = sum1 % 10;
                    }

                    if (find(numbers.begin(),numbers.end(), mult3) != numbers.end() &&
                        find(numbers.begin(),numbers.end(), mult4) != numbers.end() &&
                        find(numbers.begin(),numbers.end(), sum1) != numbers.end()){

                    for (int m = 0; m < numbers.size(); m++){
                        s_five = numbers[m];
                        int mult5 = s_three * s_five + carry3;
                        int mult6 = s_one * s_five + carry4;
                        if (mult5 > 9 || mult6 > 9){
                            continue;       // Condition breaks our template.
                        }
                        int sum2 =  mult6 + mult3 + sum_carry1;
                        if (sum2 > 9){
                            continue;
                        }
                        int status = -1;
                        if (find(numbers.begin(),numbers.end(), mult5) != numbers.end() &&
                            find(numbers.begin(),numbers.end(), mult6) != numbers.end() &&
                            find(numbers.begin(),numbers.end(), sum2) != numbers.end()){
                            counter++;
                            cout << "SOLUTION FOUND!" << endl;
                            status = 0;
                            }
                            if (status == -1){
                                cout << endl;
                                cout << "__Current values__ " << endl;
                                cout << "Numbers at i: " << numbers[i] << endl;
                                cout << mult1 << ' ' << mult2 << ' ' << mult3 << ' ' << mult4 << ' ' << mult5 << ' ' << mult6 << endl;
                                cout << sum1  << ' ' << sum2 << endl;
                                cout << "********" << endl;

                               system("pause");
                            }
                    }   // End loop 5
                  }


                } // End loop 4
              }


            } // End loop 3
          }


        } // End loop 2

   } // End loop 1

   cout <<  counter << endl;
}

[kevinkjt2000]

The problem you posted dictates using digits

from the set {1,2,3,4,5,6,7,8,9}

. Why would you only use 1-5?
Never mind I see what you meant by diagram above now.

Edit: I would suggest an approach using backtracking. I will try to type one up later to demonstrate if you would like.
http://en.wikipedia.org/wiki/Backtracking

[jhoojhoo]

Thanks for the reply.

Hm. I thought this was a backtracking method, since we build our solutions step by step, but stepping back, or in this case looping to the next value if the number is invalid.

I'm still stumped as to why this won't work :( But if you have another way I would love to see!

[kevinkjt2000]

Here is the solution I promised: http://ideone.com/qenDWZ
Let me know if there are sections you would like for me to explain.
The code is not ultra efficient, but it does run through the combinations pretty fast.