Game Puzzle - My number

[lastchance]

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

Well, you could replace it with the line
for (int i = 0; i < N; i++ ) one[i] = i;

However, if it baulks at that then it probably won't like 'auto' or range-based for-loops either, so you would do well to upgrade your compiler.

[steph111]

This code have a lot of problem. Can you fix it?
And place code here.
Thank you so much.

[helios]

If I have to get rational divisions right then I would have to go back and write a fraction class.

Just use boost::rational.

[steph111]

Can you send me fixed code?

[salem c]

The point about homework is for you to attempt your own solution, to both solidify your learning and demonstrate that you have done so.

Simply running off to teacher with lastchance's code in http://www.cplusplus.com/forum/general/248326/#msg1094552 will do neither of those things.

For one thing, any teacher with any academic integrity would see right through your attempt at cheating, since the code is far beyond what you could have achieved yourself.

[lastchance]

OK Helios, a basic Rational class is now incorporated.

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

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

//=== Rational Class ===

using INT = long long;

INT hcf( INT a, INT b )
{
   INT q = 1;
   while ( b > 0 )
   {
      q = b;
      b = a % q;
      a = q;
   }
   return q;
}

class Rational
{
public:
   INT p;
   INT q;
   Rational( INT p_ = 0, INT q_ = 1 );
   Rational operator + ( Rational r );
   Rational operator - ( Rational r );
   Rational operator * ( Rational r );
   Rational operator / ( Rational r );
};

Rational::Rational( INT p_, INT q_ )
{
   p = p_;
   q = q_;

   INT factor = hcf( abs( p ), abs( q ) );
   p /= factor;
   q /= factor;

   if ( q < 0 )
   {
       p = -p;
       q = -q;
   }
}

Rational Rational::operator + ( Rational r ) { return Rational( p * r.q + q * r.p, q * r.q ); }
Rational Rational::operator - ( Rational r ) { return Rational( p * r.q - q * r.p, q * r.q ); }
Rational Rational::operator * ( Rational r ) { return Rational( p * r.p          , q * r.q ); }
Rational Rational::operator / ( Rational r ) { return Rational( p * r.q          , q * r.p ); }

//==================

struct item
{
   bool isOperator = false;
   int value = 0;
};

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

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

vector< vector<int> > allPermutations( int N )        // 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 )  // all length-N collections of 0, ..., p-1
{
   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 )     // all choices of r from N
{
   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, Rational &result )   // work out an rpn expression
{
   stack<Rational> S;
   result = Rational( 0 );

   for ( auto &e : rpn )
   {
      if ( e.isOperator )
      {
         if ( S.empty() ) return false;
         Rational op2( S.top() );   S.pop();
         if ( S.empty() ) return false;
         Rational op1( S.top() );   S.pop();
         switch( e.value )
         {
            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.p == 0 ) return false;
               S.push( op1 / op2 );
               break;
            }
         }
      }
      else
      {
         S.push( Rational( e.value ) );
      }
   }
   if ( S.size() != 1 ) return false;

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

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

string infix( const vector<item> &rpn )     // convert to infix
{
   stack<Rational> S;
   stack<string> T;
   string element;

   for ( auto &e : rpn )
   {
      if ( e.isOperator )
      {
         Rational op2( S.top() );   S.pop();   string t2( T.top() );   T.pop();
         Rational op1( S.top() );   S.pop();   string t1( T.top() );   T.pop();
         switch( e.value )
         {
            case 0: S.push( op1 + op2 );   element = t1 + " + " + t2;   break;
            case 1: S.push( op1 - op2 );   element = t1 + " - " + t2;   break;
            case 2: S.push( op1 * op2 );   element = t1 + " * " + t2;   break;
            case 3: S.push( op1 / op2 );   element = t1 + " / " + t2;   break;
         }
         element = "( " + element + " )";
         T.push( element );
      }
      else
      {
         S.push( Rational ( e.value ) );
         T.push( to_string( e.value ) );
      }
   }

   string result = T.top();
   return result.substr( 2, result.size() - 4 );
}

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

void output( const vector<item> &rpn )           // output an rpn expression
{
   for ( auto &e : rpn )
   {
      if ( e.isOperator ) cout << opSymbol[e.value] << " ";
      else                cout << e.value           << " ";
   }
   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;


   // Sort out the positions that you can put operators
   vector< vector<bool> > temp = allChoices( rpnLength - 3, N - 2 );
   vector< vector<bool> > operatorPositions;
   for ( auto &V : temp )
   {
      bool ok = true;
      for ( int i = 0, countOps = 0, countNums = 0; i < V.size(); i++ )
      {
         if ( V[i] )
         {
            countOps++;
            if ( countOps >= countNums + 2 )
            {
               ok = false;
               break;
            }
         }
         else
         {
            countNums++;
         }
      }
      if ( ok )
      {
         V.insert( V.begin(), 2, false );     // operator can't be in first two positions
         V.push_back( true );                 // operator must be in last position
         operatorPositions.push_back( V );
      }
   }

   // Sort out the N numbers
   vector< vector<int> > perms = allPermutations( N );

   // Sort out the N - 1 ops
   vector< vector<int> > ops   = allCollections ( N - 1, Nops );


   // Brute force through all available RPNs
   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].value      = op[n];
               n++;
            }
         }

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

            Rational ans;
            if ( evaluate( rpn, ans ) && ans.q == 1 && ans.p == target )
            {
//              output( rpn );
//              cout << infix( rpn ) << '\n';
                return true;
            }
         }
      }
   }

   return false;
}

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

int main()
{
   // Given case
   vector<int> V = { 1, 2, 3, 5, 6 };
   int target = 45;
   // Helios case from earlier thread
// vector<int> V = { 3, 7, 8, 10, 50, 100 };
// int target = 315;

   vector<item> rpn;

   if ( test( V, target, rpn ) )
   { 
      output( rpn );
      cout << infix( rpn ) << '\n';
   }
   else
   {
      cout << "None\n";
   }
}

[steph111]

This code have a lot of problem with INT, he does't recogonize that.
Please fix, if you can.

[helios]

Get a better compiler.

[steph111]

Which one?
I use Dev-C++ program for C++ code, but I have a Code Blocks and I use him sometimes.
On Code Bloks I use classic compiler.

[Ganado]

https://en.cppreference.com/w/cpp/language/type_alias
I would assume both of those IDEs have outdated compilers packed with them. With Code Blocks at least, you can link your own compiler instead of using theirs.
https://stackoverflow.com/questions/5604183/adding-compiler-to-codeblocks

But also, try just addin -std=c++11 or -std=c++0x as an additional compiler flag somewhere in your options/compiler settings menu.

That being said, here's links to some places to download the latest MinGW compiler.
https://mingw-w64.org/doku.php/download
Alternatively: https://nuwen.net/mingw.html (This is the compiler I've downloaded and used for the past 2-3 years).

[lastchance]

You can just try it with the online compiler (cpp.sh), @steph111. It's a little gear wheel icon to the top right of a runnable code sample.

It will also allow you to test the code with previous standards. You will need a minimum of C++11.

I use the mingw-64.org link that @Ganado has given you, as it gives me both c++ and fortran compilers. I don't use any IDE: everything from the command line.

[steph111]

Thank you it's work on cpp.sh.
Thank all so much.

[Grime]

But don't paste that as your homework you will get caught. What if they ask you what a specific part of the code does (oh and they definitely will)?