Solution

I l @ ve RuBoard

The solutions presented here are not the only right answers. Both are nicely extensible to additional colors and pegs, because they avoid hardcoding peg- color and combination- size restrictions within the algorithm. Peg colors can be extended simply by changing the colors string; the combination length can be changed directly by changing the length of the comb string. On the downside, both solutions do insufficient error checking.

One of the requirements of the problem was to minimize the number of statements, so wherever possible these solutions use a comma instead of a semicolon as a statement separator. Most of us aren't used to seeing so many commas in C or C++ code, but it's possible to use commas in more places than one might at first think. Another requirement was to avoid the built-in control keywords, so for our purposes the ternary ? : operator will understudy for if / else .

Solution #1

The idea of the first solution is to evaluate each guess by making only a single pass through the guess string input by the player. This first solution does still use one while . In the second solution, we'll replace it with find_if (although at some further cost of clarity).

To see the basic structure of this code, let's start with the mainline:

 typedef map<int,int> M; int main() {   const string colors("BGR");   // possible colors   string comb(4, '.'),          // combination          guess;                  //  current guess 

Extending this program to handle more colors, or more pegs per combination, is easy: To change the colors, change colors . To make the guess length longer or shorter, make comb longer or shorter.

 int cok, pok = 0;           // right color & place M cm, gm;                   // helper structures 

We need a string to hold the combination to be found, and another to hold the guess. The rest are working data used to process each guess.

The first thing we need to do is to generate the combination:

 srand( time(0) ), generate( comb.begin(), comb.end(),           ChoosePeg( colors ) ); 

After seeding the built-in random number generator, we use the standard library's generate() facility to make up a combination. Here generate() uses a function object of type ChoosePeg to generate a combination by invoking ChoosePeg 's function call operator, operator()() , once for each peg position to determine the color at that position. We'll see how ChoosePeg works later on.

Now all we need is the main loop, to print prompts and process guesses:

 while( pok < comb.size() )   cout << "\n\nguess--> ",    cin >> guess,    guess.resize( comb.size(), ' ' ), 

We do some basic input-error handling. If the player's guess is too long, the guess is truncated; if it's too short, it's padded with spaces. Padding short guesses lets the player cheat by simply trying one-letter guesses until he or she finds the right letter, then two-letter guesses to find the second letter, and so on to incrementally guess the solution. This code doesn't bother to prevent that.

Next , we need to clear our working area and process the guess:

 cm = gm = M(), 

We have to process the guess in two ways: First, we determine the number of pegs that are the right color and in the right place ( pok , or "place okay"). Separately, we determine the number of pegs that are the right color but not necessarily in the right location ( cok , or just "color okay"). To avoid making two passes through the guess, we first use transform() to process the two ranges and let the CountPlace function object accumulate information about how many pegs of each color appear in the combination and in the guess:

 transform( comb.begin(), comb.end(),            guess.begin(), guess.begin(),            CountPlace( cm, gm, pok ) ), 

The standard library's transform() algorithm operates on two input ranges ”here, the combination and guess strings viewed as sequences of characters . Now, transform() actually does more than we need; it can also generate output, and we don't care about the output. The easiest way to ignore the output is to make sure the supplied CountPlace function object doesn't actually change anything and then put the output back into the guess string, which is thus a no-op.

Note that the CountPlace function object also populates our cm and gm maps, in addition to its primary purpose of calculating pok . These helper maps are then used in the second phase, where the for_each loop loops through the colors (not the guess) and counts how many pegs of each color will match:

 for_each ( colors.begin(), colors.end(),            CountColor( cm, gm, cok ) ), 

The for_each() algorithm is probably the best-known algorithm in the standard library. All it does is iterate over a range and apply the supplied function object to each element in the range. In this case, the CountColor object is responsible for counting and then totaling how many pegs of each color match up in the two strings.

Having done all the work to process the guess, we report our results:

 cout << cok << ' ' << pok; 

Note that no braces are needed around the while loop's body because the whole body is one statement, thanks to all those commas.

Finally, when the loop ends, we're done:

 cout << " - solved!\n"; } 

Having seen how the whole program is intended to work, let's take a look at the three helper function objects.

ChoosePeg

The simplest of the helpers is ChoosePeg , which is used to generate the combination:

 class ChoosePeg { public:   ChoosePeg( const string& colors )     : colors_(colors) { }   char operator()() const     { return colors_[rand() % colors_.size()]; } private:   const string& colors_; }; 

Each invocation of operator()() generates another peg's color.

If it weren't for the fact that ChoosePeg remembers a reference to the string of valid colors, it could be a plain function. We could have made colors a global string and polluted the global namespace. This solution prefers avoiding global data and making ChoosePeg better encapsulated rather than making the colors string global and having ChoosePeg depend on knowledge of the global data.

CountPlace

Next, CountPlace is responsible for calculating pok , the number of pegs that are the right color and in the right place. It's also responsible for populating statistical information about the guess and combination strings for later tallying by CountColor .

 class CountPlace { public:   CountPlace( M& cm, M& gm, int& pok )     : cm_(cm), gm_(gm), pok_(pok=0) { }   char operator()( char c, char g )   {     return ++cm_[c],            ++gm_[g],            pok_ += (c == g),            g;   } private:   M &cm_, &gm_;   int& pok_; }; 

Each invocation of operator()() compares one of the combination's pegs, c , with the corresponding peg from the guess, g . If they're equal, we increment pok_ . Now the purpose of the maps is clearer. Each map stores the number of pegs of a given color (the color's char value converted to an int ) appearing in the given string.

Because of transform() 's semantics, operator()() has to return some char . It doesn't really matter what we return because, although the output is directed back into the guess string, the guess string won't be used again. For simplicity and general cleanliness, though, we just return the guess's peg color so that the guess string remains unmodified.

CountColor

Finally, CountColor is responsible for calculating cok , using the statistical information generated by CountPlace . It does so in the obvious way: For each possible color, it adds the number of matching pegs regardless of location, which is to say the minimum of the number of pegs of that color in the combination and in the guess.

 class CountColor { public:   CountColor( M& cm, M& gm, int& cok )     : cm_(cm), gm_(gm), cok_(cok=0) { }   void operator()( char c ) const     { cok_ += min( cm_[c], gm_[c] ); } private:   M &cm_, &gm_;   int& cok_; }; 

Summary

Putting it all together into a complete program, we get the following:

 #include <iostream> #include <algorithm> #include <map> #include <string> #include <ctime> #include <cstdlib> using namespace std; typedef map<int,int> M; class ChoosePeg { public:   ChoosePeg( const string& colors )     : colors_(colors) { }   char operator()() const     { return colors_[rand() % colors_.size()]; } private:   const string& colors_; }; class CountPlace { public:   CountPlace( M& cm, M& gm, int& pok )     : cm_(cm), gm_(gm), pok_(pok=0) { }   char operator()( char c, char g )   {     return ++cm_[c],            ++gm_[g],            pok_ += (c == g),            g;   } private:   M &cm_, &gm_;   int& pok_; }; class CountColor { public:   CountColor( M& cm, M& gm, int& cok )     : cm_(cm), gm_(gm), cok_(cok=0) { }   void operator()( char c ) const     { cok_ += min( cm_[c], gm_[c] ); } private:   M &cm_, &gm_; int& cok_; }; int main() {   const string colors("BGR"); // possible colors   string comb(4, '.'),        // combination          guess;               // current guess   int cok, pok = 0;           // right color & place   M cm, gm;                   // helper structures   srand( time(0) ),    generate( comb.begin(), comb.end(),              ChoosePeg( colors ) );   while( pok < comb.size() )     cout << "\n\nguess--> ",      cin >> guess,      guess.resize( comb.size(),' '),      cm = gm = M(),      transform( comb.begin(), comb.end(),                 guess.begin(), guess.begin(),                 CountPlace( cm, gm, pok ) ),      for_each ( colors.begin(), colors.end(),                 CountColor( cm, gm, cok ) ),      cout << cok << ' '<< pok;   cout << " - solved!\n"; } 

Solution #2

The idea of the second solution is to make the mainline dead simple by simply saying "find the combination in the input." Here's the mainline:

 int main() {   srand( time(0) ),    find_if( istream_iterator<string>(cin),             istream_iterator<string>(),             Combination() ); } 

That's it. The Combination predicate has to do all the work.

Combination

Clearly, we expect that Combination 's default constructor will invent a combination:

 class Combination { public:   Combination()     : comb_(4, '.')   {     generate( comb_.begin(), comb_.end(), ChoosePeg ),      Prompt();   } 

Note that this ChoosePeg() is different from the one in the first solution; more on that in a moment. After generating the combination, the constructor emits the first prompt, and that's all it needs to do.

Next, Combination::operator()() will compare each input guess string with the combination and return true if it matches the combination, and false otherwise :

 bool operator()( string guess ) const // one round {   int cok, pok;   // right color & place   return      guess.resize( comb_.size(), '  '), 

Again, we do some basic error handling by adjusting the size of the guess , if necessary.

The major work will, again, be done in two stages. The difference is that this time the two states are reversed , and we don't bother limiting ourselves to just one pass through the input. First, we determine cok , the number of pegs that are the right color but may or may not be in the right place:

 cok = accumulate( colors.begin(), colors.end(),                   ColorMatch( 0, &comb_, &guess ),                   ColorMatch::Count ), 

We'll look at the ColorMatch helper in a moment.

Phase 2 is to calculate pok , the number of pegs with the right color and position. To do this, we're going to use what may seem like an inappropriate algorithm:

 pok = inner_product( comb_.begin(), comb_.end(),                      guess.begin(), 0,                      plus<int>(),                      equal_to<char>() ), 

We're not performing mathematical matrix calculations here, so why use inner_product() ? The short answer is, because it's there.

The longer answer is that it's the algorithm whose behavior is the closest to what's wanted. The inner_product() algorithm:

• Takes two input ranges

• Performs a specified operation (let's call it op2 ) on the two first elements of the ranges, then Son the two second elements of the ranges, and so on; and

• Performs another specified operator (let's call it op1 ) to combine the results.

It happens that the defaults for op1 and op2, respectively, are addition and multiplication. But what we want is only slightly different. For op1, addition is fine, and we just want op2 to return 1 if the two characters are equal, and otherwise, which happens to be what you get when you use equality comparison   la equal_to<char> and let the resulting bool promote to an int .

If the name inner_product() still worries you, think of this standard algorithm as a kind of m lange of accumulate() , which counts things in a single input range, and transform() , which processes two input ranges, with a dash of flexibility to customize what to do with the elements from the two ranges. A mathematical inner product calculation is a special case of the same description, but the inner_product() algorithm is specified more generally and can adapt to different ways of combining and tallying input sequences, as we've just seen.

 cout << cok <<'   '<< pok,      (pok == comb_.size())        ? (cout << " - solved!\n", true)        : (Prompt(), false); } 

Finally, the operator also generates the user interface, including guess feedback and the subsequent prompt or completion message.

When it comes to nonstatic data members , we need only the obvious one:

 private:   string comb_;  // actual combination 

That's it for the nonstatic members. The rest of Combination's members are static:

 static char ChoosePeg() { return colors[rand() % colors.size()]; } 

Note that because of the changed encapsulation ”with the colors string in the same scope as ChoosePeg() ”we can simplify ChoosePeg() and make it just a stateless function.

 static void Prompt()    { cout << "\n\nguess--> "; }   static const string colors;       // possible colors }; const string Combination::colors = "BGR"; 

Since Combination is now the only class that needs to know about the possible colors and the length of guesses, we can nicely hide that information by tucking it away inside Combination 's scope.

ColorMatch

The only thing we still need is a ColorMatch function object. Remember, it is intended to be used like this:

  cok = accumulate( colors.begin(), colors.end(),   ColorMatch( 0, &comb_, &guess ),   ColorMatch::Count ),  

There are a couple of wrinkles here. Note that ColorMatch is actually the type of value being accumulated . For one thing, this means that accumulate() will return the final ColorMatch value, whereas we're looking for an int . That's pretty easy ”we'll just provide a conversion to int :

 class ColorMatch { public:   ColorMatch( int i, const string* s1, const string* s2 )     : cok_(i), s1_(s1), s2_(s2) { }   operator int() const { return cok_; } 

Now, when we use accumulate() as above, instead of adding plain values such as int s, we'll be Count() -ing using ColorMatch objects. That is, for each char in colors , accumulate() will apply the function ColorMatch::Count() , which takes a ColorMatch value representing the tally so far and the next colors character to process:

 static ColorMatch Count( ColorMatch& cm, char c ) {   return     ColorMatch(       cm.cok_ +         min( count( cm.s1_->begin(), cm.s1_->end(), c ),              count( cm.s2_->begin(), cm.s2_->end(), c ) ),       cm.s1_, cm.s2_ ); } 

Count() 's job is to figure out how many pegs of color c exist in both strings (although not necessarily in the same positions ), and add that to the current ColorMatch tally. It does this by simply using another standard algorithm, count() , to determine the number of pegs with color c in each string, and adding the lower number. Count() then returns a new ColorMatch object that contains the new tally. Because Count() will be called once for each possible color, the final ColorMatch object's cok_ value will be exactly the number we want: the number of pegs with the right color but not necessarily in the right place.

Finally, the function object keeps some private state:

 private:   int cok_;   const string *s1_, *s2_; }; 

Summary

Again, putting it all together into a complete program makes it easier to see how the various parts fit and coexist:

 #include <iostream> #include <algorithm> #include <numeric> #include <functional> #include <string> #include <ctime> #include <cstdlib> using namespace std; class ColorMatch { public:   ColorMatch( int i, const string* s1, const string* s2 )     : cok_(i), s1_(s1), s2_(s2) { }   operator int() const { return cok_; }   static ColorMatch Count( ColorMatch& cm, char c )   {     return       ColorMatch(         cm.cok_ +           min( count( cm.s1_->begin(), cm.s1_->end(), c ),                count( cm.s2_->begin(), cm.s2_->end(), c ) ),         cm.s1_, cm.s2_ );   } private:   int cok_;   const string *s1_, *s2_; }; class Combination { public:   Combination()     : comb_(4, '.')   {     generate( comb_.begin(), comb_.end(), ChoosePeg ),      Prompt();   }   bool operator()( string guess ) const // one round   {     int cok, pok;   // right color & place     return        guess.resize( comb_.size(),' '),        cok = accumulate( colors.begin(), colors.end(),                       ColorMatch( 0, &comb_, &guess ),                       ColorMatch::Count ),        pok = inner_product( comb_.begin(), comb_.end(),                             guess.begin(), 0,                             plus<int>(),                             equal_to<char>() ),        cout << cok <<'   '<< pok,        (pok == comb_.size())          ? (cout << " - solved!\n", true)          : (Prompt(), false);   } private:   string comb_;  // actual combination   static char ChoosePeg() { return colors[rand() % colors.size()]; }   static void Prompt()    { cout << "\n\nguess--> "; }   static const string colors;       // possible colors }; const string Combination::colors = "BGR"; int main() {   srand( time(0) ),    find_if( istream_iterator<string>(cin),             istream_iterator<string>(),             Combination() ); } 

Comparing the Solutions

This Item has two purposes. One purpose is to have some fun with some C++ features, so we've enjoyed some creative use of comma operators that should be used rarely, if ever, in real-world production code.

The other purpose, however, and the more serious one, is to get better acquainted with generic programming and with what the C++ standard library has to offer, prepackaged and ready-to-use. Each solution approached this purpose in a different way, with different goals. The main goal shaping Solution 1 was to avoid multiple passes through the input. That's not a performance consideration in this simple program whose runtime is dominated by user input, not by the program's processing, but avoiding multiple passes is a useful technique worth knowing for real-world code. When might you want to avoid multiple passes through data? One common example is when the input data is very large, and multiple passes may be prohibitively expensive if the data is larger than memory and needs to be read from disk twice or more ”clearly, it can be desirable to avoid needless access to slow secondary storage. Another example is when multiple passes might be impossible ”you may get only one chance at the data, such as when the input comes from an input iterator.

The main goal shaping Solution 2 was to have a clean and expressive mainline and better-encapsulated internal code. Although a bit longer than Solution 1, Solution 2 is clearer because it avoids Solution 1's possibly mysterious indirect coordination between the main loop's two phases via helper structures. Those structures aren't needed when we allow two passes through the input data, and so the two passes become distinct instead of interdependent. Therefore, they're easier to understand.

Both solutions have given us some exercise reusing the standard library, and both have demonstrated techniques that can be useful in production code. (But, yes, in production code, I'd stay away from all those commas; those were just for fun.)

I l @ ve RuBoard