Calculate 24, A Childhood Game the C++ Way / 算24的C++实现

 This is actually a showcase of the power of the C++ STL library and the BOOST library: Do more while coding less.

 1. Background

It all starts 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.

2. 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 (*) and 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.

3. Implementation

With the power of STL and BOOST, things can easily be done. The code is so short that it can all 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;
}
 4. Result 

A snapshot of the result is showed below(compiled with VC8.0):

 

Advertisements
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: