Calculate 24, A Childhood Game in a C++ way

• Download source - 1 Kb

Background

It all started with a favorite game of playing cards since my childhood: Calculating 24. The rule is simple: pick any 4 cards, and try to get a result of 24 from the numbers on the cards, only with the 4 basic arithmetic operations, namely, addition (+), subtraction (-), multiplication (*) and division (/). Jack (J), Queen (Q), King (K) and Ace (A) represent 11, 12, 13 and 1 respectively, or they all represent 1 in an alternative flavor.

For example, given numbers 3, 3, 4 and 8, we can get such an expression: 3*8*(4-3) = 24.

A more general mathematic description of this game would be: given a vector of any length and a set of calculation methods, what is the complete set of calculation results?

Algorithm

The computer way to play this game is to:

1. get all possible permutations of 4 numbers,
2. calculate all possible arithmetic results for each permutation, and then
3. judge whether 24 is within the result set.

Step 2 is the core of the algorithm.

Let's assume a sorted permutation from step 1 is expressed as A1, A2, A3, ..., An.

Define F as F (An) = A1 (op) A2 (op)A3, ... An-1 (op) An, where (op) is addition (+), subtraction (-), multiplication (*) or division (/), reverse subtraction or reverse division.

It's natural that F (An) = F (An-1) (op) An. This is where a recursive function shows its power.

Implementation

With the power of STL and BOOST, things can easily be done. The code is so short that it can all be be pasted below:

#include <iostream>
#include <vector>       // for vector
#include <set>          // for set
#include <algorithm>    // for for_each(), next_permutation(), prev_permutation()

#include <boost/bind.hpp>           // for boost::bind
#include <boost/assign.hpp>         // for vector += assignment
#include <boost/lambda/lambda.hpp>  // for boost::lambda::_1 
#include <boost/lambda/if.hpp>      // for boost::lambda::if_ 

using namespace std;

template<typename T>
class CCalculate
{
public:
    CCalculate(const vector<T>& v):m_v(v)
    {
    };

    set<T> operator() () 
    {
        RecursiveCalculate();
        return m_setNextSum;
    }

private:
    vector<T> m_v;
    set<T> m_setPrevSum, m_setNextSum;

private:
    void BasicCalculation(T d1, T d2)
    {
        m_setNextSum.insert(d1 - d2);
        m_setNextSum.insert(d1 * d2);
        m_setNextSum.insert(d2 - d1);
        if(0 != d2) m_setNextSum.insert(d1 / d2);
        if(0 != d1) m_setNextSum.insert(d2 / d1);
    }

    void RecursiveCalculate(void)
    {
        if(m_v.size() > 2)
        {
            T v_back;
            v_back = m_v.back();
            m_v.pop_back();

            RecursiveCalculate();
            swap(m_setPrevSum, m_setNextSum);
            m_setNextSum.clear();

            for_each(m_setPrevSum.begin(),
                m_setPrevSum.end(),
                boost::bind(&CCalculate<T>::BasicCalculation, 
                this, 
                _1, 
                v_back));
        }
        else
        {
            m_setNextSum.clear();
            BasicCalculation(m_v.front(), m_v.back() );
        }
    };
};

void PrintResult(vector<double> v)
{
    using boost::lambda::_1;
    using boost::lambda::if_;
    using boost::lambda::constant;  

    set<double> setFinalVal;
    setFinalVal =  CCalculate<double>(v)();

    cout<<"current vector is: [ ";
    for_each( v.begin(), v.end(), cout<<_1<<" " );
    cout<<"]\n";

    cout<<"Corresponding Results are:{ ";
    for_each( setFinalVal.begin(), setFinalVal.end(),
        ( cout<<_1<<" ", if_((_1 < 24.000001) && 
        (_1 > 23.999999))[ cout <<constant("Bingo:<")
        << _1<<" found here.> "])  );

    cout<<"}\n\n";
}

int main()
{
    cout<<"build on "<<__DATE__<<" "
        <<__TIME__<<endl;

    using namespace boost::assign;
    vector<double> vTest;
    
    vTest += 3,3,8,8;

    sort(vTest.begin(), vTest.end());
    do{
        PrintResult(vTest);
    } while ( next_permutation( vTest.begin(), vTest.end()));

    return 0;
}

References

1. Free peer-reviewed portable C++ source libraries.