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

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!*414), which is approximately 3.5 × 1020.

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 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;
if (status==1) output << numgroup;
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;
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.close();
cout << "Numbers given: "<< numgroup;
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 = cnumgroup + 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 = cnumgroup - 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 == theanswer){
//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;
}
• I'd sort the numbers and employ a tree to memoize previous operations like in a transaction database. I'd also memoize and check for repeated operations (they would be invalidated) At the end, I'd filter the valid leafs for 70. Assuming they can all divide each other and none are unique, you have a worst case of 120 operations (not instructions) to run, and this can easily be done on one pass after trivial sorting. Just an algorithmic tip. – Isiah Meadows Jun 26 '16 at 14:10
• Also, don't be afraid of labelled loops. Your cont = true; break; could be simplified to continue loop;, adding a loop: before your inner do ... while, and removing the if (cont) continue; statement. – Isiah Meadows Jun 26 '16 at 14:13
• I'm not a frequent C++ user, but I've used those a few times even in JS. It's much simpler conceptually IMO, and it's easier to optimize (I don't think g++ is quite that intelligent yet, but who knows). – Isiah Meadows Jun 26 '16 at 14:14
• @IsiahMeadows Since performance is the main priority here, labelled loop is fine if it can improve performance. But is it the loop checking is the bottleneck here? – B. Liew Jun 26 '16 at 14:31
• @B.Liew I may have been wrong with 480, but I got it from 4 * (1 + 2 + ... + 15), one for each possible branch of the largest tree. And yes, my method originally lacked that ability, but I've revised it some. See this gist for more details. It also includes a JS version where I normally think a little more functionally. It's highly recursive, but that should never be a problem in practice. – Isiah Meadows Jun 30 '16 at 11:37

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);
long i=0, bitMask=1, sum=0, count=0, limit=268435456;
for (long bits=0;bits<limit;++bits)
{
sum=a;
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;
}
}
if (sum==72)
{
std::cout << count++ << ": " << a;
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];
}
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...

• Thanks for the attempt, but the * and & do have higher priority than - +, which makes it more complicated. As an example, 5+3*4 is actually 18 and not 32. If you take care of the * / priority, will your idea still work? – B. Liew Jun 27 '16 at 16:35
• Yes - you'd just have to do two passes - one to calculate the * / terms and another to calculate the remaining - + terms. There would be more bookkeeping as well (temporary values), but since the binary number bits represents the symbol between values, you would still end up trying every possible symbol for a given sequence of numbers. – Dave P. Jun 27 '16 at 21:48
• You bitMask method is actually very fast compare to the array's element by element increment method. Can you give an idea that can do the bookkeeping work in an optimized way? – B. Liew Jun 29 '16 at 20:01
• Especially when there are consecutive * / in a sequence, like 1+a*b/c+2 , which it must do a*b=z first then only z/c=y, lastly replace the +a*b/c into +y so that it becomes 1+y+2. – B. Liew Jun 29 '16 at 21:08

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.

• Thanks for pointing out the bad practices which I have done in the code given above. – B. Liew Jun 29 '16 at 20:03

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);
long i=0, bitMask=1, sum=0, limit=268435456;
long stack[aTot], sI=0;
for (long bits=0;bits<limit;++bits)
{
stack=a;
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;
}
}
sum=0;
for (i=0;i<sI;++i)
sum+=stack[i];
if (sum==72)
{
std::cout << a;
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];
}
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.

• This is almost what I'm looking for currently! But there is a lot of formulas you missed. The possible formulas not only can do a*b-c*d+e , it can even be a*b-c*d*e or a+b/c*d*e. Which the stacks of * / can be more than 2 numbers in it. – B. Liew Jul 1 '16 at 9:24
• Step through the code and you'll see it handles multiple */ terms in a row, combining them... – Dave P. Jul 1 '16 at 9:30
• Oh my mistake, it did.. After it gets an answer, then I can permute it and get other same answer with different order (the order of each * / sets will still permute inside their own sets). But actually the a*b-c*d and a*c-b*dis different, how do I get the second answer without permute all 15! which will get duplicated answers and also not efficient. – B. Liew Jul 1 '16 at 10:09
• You shouldn't have a problem - aside from 75, there are no identical numbers, so most of the permutations should be fine. Since you only have 200 secs, I doubt you'll be able to get through many, anyways. – Dave P. Jul 1 '16 at 10:53
• And if you want to permutate the answer you already have, just remember operator precedence, so a X b can be rearranged to b X a, but a/b can't become b/a - group the terms you can't rearrange into groups, and permutate that. In fact, if you took each group and make it a string, you could permutate the array of strings, and just print them out, w/o any more calculations... – Dave P. Jul 1 '16 at 11:00