GotW #41

Home Blog Talks Books & Articles Training & Consulting

On the
blog		 RSS feed November 4: Other Concurrency Sessions at PDC
November 3: PDC'09: Tutorial & Panel		 October 26: Hoare on Testing
October 23: Deprecating export Considered for ISO C++0x

This is the original GotW problem and solution substantially as posted to Usenet. See the book More Exceptional C++ (Addison-Wesley, 2002) for the most current solution to this GotW issue. The solutions in the book have been revised and expanded since their initial appearance in GotW. The book versions also incorporate corrections, new material, and conformance to the final ANSI/ISO C++ standard.

Using the Standard Library
Difficulty: 9 / 10

How well do you know the standard library's algorithms? This puzzle requires a "master mind."

Problem

1. Write a program that plays simplified Mastermind, using only Standard Library containers, algorithms and streams. The challenge is to use as few "if"s, "while"s, "for"s and other builtin constructs as possible, and have the program take up as few statements as possible.

Simplified Rules Summary

To start the game, the program randomly chooses a string of four pegs in some internal order. Each peg can be one of three colours: red (R), green (G) or blue (B). For example, the program might pick "RRBB" or "GGGG" or "BGRG".

The player makes successive guesses until he figures out the order. For each guess, the program tells the player two numbers: the first is the number of pegs that are the correct colour (independent of order); and the second is the number of pegs with the correct colour AND the correct location.

Here is an example session, where the program chose the combination "RRBB":

guess--> rbrr
3 1

guess--> rbgg
2 1

guess--> bbrr
4 0

guess--> rrbb
4 4 - solved!

(A more complex form of this puzzle was proposed by Tom Holaday at the November 1997 meeting: To write a program that plays the full advanced Mastermind, using only one expression. It kept half a dozen committee members amused for hours during the evenings.)

Solution

1. Write a program that plays simplified Mastermind, using only Standard Library containers, algorithms and streams. The challenge is to use as few "if"s, "while"s, "for"s and other builtin constructs as possible, and have the program take up as few statements as possible.

The solution presented below is not the only right answer. In fact, it may not even be the cleanest, and it's relatively unimaginative. Each of the solutions that were posted to the newsgroup have aspects that I like better (such as creative use of count<> and inner_product<>) and aspects that I don't (such as randomizing the combination poorly and hardcoding the peg colours within the algorithm). All of the solutions, including this one, do insufficient error checking.

This solution avoids hardcoding peg-colour and combination-size restrictions within the algorithm; peg colours can be extended simply by changing the 'colors' string, and the combination length can be changed simply by changing the '4' literal. It does use one "while," however, which can replaced (at further cost of clarity) by "find_if( istream_iterator<string>(cin), ... );".

  string colors("BGR"), comb(4, '.'), l(comb), guess;

  typedef map<int,int> M;

  struct Color {
    Color( M& cm, M& gm, int& color )
      : cm_(cm), gm_(gm), color_(color=0) { }
    void operator()( char c )
      { color_ += min( cm_[c], gm_[c] ); }
    M &cm_, &gm_;
    int& color_;
  };

  struct Count {
    Count( int& color, int& exact )
      : color_(color), exact_(exact=0) { }
    char operator()( char c, char g )
      { return ++cm_[c], ++gm_[toupper(g)], 
               exact_ += c == toupper(g), '.'; }
   ~Count()
      { for_each( colors.begin(), colors.end(),
                  Color( cm_, gm_, color_ ) ); }
    M cm_, gm_;
    int &color_, &exact_;
  };

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

  int main() {
    int color, exact = 0;
    srand( time(0) ),
      generate( comb.begin(), comb.end(), ChoosePeg );
    while( exact < comb.length() ) {
      cout << "\n\nguess--> ", cin >> guess;
      transform( comb.begin(), comb.end(),
                 guess.begin(), l.begin(),
                 Count( color, exact ) );
      cout << color << ' ' << exact;
    }
    cout << " - solved!\n";
  }

Copyright © 2009 Herb Sutter