Writing a C++ version of the algebra game 24

Question

I am trying to write a C++ program that works like the game 24. For those who don't know how it is played, basically you try to find any way that 4 numbers can total 24 through the four algebraic operators of +, -, /, *, and parenthesis.

As an example, say someone inputs 2,3,1,5 ((2+3)*5) - 1 = 24

It was relatively simple to code the function to determine if three numbers can make 24 because of the limited number of positions for parenthesis, but I can not figure how code it efficiently when four variables are entered.

---

I have some permutations working now but I still cannot enumerate all cases because I don't know how to code for the cases where the operations are the same.

Also, what is the easiest way to calculate the RPN? I came across many pages such as this one: http://www.dreamincode.net/forums/index.php?showtopic=15406 but as a beginner, I am not sure how to implement it.

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





bool MakeSum(int num1, int num2, int num3, int num4)
{

  vector<int> vi;
  vi.push_back(num1);
  vi.push_back(num2);
  vi.push_back(num3);
  vi.push_back(num4);

  sort(vi.begin(),vi.end());


  char a1 = '+';
  char a2 = '-';
  char a3 = '*';
  char a4 = '/';
  vector<char> va;
  va.push_back(a1);
  va.push_back(a2);
  va.push_back(a3);
  va.push_back(a4);

  sort(va.begin(),va.end());
  while(next_permutation(vi.begin(),vi.end()))
    {

      while(next_permutation(va.begin(),va.end()))
    {

      cout<<vi[0]<<vi[1]<<vi[2]<<vi[3]<< va[0]<<va[1]<<va[2]<<endl;

      cout<<vi[0]<<vi[1]<<vi[2]<<va[0]<< vi[3]<<va[1]<<va[2]<<endl;

      cout<<vi[0]<<vi[1]<<vi[2]<<va[0]<< va[1]<<vi[3]<<va[2]<<endl;

      cout<<vi[0]<<vi[1]<<va[0]<<vi[2]<< vi[3]<<va[1]<<va[2]<<endl;

      cout<<vi[0]<<vi[1]<<va[0]<<vi[2]<< va[1]<<vi[3]<<va[2]<<endl; 


    }

    }

  return 0;

}

int main()
{

  MakeSum(5,7,2,1);
  return 0;
}

Answer 1

So, the simple way is to permute through all possible combinations. This is slightly tricky, the order of the numbers can be important, and certainly the order of operations is.

One observation is that you are trying to generate all possible expression trees with certain properties. One property is that the tree will always have exactly 4 leaves. This means the tree will also always have exactly 3 internal nodes. There are only 3 possible shapes for such a tree:

  A
 / \
 N  A
   / \      (and the mirror image)
  N   A
     / \
    N   N

  A
 / \
N   A
   / \
  A   N   (and the mirror image)
 / \
N   N

     A
   /` `\
  A     A
 / \   / \
N  N  N  N

In each spot for A you can have any one of the 4 operations. In each spot for N you can have any one of the numbers. But each number can only appear for one N.

Coding this as a brute force search shouldn't be too hard, and I think that after you have things done this way it will become easier to think about optimizations.

For example, + and * are commutative. This means that mirrors that flip the left and right children of those operations will have no effect. It might be possible to cut down searching through all such flips.

Someone else mentioned RPN notation. The trees directly map to this. Here is a list of all possible trees in RPN:

N N N N A A A
N N N A N A A
N N N A A N A
N N A N N A A
N N A N A N A

That's 4*3*2 = 24 possibilities for numbers, 4*4*4 = 64 possibilities for operations, 24 * 64 * 5 = 7680 total possibilities for a given set of 4 numbers. Easily countable and can be evaluated in a tiny fraction of a second on a modern system. Heck, even in basic on my old Atari 8 bit I bet this problem would only take minutes for a given group of 4 numbers.