Game Puzzle - My number

[steph111]

I need help for school. I cin(enter) 6 number and I need a program that the first 5 number combined with basic mathematical operations(+, -, * and /) to get the sixth number.
For example:

entrance:
1 2 3 5 6 45
out:
((6*5) / 2) * (3/1)

[dutch]

I guess you need to go through all the permutations of values, operators, parentheses. For handling the "parentheses", reverse polish notation is probably easier (and translate to infix for output). Then again, there's only a few (15?) ways to place the parentheses so you could maybe hard code that.

[salem c]

How long have you got to finish the exercise?

What other clues has your teacher given you which you haven't told us?

What's your approach going to be
- factorise the target number (the factors of 45 are 1, 3, 5, 9, 15) and then do something?
- brute force try every possible permutation until something matches?

https://en.wikipedia.org/wiki/Reverse_Polish_notation
This means you don't have to worry about parentheses and operator precedence.
So for example, your output could be represented internally as
6 5 * 2 / 3 1 / *
Evaluating an RPN stack is very easy from that point on.

So coupled with http://www.cplusplus.com/reference/algorithm/next_permutation/, perhaps
- permute the array
-- permute "+-/*"
--- generate and evaluate some RPNs

[Grime]

- factorise the target number (the factors of 45 are 1, 3, 5, 9, 15) and then do something?

Would factorizing help?

[salem c]

> Would factorizing help?
I've no idea :)

But it might help to prune the search space somewhat.

For example, take the target value T, apply +-*/ with just one of the numbers, then factorise that.

Eg, 45+3 = 48, which has lots of factors to play with (1, 2, 3, 4, 6, 8, 12, 16, 24, 48).
45 = (6*2)*(5-1)-3

@steph111, is it necessary to always use all 5 numbers to arrive at the 6th?

[Grime]

There's gotta be a better way than to just brute force.. Maybe some kind of approach or mathematical property to get rid of at least a small part of the permutations before hand..

[lastchance]

Anybody want to check the logic here?

(EDITED)
In RPN notation you have 9 sites in which you have to place either a number or an operator (5 numbers, 4 operators).

An operator can't go in the first two locations, but an operator must go in the last location, so that leaves (less than) 6C3 = 20 ways of choosing the 3 other places that you are going to put an operator. (Number of operators must never be greater than or equal to the count of preceding numbers, so some of these will be impossible).

For each of (at most) 20 placings you have 5! = 120 ways of permuting the numbers.

For each of those (at most) 20 x 120 number placings you have 4⁴ = 256 ways of choosing 4 operators (which can repeat).

So, brute force amounts to checking (at most) 20 x 120 x 256 = 614400 RPNs. That's feasible, I think.


If that is correct (somebody please check!) then I think I would start by working out a vector<vector<int>> containing the 120 permutations of 5 numbers, vector<string> containing the 256 assemblies of 4 (possibly repeating) operators and a vector<string> containing the (less than) 20 potential op-num combinations. Then it's a 3-layer nested loop ...

[Grime]

lastchance you're a mathematical wizard!

Is there any way the bruteforce approach can be improved? For example, if the sum of the digits is lesser than the number to be obtained, then there must be at least one + or *. Maybe something with negative numbers too.

[dutch]

I count 14 rpn patterns (did I leave any out?):

    const char *rpn_patterns[] = {
        "ABCDE....",
        "ABCD.E...",
        "ABC.DE...",
        "AB.CDE...",
        "ABCD..E..",
        "ABC.D.E..",
        "AB.CD.E..",
        "ABC..DE..",
        "AB.C.DE..",
        "ABCD...E.",
        "ABC.D..E.",
        "AB.CD..E.",
        "ABC..D.E.",
        "AB.C.D.E."
    };

[lastchance]

That's interesting. This actually finds a different solution

(1 + 2 + 5) * 6 - 3 = 45

In RPN:

1 2 + 5 + 6 * 3 -

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <stack>
using namespace std;

//------------------------------------------------

struct item
{
   bool isOperator = false;
   int op = 0;
   int val = 0;
};

char opSymbol[] = { '+', '-', '*', '/' };
const int Nops = sizeof( opSymbol ) / sizeof( opSymbol[0] );

//------------------------------------------------

vector< vector<int> > allPermutations( int N )             // return all permutations of 0, 1, ..., N-1
{
   vector< vector<int> > result;
   vector<int> one( N );
   iota( one.begin(), one.end(), 0 );

   do
   {
      result.push_back( one );
   } while( next_permutation( one.begin(), one.end() ) );

   return result;
}

//------------------------------------------------

vector< vector<int> > allCollections( int N, int p )       // return all length-N collections of 0, ..., p-1
{                                                          //    (needs improvement!)
   vector< vector<int> > result;
   result.push_back( vector<int>{} );

   for ( int pos = 0; pos < N; pos++ )
   {
      vector< vector<int> > temp = result;
      result.clear();
      for ( auto &v : temp )
      {
         v.push_back( 0 );
         for ( int i = 0; i < p; i++ )
         {
            v[pos] = i;
            result.push_back( v );
         }
      }
   }

   return result;
}

//------------------------------------------------

vector< vector<bool> > allChoices( int N, int r )          // return all choices of r from N
{                                                          //    (needs improvement!)
   vector< vector<bool> > result;
   result.push_back( vector<bool>( N, false ) );
   for ( int choice = 1; choice <= r; choice++ )
   {
      vector< vector<bool> > temp = result;
      result.clear();
      for ( auto &v : temp )
      {
         int lastTrue = N - 1;
         while( lastTrue >= 0 && !v[lastTrue] ) lastTrue--;
         for ( int i = lastTrue + 1; i < N; i++ )
         {
            auto vv = v;
            vv[i] = true;
            result.push_back( vv );
         }
      }
   }
   return result;
}

//------------------------------------------------

bool evaluate( const vector<item> &rpn, int &result )      // work out an rpn expression
{
   stack<int> S;
   result = 0;

   for ( auto &e : rpn )
   {
      if ( e.isOperator )
      {
         if ( S.empty() ) return false;
         int op2 = S.top();   S.pop();
         if ( S.empty() ) return false;
         int op1 = S.top();   S.pop();
         switch( e.op )
         {
            case 0: S.push( op1 + op2 );   break;
            case 1: S.push( op1 - op2 );   break;
            case 2: S.push( op1 * op2 );   break;
            case 3: 
            {
               if ( op2 == 0 ) return false;
               S.push( op1 / op2 );
               break;
            }
         }
      }
      else
      {
         S.push( e.val );
      }
   }
   if ( S.size() != 1 ) return false;

   result = S.top();
   return true;
}

//------------------------------------------------

void output( const vector<item> &rpn )                     // output an rpn expression
{
   for ( auto &e : rpn )
   {
      if ( e.isOperator ) cout << opSymbol[e.op] << " ";
      else                cout << e.val          << " ";
   }
   cout << '\n';
}

//------------------------------------------------

bool test( const vector<int> &V, int target, vector<item> &rpn )               // test numbers in V against target
{
   int N = V.size();
   int rpnLength = 2 * N - 1;

   vector< vector<bool> > operatorPositions = allChoices( rpnLength - 3, N - 2 );
   for ( auto &V : operatorPositions )
   {
      V.insert( V.begin(), 2, false );     // operator can't be in first two positions
      V.push_back( true );                 // operator must be in last position
   }

   vector< vector<int> > perms = allPermutations( N );
   vector< vector<int> > ops   = allCollections ( N - 1, Nops );

   for ( auto &pos : operatorPositions )                   // operator positions loop
   {
      for ( auto &op : ops )                               // operator collection loop
      {
         rpn = vector<item>( rpnLength );
         for ( int i = 0, n = 0; i < rpnLength; i++ )
         {
            if ( pos[i] )
            {
               rpn[i].isOperator = true;
               rpn[i].op = op[n];
               n++;
            }
         }

         for ( auto &perm : perms )                        // number permutation loop
         {
            for ( int i = 0, n = 0; i < rpnLength; i++ )
            {
               if ( !pos[i] )
               {
                  rpn[i].val = V[perm[n]];
                  n++;
               }
            }

            int ans;
            if ( evaluate( rpn, ans ) && ans == target ) return true;
         }
      }
   }

   return false;
}

//------------------------------------------------

int main()
{
   vector<int> V = { 1, 2, 3, 5, 6 };
   int target = 45;
   vector<item> rpn;

   if ( test( V, target, rpn ) ) output( rpn );
   else                          cout << "Impossible\n";
}

[dutch]

Mine came up with yet another:

3 + 6 * (2 + 1 * 5)

[helios]

http://www.cplusplus.com/forum/general/135491/
http://www.cplusplus.com/forum/general/135491/2/#msg725582

[Browni3141]

This is remarkably similar to a PE problem I solved a few days ago.

https://projecteuler.net/problem=259

My strategy was to enumerate all 2^9 = 512 concatenations of numbers and keep them in an array, then enumerate each operation on each pair of adjacent numbers at each depth in a recursive function, recording the result whenever the array condensed to a single integer. I used memoization to avoid some repeated calculations The same strategy could be used here, except there's no concatenation and the numbers can be used in any order, and we only need to find one number, rather than all of them.

At each depth of recursion, there will be n choose 2 pairs of numbers, n = 5-depth. This means the number of orders in which to perform operations is (5 choose 2)*(4 choose 2)*(3 choose 2) = 10*6*3 = 180.

For each operation, there are four operations and two orders of numbers (eg. a-b or b-a). Multiplication and addition are commutative, so that's 6 ways to apply an operation, and we apply an operation four times. 6^4 = 1296.

I get 180*1296 = 233280 ways to brute force the solution. Of course, this could be further reduced by recognizing that some branches of the search are repeated because the order of operations often doesn't result in distinct results. I think it would be easiest to just use memoization to prune these branches, or even just not worry about them since 233280 is a small enough number.

foo(myArray, target):
    if myArray's only element == target:
        output result
    for each (i, j) in myArray:
        for each operation:
            myArray.erase( i, j)
            myArray.insert(i[operation]j)
            foo(myArray, target) 

[lastchance]

All good information. Thank-you.

When I let the code run through all the possibilities (and pruned out the repeats due to * and + being commutative) it actually came up with 1332 distinct solutions!

(Just tried it on @helios' problem and it took considerably longer, even with -O3 optimisation.)

[Browni3141]

lastchance, isn't there an issue in your code with integer division? You are performing operations with integers, but division can result in fractions. The code should allow for intermediate fraction results since they can still eventually resolve to an integer, or the target number could be decimal.

[steph111]

The first 5 number don't need to be the factors of sixth number.
Thank all.

[lastchance]

lastchance, isn't there an issue in your code with integer division?

Yes, but then there is a lack of information in the original question about whether / means integer division or not ... and I didn't feel like writing a fraction class just to solve it.

If anyone feels like including a fraction class then it really only affects the calculations in procedure evaluate(), where int would be replaced by class fraction. I don't have such a class to hand at the moment.

The target number can't be decimal without running into potential problems with comparing floating-point numbers.

[helios]

(Just tried it on @helios' problem and it took considerably longer, even with -O3 optimisation.)

Do they do the same, though? Did you get exactly the same results?

[lastchance]

Did you get exactly the same results?

Well, the one that my code produced first doesn't look like any in that thread, and is also subject to doing an integer division.

If I have to get rational divisions right then I would have to go back and write a fraction class. However, that also leads to a high chance of numerical overflow when a lot of numbers with no common factors are involved.

[steph111]

I copied the code and it don't work for me. The problem is with "iota".
Row 26.
Please help me.