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
and5-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 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;
}
cont = true; break;
could be simplified tocontinue loop;
, adding aloop:
before your innerdo ... while
, and removing theif (cont) continue;
statement. \$\endgroup\$