IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Guru Of the Week n°41 : utiliser la bibliothèque standard

Difficulté : 9 / 10
Est-ce que vous connaissez bien les algorithmes de la bibliothèque standard ? Ce casse-tête nécessite d'être un esprit supérieur(1).


Note de traduction : le code fournit dans cet article présente des problèmes et ne doit pas être utilisé tel quel. Veuillez consulter la discussion sur le forum pour plus de détail.


Retrouvez l'ensemble des Guru of the Week sur la page d'index.

N'hésitez pas à commenter cet article ! 20 commentaires Donner une note à l´article (5)

Article lu   fois.

Les deux auteurs

Profil Pro

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

I. Problème

Écrire un programme qui permet de jouer à un Mastermind simplifié en utilisant les conteneurs, les algorithmes et les flux de la bibliothèque standard. Le défi consiste à utiliser le moins possible les structures if, while et for du langage et en minimisant le nombre de déclarations.

I-A. Résumé des règles simplifiées

Pour commencer le jeu, le programme choisit au hasard une série de quatre pions dans un certain ordre. Chaque pion peut être de l'une des trois couleurs : rouge (R), vert (G) ou bleu (B). Par exemple, le programme pourrait choisir la série « RRBB » ou « GGGG » ou « BGRG ».

Le joueur fait des propositions successivement, jusqu'à ce qu'il trouve la bonne combinaison dans l'ordre. Pour chaque essai, le programme indique au joueur deux nombres : le premier est le nombre de pions qui sont de la bonne couleur (indépendamment de l'ordre) et le second est le nombre de pions avec la bonne couleur et l'emplacement correct.

Voici un exemple de session, où le programme a choisi la combinaison « RRBB » :

 
Sélectionnez
Proposition -> rbrr
3 1
 
Proposition -> rbgg
2 1
 
Proposition -> bbrr
4 0
 
Proposition -> rrbb
4 4 - resolu !

Une forme plus complexe de ce puzzle a été proposée par Tom Holaday à la réunion de novembre 1997 avec une version complète avancée d'un programme de Mastermind, qui n'utilisait qu'une seule expression. Il a amusé une demi-douzaine de membres du comité pendant des heures le soir.

II. Solution

Écrire un programme qui permet de jouer à un Mastermind simplifié en utilisant les conteneurs, les algorithmes et les flux de la bibliothèque standard. Le défi consiste à utiliser le moins possible les structures if, while et for du langage et en minimisant le nombre de déclarations.

La solution présentée ci-dessous n'est pas la seule réponse correcte. En fait, elle n'est peut-être pas la plus propre et elle manque relativement d'imagination. Chacune des solutions qui ont été postées sur le forum de discussion présente des aspects que j'aime plus (comme l'utilisation créative de count et inner_product) et d'autres que je n'aime pas (comme la randomisation de la combinaison des couleurs des pions, mal codée et en dur à l'intérieur de l'algorithme). Toutes les solutions, y compris celle-ci, font une vérification d'erreurs insuffisante.

Cette solution évite la restriction imposée par le codage en dur et permet de modifier facilement la liste de couleurs des pions et la taille de la combinaison dans l'algorithme : la liste des couleurs possibles pour les pions peut être modifiée en changeant simplement la chaîne de caractères colors et la longueur de la combinaison peut être changée simplement en modifiant la valeur 4. Elle utilise cependant un while, qui peut être remplacé (en sacrifiant la clarté du code) par find_if( istream_iterator string (cin), ... );.

 
Sélectionnez
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";
}

III. Remerciements

Cet article est une traduction en français par l'équipe de la rubrique C++ de l'article de Herb Sutter publié sur Guru of the Week. Vous pouvez retrouver cet article dans sa version originale sur le site de Guru of the Week : Using the Standard LibraryUsing the Standard Library.

Merci à Luc Hermitte et à mitkl pour leur relecture technique et à f-leb pour sa relecture orthographique.

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   


Note de traduction : jeu de mots difficilement traduisible en français, où "master mind" signifie littéralement "maître de l'esprit" et fait également allusion au jeu Mastermind.

Copyright © 2009 Herb Sutter. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.