1
\$\begingroup\$

I shuffle a deck of cards(with an equal number of red and black cards) and start dealing them face up. After any card you can say “stop”, at which point I pay you $1 for every red card dealt and you pay me $1 for every black card dealt. What is your optimal strategy, and how much would you pay to play this game ?

I'd be very happy if you could judge the quality of the code.

using namespace std;

int main(int argc, char * const argv[])
{

    BinaryOptionPricing bop;
    int total_number_of_cards;

    sscanf_s(argv[1], "%d", &total_number_of_cards);
    cout << "Total Number of Cards = " << total_number_of_cards << endl;

    bop.set(total_number_of_cards);
    cout << "Value of the game = " << bop.get() << endl;

    return 0;
}

class BinaryOptionPricing
{

private: int red;
private: int black;
private: std::map<std::pair<int, int>, double> Cache;
private: typedef int card;
private: typedef double redValue;
private: typedef double blackValue;
private: typedef double gameValue;

private:
    double value(card red, card black)
    {
        redValue rValue;
        blackValue bValue;
        gameValue maxValue;

        if (0 == red)
            return ((double)black);
        if (0 == black)
            return (0);

        auto searchPair = Cache.find(std::make_pair(red, black));

        if (searchPair != Cache.end())
            return (searchPair->second);

        rValue= ((double)red / (red + black)) * value(red - 1, black);
        bValue = ((double)black / (red + black)) * value(red, black - 1);

        maxValue = std::max((rValue + bValue), (double)(black - red));
        Cache.insert(std::make_pair(make_pair(red, black), maxValue));

        return maxValue;
    }

public:
    double get()
    {
        return value(red, black);
    }

public:
    void set(int totalNumberOfCards)
    {
        this->red = (totalNumberOfCards/2);
        this->black = (totalNumberOfCards / 2);
    }
};
\$\endgroup\$
2
\$\begingroup\$

Your code has many, many stylistic issues. Some of them seem to be idioms you've invented coming from a Java background; some of them may be due to not really understanding how OOP classes work.


using namespace std;

int main(int argc, char * const argv[])
{

    BinaryOptionPricing bop;
  • You're missing a bunch of #include lines.
  • Prefer char * const *argv over char * const argv[] because you don't have to understand array-to-pointer decay to read it.
  • const-qualifying *argv here is incorrect, or at least the compiler is within its rights to reject it. The correct prototype for main is int main(int argc, char **argv) with no consts.
  • using namespace std; is frowned upon in C++; prefer to write out std::vector and so on, since that's what you'll be doing once you enter the workforce (or wherever you end up coming in contact with other programmers).
  • BinaryOptionPricing is undefined at this point. You need to provide the definition of this class before you try to use it.

class BinaryOptionPricing
{

private: int red;
private: int black;
private: std::map<std::pair<int, int>, double> Cache;
private: typedef int card;
private: typedef double redValue;
private: typedef double blackValue;
private: typedef double gameValue;

C++ isn't Java; you don't have to write public static void main and so on. In C++, public: and private: (and protected:) act as a kind of "section header" introducing a whole bunch of public or private (or protected) members at once. You should write the above code as

class BinaryOptionPricing
{
  private:
    int red;
    int black;
    std::map<std::pair<int, int>, double> Cache;

    using card = int;
    using redValue = double;
    using blackValue = double;
    using gameValue = double;

Notice that private: is the default inside a class, so you don't even need the line private: there; I just put it so you'd see how you could do it. Also notice that I'm using the C++11 using syntax for type aliases, instead of the old C/C++03 typedef syntax — the latter is still perfectly legal and supported, but the former syntax is becoming the de facto standard because it supports things like dependent type names and alias templates whereas the typedef syntax is basically an evolutionary dead end in those respects.


I would advise against using the typedef name card to refer to an integer count of cards. You could say cards or cardCount or NumberOfCards instead... but really, there's nothing wrong with using int directly. It saves you some typing, and clearly indicates what's going on in the code (namely, an integer count).


private:
    double value(card red, card black)
    {
        // ...
    }

public:
    double get()
    {
        return value(red, black);
    }

Here is where I say you may be fundamentally misunderstanding how classes work. Your class BinaryOptionPricing already has data members ("member variables") named red and black. You wrote a member function get() that grabs the value of those members and passes them as function parameters to another member function value(). Inside value, whenever you refer to red, you're referring to the function parameter red, which shadows the data member red defined in the class itself. Fortunately for you, the function parameter has the same value as the data member that it's shadowing... well, at least on the initial recursive call... but this is a very awkward way to write code! If you don't want access to your class's data members at all, you should make value(int, int) a static member function:

static double value(int red, int black)
{
    // ...
}

double get() const
{
    return value(this->red, this->black);
}

void set(int totalNumberOfCards)
{
    this->red = (totalNumberOfCards/2);
    this->black = (totalNumberOfCards / 2);
}

This looks like you want a constructor.

explicit BinaryOptionPricing(int totalNumberOfCards) :
    red(totalNumberOfCards/2), black(totalNumberOfCards/2)
{}

Even better, you should consider just not using OOP at all for this problem; there's no reason the member variables red and black really need to exist here. You could just write

double value_of_game(int red, int black)
{
    if (red == 0 || black == 0) return black;
    double total = red + black;
    double result = (red / total) * value_of_game(red-1, black)
                  + (black / total) * value_of_game(red, black-1);
    return std::max<double>(result, black - red);   
}

and it would work just fine, modulo the lack of memoization making it slow.

Notice that you don't need (and shouldn't put) parentheses around your return expressions; that you're overusing explicit cast notation (frowned upon in C++); and that in C++ it is idiomatic to initialize your local variables and then rarely-if-ever change their initial values, rather than defining them uninitialized at the top of the function and then giving their "real" values farther down in the code.


So let's look at your memoization code.

    auto searchPair = Cache.find(std::make_pair(red, black));
    if (searchPair != Cache.end()) {
        return searchPair->second;
    }

    // ...

    Cache.insert(std::make_pair(make_pair(red, black), maxValue));

Good use of C++11 auto to avoid typing out the name of the iterator type! Instead of insert, you could use Pythonesque syntax:

    Cache[make_pair(red, black)] = maxValue;

or even

    Cache[{red, black}] = maxValue;

although the latter is a bit tricksy so don't ask me to explain it. :)


Putting that all together, we get something along the lines of

double value_of_game(int red, int black)
{
    static std::map<std::pair<int,int>, double> cache;
    if (red == 0 || black == 0) return black;
    auto it = cache.find({red, black});
    if (it != cache.end()) return it->second;
    double total = red + black;
    double result = (red / total) * value_of_game(red-1, black)
                + (black / total) * value_of_game(red, black-1);
    result = std::max<double>(result, black - red);
    cache[{red, black}] = result;
    return result;
}

And this is where we might want to reintroduce a "noun" (a class) into our program, because maybe we want the ability to call value_of_game(x,y) from two different threads simultaneously and we don't want race conditions on cache. So we could do

class BinaryOptionPricing {
    std::map<std::pair<int,int>, double> cache;

  public:
    double value_of_game(int red, int black)
    {
        if (red == 0 || black == 0) return black;
        auto it = cache.find({red, black});
        if (it != cache.end()) return it->second;
        double total = red + black;
        double result = (red / total) * value_of_game(red-1, black)
                    + (black / total) * value_of_game(red, black-1);
        result = std::max<double>(result, black - red);
        cache[{red, black}] = result;
        return result;
    }
};

Alternatively we could directly expose the memoization mechanism to the caller:

using value_of_game_cache_t = std::map<std::pair<int,int>, double>;

double value_of_game(int red, int black, value_of_game_cache_t& cache)
{
    if (red == 0 || black == 0) return black;
    auto it = cache.find({red, black});
    if (it != cache.end()) return it->second;
    double total = red + black;
    double result = (red / total) * value_of_game(red-1, black, cache)
                + (black / total) * value_of_game(red, black-1, cache);
    result = std::max<double>(result, black - red);
    cache[{red, black}] = result;
    return result;
}

Notice that the second alternative here is just a very thin refactoring of the first alternative: we've merely renamed BinaryOptionPricing to value_of_game_cache_t and passed it as an explicit function parameter instead of an implicit this parameter.

BinaryOptionPricing bop;
printf("EV is %g\n", bop.value_of_game(26, 26));  // first approach

value_of_game_cache_t bop;
printf("EV is %g\n", value_of_game(26, 26, bop));  // second approach

The advantage of the first (class-based) approach, in this context, is that I could write my call as a one-liner and it would be just as fast and just as thread-safe as the alternative: the best of both worlds.

printf("EV is %g\n", BinaryOptionPricing().value_of_game(26, 26));
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.