Find expressions equal to a given number using 15 integers with 4 operators

Question

For example, given 15 integers

70, 75, 32, 4, 64, 98, 73, 52, 36, 88, 96, 58, 79, 39, 75

How can we obtain is 72?

4 operators can be used for the 15 integers to get the equation to the answer of 72, which are + - * /. Divison is only allowed where there is no remainder. A few answers will be

• 4+32+36+39+52-58-64-70+73+75/75-79-88+96+98
• 4+32+36-39-52+58*64+70+73*75+75+79+88-96*98
• 4+32*36*39/52-58+64-70+73*75-75*79-88-96-98
• 4+32*36*39/52-98+64-70+73*75-75*79-88-96-58

Rules

• 5+1-3 and 5-3+1 are 2 different answers.
• No duplicated answer.
• All 15 integers must be used in the equation in any order.

Time given is 200 seconds.

What is the "best" strategy or optimization can be used to obtain as many expressions as possible in the allotted time? The brute-force complexity is (15!*4¹⁴), which is approximately 3.5 × 10²⁰.

The code below is the code written by me and it is partially optimized by me, it just able to compute 1.0e9 combinations in 200s. Performance analysis shows that prev_num_pos() used 31% of computation time and nextoptgroup() used 15% of computation time.

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

#define PROBLEMSIZE 15
#define PRINTTOSCREEN false
#define OPERATIONUSED 3

int numgroup[PROBLEMSIZE]; //numbers array
int optgroup[PROBLEMSIZE - 1]; //operations array
int theanswer; //the target answer
int size=PROBLEMSIZE;
ofstream output("solution.txt", ios::app);

bool nextoptgroup(){ //true = success next-ed, false = tried all combinations
    for (int i = PROBLEMSIZE - 2; i >= 0; i--){ //bruteforce type
        if (optgroup[i] < OPERATIONUSED){ //increase itself if possible
            optgroup[i] += 1;
            break;
        }
        else { //optgroup[i] == 3
            optgroup[i] = 0;  //reset itself to 0 and continue to increase its parent
        }
        if (i == 0){
            return false;
        }
    }
    return true;
}

char symbols(int s){
    switch (s){
    case 0:
        return '+';
    case 1:
        return '-';
    case 2:
        return '*';
    case 3:
        return '/';
    default:
        return '$';
    }
}

void print_out(int status =0){ //0 = do not print to file, 1 = correct answer, print to file
    if (PRINTTOSCREEN) cout << numgroup[0];
    if (status==1) output << numgroup[0];
    for (int i = 0; i < PROBLEMSIZE-1; i++){
        if (PRINTTOSCREEN)  cout << symbols(optgroup[i]) << numgroup[i + 1];
        if (status == 1) output << symbols(optgroup[i]) << numgroup[i + 1];
    }
}

//only will use for * / , priortized
int prev_num_pos(int opt[], int pos){ //check for prev non -1 position, return num pos
    for (int i = pos - 1; i >= 0; i--){ //used for num position
        if (opt[i] != -1) return i + 1;
    }
    return 0;
}

void debug_print(int num[],int opt[]){
    cout << num[0];
    for (int i = 0; i < PROBLEMSIZE - 1; i++){
        if (opt[i]!=-1) cout << symbols(opt[i]) << num[i + 1];
    }
    cout << endl;
    system("PAUSE");
}

int main(){
    ifstream input("problems.txt");
    if (input.is_open() == false) return 1;
    for (int i = 0; i < PROBLEMSIZE; i++) { //get problems
        input >> numgroup[i];
    }
    input >> theanswer; //get answer
    input.close();
    cout << "Numbers given: "<< numgroup[0];
    for (int i = 1; i < PROBLEMSIZE; i++) { //show problems
        cout << ", " << numgroup[i];
    }
    cout << endl << "The answer needed: " << theanswer << endl << endl;
    if (PRINTTOSCREEN) system("PAUSE");
    for (int i = 0; i < PROBLEMSIZE - 1; i++) { //initialize optgroup
        optgroup[i] = 0;
    }

    sort(numgroup, numgroup + PROBLEMSIZE);//sort the problems



    do { //iterate every combinations
        //calculate the answer based on numgroup and optgroup
        //need give priority to * / % left to right otherwise
        do { //for each combination of number need to go through each operation combination
            //create a copy for calculation, both num n opt
            int cnumgroup[PROBLEMSIZE];
            int coptgroup[PROBLEMSIZE];
            size = PROBLEMSIZE;
            for (int i = 0; i < PROBLEMSIZE; i++){
                cnumgroup[i] = numgroup[i];
            }
            for (int i = 0; i < PROBLEMSIZE; i++){
                coptgroup[i] = optgroup[i];
            }
            //bool to skip this undivisible loop
            bool cont = false;
            //give priority
            for (int it = 0; it < PROBLEMSIZE - 1; ++it) { //it = position of opt
                int prev_pos = -1;
                if (coptgroup[it] == 2 || coptgroup[it] == 3){ // !goodforpermfornace
                    prev_pos = prev_num_pos(coptgroup, it);
                }
                else continue;
                if (coptgroup[it] == 2){ //for multiplier*
                    cnumgroup[prev_pos] = cnumgroup[prev_pos] * cnumgroup[it + 1];
                    coptgroup[it] = -1; //set operator to used
                    //debug_print(cnumgroup, coptgroup); //!debug!
                }
                else if (coptgroup[it] == 3) { //for division/
                    if (cnumgroup[prev_pos] % cnumgroup[it + 1] != 0){ //have remainder, undivisible
                        cont = true;
                        break;
                    }
                    else {
                        cnumgroup[prev_pos] = cnumgroup[prev_pos] / cnumgroup[it + 1];
                        coptgroup[it] = -1; //set operator to used
                        //debug_print(cnumgroup, coptgroup); //!debug!
                    }
                }
            }
            if (cont) continue;
            //do remaining add and subtract
            for (int it = 0; it < PROBLEMSIZE - 1; ++it) {
                if (coptgroup[it] == -1) continue; // !goodforpermfornace
                if (coptgroup[it] == 0){ // for addition+
                    cnumgroup[0] = cnumgroup[0] + cnumgroup[it + 1]; //add to the first number
                    coptgroup[it] = -1; //set operator to used
                    //debug_print(cnumgroup, coptgroup); //!debug!
                }
                else if (coptgroup[it] == 1) { //for subtraction-
                    cnumgroup[0] = cnumgroup[0] - cnumgroup[it + 1]; //subtract the first number
                    coptgroup[it] = -1; //set operator to used
                    //debug_print(cnumgroup, coptgroup); //!debug!
                }
                else if (coptgroup[it]!=-1) { //!performance!
                    if (PRINTTOSCREEN)  cout << "ERROR FOUND!! CODE:ADDSUBLOOPBUTNOT\n";
                }
            }
            //finished all the calculation, check the answer
            if (cnumgroup[0] == theanswer){
                //answer found
                //print it out
                print_out(1);
                output << endl;
                if (PRINTTOSCREEN)  cout << "\tCorrect\n"; //!performance!
            }
            else { // !BAD!performance!
                if (size > 1){
                    if (PRINTTOSCREEN)  cout << "ERROR FOUND!! CODE:CNUMGROUPSIZEisNOT1\n";
                }
                else {
                    print_out();
                    if (PRINTTOSCREEN)  cout << "\tWrong\n";
                }
            }
        } while (nextoptgroup());
    } while (next_permutation(numgroup, numgroup + PROBLEMSIZE));

    output.close();
    return 0;
}

Answer 1

Another way of looking at it is, rather than rearranging the numbers, just rearrange the symbols. For example, with your fifteen numbers you have 14 symbols between them, with any of 4 values: - + / *

Since each location is independent of each other, you are actually describing a binary number, with 2 bits per symbol location, for a total of 28 bits (=268,435,456)

Looked at it from this point of view, you just count from 0 to 268435456 and use each pair of bits in sequence to determine whether you use a +, -, / or * at that point. Here's some code that does that:

int a[]={4, 32, 36, 39, 52, 58, 64, 70, 73, 75, 75, 79, 88, 96, 98};
int aTot=sizeof(a)/sizeof(a[0]);
long i=0, bitMask=1, sum=0, count=0, limit=268435456;
for (long bits=0;bits<limit;++bits)
{
  bitMask=bits;
  sum=a[0];
  for (i=1;i<aTot;++i)
  {
    switch (bitMask & 0x3 )
    {
      case 0:
        sum-=a[i];
        break;
      case 1:
        sum+=a[i];
        break;
      case 2:
        sum*=a[i];
        break;
      case 3:
        if ( ( sum % a[i] ) != 0 )
        {
          sum=-1;
          i=9999;
          break;
        }
        sum/=a[i];
        break;
    }
    bitMask>>=2;
  }
  if (sum==72)
  {
    bitMask=bits;
    std::cout << count++ << ": " << a[0];
    for (i=1;i<aTot;++i)
    {
      switch (bitMask & 0x3 )
      {
        case 0:
          std::cout << " - ";
          break;
        case 1:
          std::cout << " + ";
          break;
        case 2:
          std::cout << " * ";
          break;
        case 3:
          std::cout << " / ";
          break;
      }
      std::cout << a[i];
      bitMask>>=2;
    }
    std::cout << '\n';
  }
}

We massage the bits to get our sum, and if it matches 72, we just repeat the process to print out the formula.

Note the test for division - if the modulo fails, then it won't divide evenly, so we give up and break out of the loop.

Using this, I got 157 answers in about 11 seconds - which gives you another 189 seconds to permute the numbers and run it again (check out next_permutation for how to speed that up). Or you could take those 157 answers and rearrange them, letting you skip some math (and gain some speed).

In any case, hopefully this will give you a starting point to do the calcs...

Answer 2

Namespaces

using namespace std; is considered bad practice. Short code is not a requirement in C++, clear code is preferred.

System

system("PAUSE"); is considered bad practice. cin.get() halts the program waiting for user input in a more standardized and portable-friendly way.

Return

return 0; is a legacy from C. In C++, it's no longer required to write this manually. The compiler will take care of returning 'normal' if no errors were thrown or other returns (like -1) are encountered.

Answer 3

If you want to produce the same output, but do the * / calcs first, you need to store the intermediate values in a stack or array:

int a[]={4, 32, 36, 39, 52, 58, 64, 70, 73, 75, 75, 79, 88, 96, 98};
const int aTot=sizeof(a)/sizeof(a[0]);
long i=0, bitMask=1, sum=0, limit=268435456;
long stack[aTot], sI=0;
for (long bits=0;bits<limit;++bits)
{
  bitMask=bits;
  stack[0]=a[0];
  sI=1;
  for (i=1;i<aTot;++i)
  {
    switch (bitMask & 0x3 )
    {
      case 0:
        stack[sI++]=-a[i];
        break;
      case 1:
        stack[sI++]=a[i];
        break;
      case 2:
        stack[sI-1]*=a[i];
        break;
      case 3:
        if ( ( stack[sI-1] % a[i] ) != 0 )
        {
          sI=0;
          i=9999;
          break;
        }
        stack[sI-1]/=a[i];
        break;
    }
    bitMask>>=2;
  }
  sum=0;
  for (i=0;i<sI;++i)
    sum+=stack[i];
  if (sum==72)
  {
    bitMask=bits;
    std::cout << a[0];
    for (i=1;i<aTot;++i)
    {
      switch (bitMask & 0x3 )
      {
        case 0:
          std::cout << " - ";
          break;
        case 1:
          std::cout << " + ";
          break;
        case 2:
          std::cout << " * ";
          break;
        case 3:
          std::cout << " / ";
          break;
      }
      std::cout << a[i];
      bitMask>>=2;
    }
    std::cout << '\n';
  }
}

The code is vary similar to the previous code; however, instead of calculating the sum right away, we store results in an array called stack. If it's a +- term, we make it a new stack item; if it's */ we combine it with the latest stack item instead, giving a new value.

Once we're done, the stack has all the terms, but the */ ones have been combined - so now we just need to add them all, and see if they match 72.

This code will take one sequence of a[] and try all possible formulas for it - then, you can just permute the a[] array and rerun it to generate as many as possible. Hope it helps.