13,046,375 members (120,708 online)
alternative version

#### Stats

25.1K views
15 bookmarked
Posted 26 Sep 2005

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

, 26 Sep 2005
 Rate this:
A C++ implementation of a liitle game and its extended mathematic model.

## 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;
}```

## Share

No Biography provided

## You may also be interested in...

 Pro

 First Prev Next
 Boost is ugly Anonymous26-Sep-05 9:50 Anonymous 26-Sep-05 9:50
 Last Visit: 31-Dec-99 18:00     Last Update: 23-Jul-17 10:18 Refresh 1