Click here to Skip to main content
Click here to Skip to main content

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

, 26 Sep 2005
Rate this:
Please Sign up or sign in to vote.
A C++ implementation of a liitle game and its extended mathematic model.

Sample Image

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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Tom Gee
Team Leader
China China
No Biography provided

Comments and Discussions

 
GeneralBoost is ugly PinsussAnonymous26-Sep-05 9:50 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.140821.2 | Last Updated 26 Sep 2005
Article Copyright 2005 by Tom Gee
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid