Exercices S04 – Solutions possibles

Ce qui suit donne quelques solutions possibles aux exercices proposés à la séance S04. Vous aurez peut-être même trouvé mieux, qui sait?

Problème de trouver_consecutifs(debut,fin,n)

Consigne :

• Écrivez l'algorithme trouver_consecutifs(debut,fin,n) qui retournera un itérateur sur le début de la première séquence de n éléments consécutifs de même valeur dans la séquence $[debut,fin)$.
  • Cet algorithme retournera fin si aucune telle séquence n'existe, ou encore si $n \le 0$

Solution possible : une solution « manuelle » possible à ce problème serait ce qui suit.

template <class It>
   It trouver_consecutifs(It debut, It fin, int n) {
      if (debut == fin || n <= 0) return fin;
      It base = debut;
      int m = 1;
      for (++debut; debut != fin; ++debut) {
         ++m;
         if (*debut != *base) {
            base = debut;
            m = 1;
         } else if (m == n) {
            return base;
         }
      }
      return m != n? fin : base;
   }

Solution possible : une solution possible à ce problème, ayant recours à des algorithmes standards serait ce qui suit.

#include <algorithm>
#include <iterator>
template <class It>
   It trouver_consecutifs(It debut, It fin, int n) {
      using namespace std;
      if (debut == fin || n <= 0) return fin;
      auto base = debut;
      auto term = find_if(next(base), fin, [=](auto val) {
         return *base != val;
      });
      while (term != fin && distance(base, term) < n) {
         base = term;
         term = find_if(next(base), fin, [=](auto val) {
            return *base != val;
         });
      }
      return distance(base, term) < n? fin : base;
   }

J'ai utilisé deux λ identiques dans la même fonction. Il aurait été tentant alléger l'écriture (et probablement le code généré) en déposant la λ dans une variable temporaire avant de l'utiliser, mais ceci aurait posé problème ici du fait de la capture par copie de base à la construction de la λ qui doit prendre une valeur distincte à chaque construction.

Notez que la version manuelle, en s'arrêtant dès que n éléments ont été comptés, sera peut-être un peu plus rapide en pratique que celle utilisant des algorithmes standards (implémentée de manière un peu naïve, il faut le dire).

Problème de plus_longue_sequence(debut,fin)

Consigne :

• Écrivez l'algorithme plus_longue_sequence(debut,fin), qui retournera une paire (voir std::pair et std::make_pair()) dont le premier élément sera un itérateur sur le début de la plus longue séquence de valeurs consécutives trouvée dans la séquence $[debut,fin)$ , et le second élément sera un itérateur sur la fin de cette « sous-séquence ».
  • Veillez à ce que la paire d'itérateurs retournée forme une séquence à demi-ouverte.
  • Si la séquence $[debut,fin)$ est vide, alors retournez une paire fin,fin. Si plusieurs séquences distinctes ont la même (plus longue) longueur, alors retournez une paire d'itérateurs sur la première d'entre elles.
  • Vous pouvez vous aider en écrivant des algorithmes auxiliaires.
  • Vous avez le droit d'utiliser std::distance()

Solution possible : une solution « manuelle » possible à ce problème serait ce qui suit.

#include <utility>
template <class It>
   auto plus_longue_sequence(It debut, It fin) {
      using namespace std;
      auto res = pair{ fin, fin };
      if (debut == fin) return res;
      auto pos = debut;
      int meilleur = 0, n = 1;
      for (++debut; debut != fin; ++debut)
         if (*pos == *debut) {
            ++n;
         } else {
            if (n > meilleur) {
               meilleur = n;
               res = { pos, debut };
            }
            n = 1;
            pos = debut;
         }
      return n > meilleur ? pair{ pos, fin } : res;
   }

Solution possible : une solution possible à ce problème, ayant recours à des algorithmes standards serait ce qui suit.

#include <utility>
#include <algorithm>
template <class It>
   auto plus_longue_sequence(It debut, It fin) {
      using namespace std;
      auto res = pair{ fin, fin };
      while(debut != fin) {
         auto pos = find_if(next(debut), fin, [=](auto val) {
            return val != *debut;
         });
         if (distance(debut, pos) > distance(res.first, res.second))
            res = { debut, pos };
         debut = pos;
      }
      return res;
   }

Vous remarquerez sans doute que cette solution est significativement plus simple que la solution « manuelle », et elle pourrait encore être allégée.

Problème de plus_longue_sequence(debut,fin,pred)

Consigne :

• Écrivez l'algorithme plus_longue_sequence(debut,fin,pred), qui retournera une paire (voir std::pair et std::make_pair()) dont le premier élément sera un itérateur sur le début de la plus longue séquence de valeurs consécutives respectant le prédicat pred trouvée dans la séquence $[debut,fin)$ , et le second élément sera un itérateur sur la fin de cette « sous-séquence ».
  • Veillez à ce que la paire d'itérateurs retournée forme une séquence à demi-ouverte.
  • Si la séquence $[debut,fin)$ est vide, alors retournez une paire fin,fin.
  • Si plusieurs séquences distinctes ont la même (plus longue) longueur, alors retournez une paire d'itérateurs sur la première d'entre elles.
  • Vous pouvez vous aider en écrivant des algorithmes auxiliaires.
  • Vous avez le droit d'utiliser std::distance()

Solution possible : une solution « manuelle » possible à ce problème serait ce qui suit.

#include <algorithm>
#include <iterator>
#include <utility>
template <class It, class Pred>
   auto plus_longue_sequence(It debut, It fin, Pred pred) {
      using namespace std;
      auto res = pair{ fin, fin };
      if (debut == fin) return res;
      for (; debut != fin && !pred(*debut); ++debut)
         ;
      while (debut != fin) {
         auto pos = debut;
         for (; debut != fin && pred(*debut); ++debut)
            ;
         if (distance(res.first, res.second) < distance(pos, debut))
            res = { pos, debut };
         for (; debut != fin && !pred(*debut); ++debut)
            ;
      }
      return res;
   }

Cette solution n'a recours à aucun algorithme standard. La logique de cet algorithme, grossièrement, est :

• Trouver le premier élément de la séquence pour lequel le prédicat s'avère, puis
• Jusqu'à ce ce la séquence soit épuisée, trouver le dernier élément de la séquence courante pour laquelle le prédicat s'avère, conserver les extrémités de cette séquence s'il s'agit de la plus longue jusqu'ici, et
• Trouver le début de la prochaine séquence pertinente

La redondance de code est un indice que nous pourrions simplifier le tout. Notez que les appels répétés à std::distance() pourraient être optimisés par le recours à une variable temporaire.

Solution possible : une solution possible à ce problème, ayant recours à des algorithmes standards serait ce qui suit.

#include <algorithm>
#include <iterator>
#include <utility>
template <class It, class Pred>
   auto plus_longue_sequence(It debut, It fin, Pred pred) {
      using namespace std;
      auto res = pair{ fin,fin };
      for (debut = find_if(debut, fin, pred); debut != fin; debut = find_if(debut, fin, pred)) {
         auto term = find_if_not(debut, fin, pred);
         if (distance(res.first, res.second) < distance(debut, term))
            res = { debut, term };
         debut = term;
      }
      return res;
   }

Ce code va à l'essentiel, en utilisant les algorithmes std::find_if() et std::find_if_not() qui font tout le travail de recherche d'un début et d'une fin de séquence pour nous.

Problème de inverser_mots(s)

Consigne :

• Écrivez l'algorithme inverser_mots(s) qui retourne une chaîne de la même taille que s, mais dont le contenu est l'inverse de l'ordre des mots dans la chaîne s sans toutefois modifier l'ordre et la taille des séquences de blancs dans s.
  • Par exemple :
    • si s est " j'aime   mon prof  ", alors la fonction retournera " prof   mon j'aime  "
    • si s est "yo", alors la fonction retournera "yo"
    • si s est "     yo man", alors la fonction retournera "     man yo"
    • si s est "yo  man", alors la fonction retournera "man  yo"

Solution laborieuse : une solution laborieuse, parce qu'un peu manuelle, mais qui fonctionnerait bien serait la suivante.

#include <algorithm>
#include <iostream>
#include <vector>
#include <cassert>
#include <string>
#include <locale>
using namespace std;
string inverser_mots(const string &s) {
   if (s.empty()) return s;
   vector<string> blancs, mots;
   auto loc = locale{ "" };
   bool debute_par_blanc = isspace(s.front(), loc);
   auto debut = find_if(begin(s), end(s), [&loc](char c) { return !isspace(c, loc); });
   if (debut != begin(s))
      blancs.emplace_back(begin(s), debut);
   while (debut != end(s)) {
      auto fin = find_if(debut, end(s), [&loc](char c) { return isspace(c, loc); });
      mots.emplace_back(debut, fin);
      debut = find_if(fin, end(s), [&loc](char c) { return !isspace(c, loc); });
      if (debut != fin)
         blancs.emplace_back(fin, debut);
   }
   reverse(begin(mots), end(mots));
   if (!debute_par_blanc)
      blancs.swap(mots);
   string resultat;
   auto q = begin(mots);
   for (auto p = begin(blancs); p != end(blancs); ++p) {
      resultat += *p;
      if (q != end(mots)) {
         resultat += *q;
         ++q;
      }
   }
   return resultat;
}

Cette solution ressemble, sur le plan structurel, à plus_longue_sequence(debut,fin,pred), du fait qu'elle alterne entre les sous-séquences qui respectent un critère (les blancs consécutifs) et celles qui respectent un autre critère (les non-blancs consécutifs). Elle en diffère toutefois du fait qu'elle conserve les sous-séquences dans deux conteneurs (nommés blancs et mots, mais ce sont des noms discutables), pour éventuellement inverser l'ordre des mots mais pas l'ordre des séquences de blancs.

Pour fusionner les sous-séquences en fin de parcours, l'algorithme retient si le texte dans s débutait par un blanc, puis permute les séquences de manière à ce que celle qui se nomme blancs contienne en fait la sorte de séquence qui débutait s initialement. Ensuite, la construction de la chaîne resultat se fait en alternant des sous-séquences de chacun des deux conteneurs.

Raffinement : remarquez que nous utilisons un même algorithme, std::find_if(), et deux λ pour identifier les blancs et les non-blancs. Ceci nous amène à écrire du code semblable mais un peu redondant. En associant l'une des λ à une variable (ici : est_blanc) et en alternant entre les algorithmes std::find_if() et std::find_if_not(), nous pouvons clarifier quelque peu notre démarche, et alléger l'écriture.

#include <algorithm>
#include <iostream>
#include <vector>
#include <cassert>
#include <string>
#include <locale>
using namespace std;
string inverser_mots(const string &s) {
   if (s.empty()) return s;
   vector<string> blancs, mots;
   auto loc = locale{ "" };
   auto est_blanc = [&loc](char c) { return isspace(c, loc); };
   bool debute_par_blanc = est_blanc(s.front());
   auto debut = find_if_not(begin(s), end(s), est_blanc);
   if (debut != begin(s))
      blancs.emplace_back(begin(s), debut);
   while (debut != end(s)) {
      auto fin = find_if(debut, end(s), est_blanc);
      mots.emplace_back(debut, fin);
      debut = find_if_not(fin, end(s), est_blanc);
      if (debut != fin)
         blancs.emplace_back(fin, debut);
   }
   reverse(begin(mots), end(mots));
   if (!debute_par_blanc)
      blancs.swap(mots);
   string resultat;
   auto q = begin(mots);
   for (auto p = begin(blancs); p != end(blancs); ++p) {
      resultat += *p;
      if (q != end(mots)) {
         resultat += *q;
         ++q;
      }
   }
   return resultat;
}

Raffinement : bien que cela ne semble pas simplifier le code à première vue, il est possible de séparer le code de fusion des deux vecteurs et de le placer dans une fonction à part entiere, ou encore dans une λ comme c'est le cas ici.

#include <algorithm>
#include <iostream>
#include <vector>
#include <cassert>
#include <string>
#include <locale>
using namespace std;
string inverser_mots(const string &s) {
   if (s.empty()) return s;
   vector<string> blancs, mots;
   auto loc = locale{ "" };
   auto est_blanc = [&loc](char c) { return isspace(c, loc); };
   bool debute_par_blanc = est_blanc(s.front());
   auto debut = find_if_not(begin(s), end(s), est_blanc);
   if (debut != begin(s))
      blancs.emplace_back(begin(s), debut);
   while (debut != end(s)) {
      auto fin = find_if(debut, end(s), est_blanc);
      mots.emplace_back(debut, fin);
      debut = find_if_not(fin, end(s), est_blanc);
      if (debut != fin)
         blancs.emplace_back(fin, debut);
   }
   reverse(begin(mots), end(mots));
   auto fusion = [](const vector<string> &v0, const vector<string> &v1) {
      string resultat;
      auto q = begin(v1);
      for (auto &str : v0) {
         resultat += str;
         if (q != end(v1)) {
            resultat += *q;
            ++q;
         }
      }
      return resultat;
   };
   return debute_par_blanc? fusion(blancs, mots) : fusion(mots, blancs);
}

Si nous faisons de fusion un algorithme générique à part entière, il devient possible de l'exprimer ainsi.

template<class T, class ItA, class ItB>
   T fusion(ItA da, ItA fa, ItB db, ItB fb, T resultat) { // fusionne à la fin de resultat
      for(; da != fa; ++da) {
         resultat += *da;
         if (db != fb) {
            resultat += *db;
            ++db;
         }
      }
      return resultat;
   }

J'ai utilisé ItA et ItB pour le type des itérateurs (on pourrait vouloir fusionner des éléments d'un vector<string> avec ceux d'une list<string> après tout), da et fa pour « début de la séquence A » et « fin de la séquence A » respectivement (idem pour la séquence B), et le type T pour permettre au code client de suppléer un type de retour.

J'utilise le paramètre resultat comme valeur initiale pour cumuler les éléments à fusionner (dans notre cas, ce devrait être une string vide).

 Notez que je triche un peu en présumant que l'ajout à la fin d'une séquence puisse se faire avec l'opérateur += de resultat; ce tronçon mériterait d'être raffiné, mais fonctionne bien si T est string. Il existe une solution pas si mal à ce problème, mais je vous laisse y réfléchir.

Avec ce changement, notre algorithme devient comme suit.

#include <algorithm>
#include <iostream>
#include <vector>
#include <cassert>
#include <string>
#include <locale>
using namespace std;
string inverser_mots(const string &s) {
   if (s.empty()) return s;
   vector<string> blancs, mots;
   auto loc = locale{ "" };
   auto est_blanc = [&loc](char c) { return isspace(c, loc); };
   bool debute_par_blanc = est_blanc(s.front());
   auto debut = find_if_not(begin(s), end(s), est_blanc);
   if (debut != begin(s))
      blancs.emplace_back(begin(s), debut);
   while (debut != end(s)) {
      auto fin = find_if(debut, end(s), est_blanc);
      mots.emplace_back(debut, fin);
      debut = find_if_not(fin, end(s), est_blanc);
      if (debut != fin)
         blancs.emplace_back(fin, debut);
   }
   reverse(begin(mots), end(mots));
   return debute_par_blanc?
      fusion(begin(blancs), end(blancs), begin(mots), end(mots), string{}) :
      fusion(begin(mots), end(mots), begin(blancs), end(blancs), string{});
}

Raffinement : on peut simplifier encore plus le tout en constatant que la distinction que nous faisons ici entre mots et blancs est artificielle, à ceci près que l'on doit se souvenir si s débutait ou non par un blanc pour s'assurer de n'inverser que l'ordre des mots (pas celui des blancs). Je vais tricher un peu ici en faisant quelques constats simplificateurs mais qui demandent des explications :

• Sachant qu'il n'y a que deux cas possibles, nous pouvons remplacer les deux vecteurs distincts par un tableau de deux vecteurs
• Sachant que l'on alternera entre trouver une séquence de blancs et trouver une séquence de non-blancs, nous pouvons chaque fois examiner si le premier symbole d'une séquence est blanc ou non, et chercher des symboles qui sont de même nature
• Lorsque le moment d'inverser l'ordre des mots, il faudra s'assurer d'inverser l'ordre des éléments du bon vecteur
• Outre ce détail, nous n'avons plus vraiment à distinguer mots et blancs, puisque la chaîne qui nous servira de résultat fusionnera les deux vecteurs dans l'ordre où ils auront été générés, peu importe lequel

Une implémentation possible serait alors la suivante.

#include <algorithm>
#include <iostream>
#include <vector>
#include <cassert>
#include <string>
#include <locale>
using namespace std;
string inverser_mots(const string &s) {
   if (s.empty()) return s;
   vector<string> v[2];
   int cur = 0;
   auto loc = locale{ "" };
   auto est_blanc = [&loc](char c) { return isspace(c, loc); };
   bool debute_par_blanc = est_blanc(s.front());
   for (auto debut = begin(s); debut != end(s);) {
      auto fin = est_blanc(*debut) ? find_if_not(debut, end(s), est_blanc) : find_if(debut, end(s), est_blanc);
      v[cur].emplace_back(debut, fin);
      cur = cur? 0 : 1;
      debut = fin;
   }
   cur = static_cast<int>(debute_par_blanc);
   reverse(begin(v[cur]), end(v[cur]));
   return fusion(begin(v[0]), end(v[0]), begin(v[1]), end(v[1]), string{});
}

Notre acceptation du fait que l'on puisse faire abstraction du concept de « est un mot » et le remplacer par « est de même nature que le premier caractère de la séquence » nous permet une économie significative d'effort et de complexité.

Raffinement : remarquez enfin que l'on n'a pas vraiment besoin de séparer la recherche de la fin de la séquence en l'utilisation de deux algorithmes distincts. Il est en effet possible de ramener le tout à « chercher le premier élément de la séquence qui n'ait pas la même caractéristique que le premier d'entre eux ». On aurait alors ce qui suit.

#include <algorithm>
#include <iostream>
#include <vector>
#include <cassert>
#include <string>
#include <locale>
using namespace std;
string inverser_mots(const string &s) {
   if (s.empty()) return s;
   vector<string> v[2];
   int cur = 0;
   auto loc = locale{ "" };
   auto est_blanc = [&loc](char c) { return isspace(c, loc); };
   bool debute_par_blanc = est_blanc(s.front());
   for (auto debut = begin(s); debut != end(s);) {
      const bool etalon = est_blanc(*debut);
      auto fin = find_if(next(debut), end(s), [=](char c) { return est_blanc(c) != etalon; });
      v[cur].emplace_back(debut, fin);
      cur = cur? 0 : 1;
      debut = fin;
   }
   cur = static_cast<int>(debute_par_blanc);
   reverse(begin(v[cur]), end(v[cur]));
   return fusion(begin(v[0]), end(v[0]), begin(v[1]), end(v[1]), string{});
}

Pouvez-vous faire encore mieux?

Problème de inverser_lettres(s)

Consigne :

• Écrivez l'algorithme inverser_lettres(s) qui retourne une chaîne de la même taille que s, mais dont le contenu est tel que seul l'ordre des symboles dans chacun des mots est inversé.
  • Par exemple :
    • si s est " j'aime   mon prof  ", alors la fonction retournera " emia'j   nom forp  "
    • si s est "yo", alors la fonction retournera "oy"
    • si s est "     yo man", alors la fonction retournera "     oy nam"
    • si s est "yo  man", alors la fonction retournera "oy  nam"

Solution possible : ce problème, pourtant semblable au précédent, admet une solution naïve relativement simple.

#include <string>
#include <locale>
#include <algorithm>
std::string inverser_lettres(std::string s) {
   using namespace std;
   auto loc = locale{ "" };
   auto debut = find_if(begin(s), end(s), [&loc](char c) { return !isspace(c, loc); });
   while (debut != end(s)) {
      auto fin = find_if(debut, end(s), [&loc](char c) { return isspace(c, loc); });
      reverse(debut, fin);
      debut = find_if(fin, end(s), [&loc](char c) { return !isspace(c, loc); });
   }
   return s;
}

Il est en effet facile ici de passer la chaîne reçue en paramètre par copie, et de travailler à l'intérieur de celle-ci plutôt que de travailler avec des conteneurs intermédiaires. Une fois les extrémités d'un mot trouvés, on peut simplement inverser la sous-chaîne correspondante.

Raffinement : on peut bien sûr se limiter à une seule λ et alterner entre std::find_if() et std::find_if_not(), comme précédemment. En remplaçant la répétitive while par un for pour contraindre la portée de debut, on en arrive à ce qui suit.

#include <string>
#include <locale>
#include <algorithm>
std::string inverser_lettres(std::string s) {
   using namespace std;
   auto loc = locale{ "" };
   auto est_blanc = [&loc](char c) { return isspace(c, loc); };
   for (auto debut = find_if_not(begin(s), end(s), est_blanc); debut != end(s);) {
      auto fin = find_if(debut, end(s), est_blanc);
      reverse(debut, fin);
      debut = find_if_not(fin, end(s), est_blanc);
   }
   return s;
}

C'est déjà pas mal, n'est-ce pas?

Problème de ltrim(s)

Consigne :

• Écrivez l'algorithme ltrim(s) (pour Left Trim) qui retourne une chaîne de caractères équivalente à s, mais dont toutes les séquences de blancs au début auront été supprimées.
  • Par exemple :
    • si s est " j'aime   mon prof  ", alors la fonction retournera "j'aime   mon prof  "
    • si s est "j'aime   mon prof  ", alors la fonction retournera "j'aime   mon prof  "
    • si s est " x ", alors la fonction retournera "x "
    • si s est "   ", alors la fonction retournera ""
    • si s est "", alors la fonction retournera ""

Solution possible : une solution possible à ce problème serait la suivante.

std::string ltrim(const std::string &s) {
   using namespace std;
   return { find_if(begin(s), end(s), [loc = locale{ "" }](char c) { return !isspace(c, loc); }, end(s) };
}

Problème de rtrim(s)

Consigne :

• Écrivez l'algorithme rtrim(s) (pour Right Trim) qui retourne une chaîne de caractères équivalente à s, mais dont toutes les séquences de blancs à la fin auront été supprimées.
  • Par exemple :
    • si s est " j'aime   mon prof  ", alors la fonction retournera " j'aime   mon prof"
    • si s est " j'aime   mon prof", alors la fonction retournera "j'aime   mon prof  "
    • si s est " x ", alors la fonction retournera " x"
    • si s est "   ", alors la fonction retournera ""
    • si s est "", alors la fonction retournera ""

Solution possible : une solution possible à ce problème serait la suivante.

std::string rtrim(const std::string &s) {
   using namespace std;
   auto pos = find_if(rbegin(s), rend(s), [loc = locale{ "" }](char c) { return !isspace(c, loc); });
   return { begin(s) + distance(rbegin(s), pos), end(s) };
}

Problème de trim(s)

Consigne :

• Écrivez l'algorithme trim(s) qui retourne une chaîne de caractères équivalente à s, mais dont toutes les séquences de blancs au début et à la fin auront été supprimées.
  • Par exemple :
    • si s est " j'aime   mon prof  ", alors la fonction retournera "j'aime   mon prof"
    • si s est " j'aime   mon prof", alors la fonction retournera "j'aime   mon prof"
    • si s est " x ", alors la fonction retournera "x"
    • si s est "   ", alors la fonction retournera ""
    • si s est "", alors la fonction retournera ""

Solution possible : une solution possible à ce problème serait la suivante.

std::string trim(const std::string &s) {
   return ltrim(rtrim(s));
}

Problème de elaguer_blancs(s)

Consigne :

• Écrivez l'algorithme elaguer_blancs(s) qui retourne une chaîne de caractères équivalente à s, mais dont toutes les séquences de blancs seront remplacées par un seul caractère d'espacement.
  • Par exemple :
    • si s est " j'aime   mon prof  ", alors la fonction retournera " j'aime mon prof "
    • si s est "j'aime   mon prof", alors la fonction retournera "j'aime mon prof"
    • si s est "   ", alors la fonction retournera " "
    • si s est " ", alors la fonction retournera " "
    • si s est "", alors la fonction retournera ""

Solution possible : une solution possible à ce problème serait la suivante.

//
// Votre code va ici, ou dans un .h que vous inclurez
//
#include <cassert>
int main() {
   assert(elaguer_blancs(" j'aime   mon prof  ") == " j'aime mon prof ");
   assert(elaguer_blancs("   ") == " ");
   assert(elaguer_blancs(" ") == " ");
   assert(elaguer_blancs("") == "");
}

Autre angle d'approche

Pour un autre angle d'approche, on pourrait pousser un peu l'analyse de ces quelques problèmes et constater qu'ils ont certains points en commun. Je vous invite donc à relire brièvement les consignes qui vous ont été données lors de la séance S04...

...en regardant tout cela de plus près, il me semble apparent que certaines opérations réapparaîtront à plusieurs reprises dans le code :

• Chercher une sous-séquence dans une séquence, car nous chercherons :
  • des séquences de valeurs consécutives identiques au sens de ==
  • des séquences de valeurs consécutives identiques au sens d'un certain prédicat
  • des séquences de blancs consécutifs
  • des séquences de non-blancs consécutifs
• Des petits prédicats, comme est_blanc ou est_non_blanc par exemple
  • ...mais, en y pensant bien, est_blanc et est_non_blanc, c'est la même chose à une négation logique près, n'est-ce pas?

Dans ma démarche de solution personnelle, j'y suis allé de manière graduelle :

• J'ai écrit une fonction qui trouve une sous-séquence d'éléments consécutive de même valeur, et je l'ai testée
• J'ai écrit une fonction qui trouve une sous-séquence d'éléments consécutive respectant un même prédicat, et je l'ai testée. Évidemment, elle ressemblait à la précédente
• J'ai modifié la première fonction pour l'exprimer en termes de la deuxième, en remplaçant le test sur == par un prédicat qui fait ce test, pour ne pas avoir deux fonctions distinctes à entretenir
• Ensuite, j'ai écrit les fonctions à rédiger, une à une, en rédigeant chaque fois le code de test en même temps que la fonction à tester. Chaque fois, j'ai écrit une fonction naïve qui fait le travail, puis j'ai réfléchi aux parties qui me semblaient correspondre à des algorithmes, ou qui me semblaient pouvoir s'exprimer comme des fonctions à part entière. J'ai découpé et redécoupé en conséquence. Ce que vous verrez donc ci-dessous n'est pas le premier jet de ma réflexion, mais j'ai essayé de laisser des indications sur les étapes intermédiaires que j'ai franchi pour y arriver.

Dans certains cas, je pourrais aller plus loin, mais je ne suis pas certain que cela aiderait à la lisibilité.

Programme principal

#include <algorithm>
#include <utility>
#include <ostream>
#include <string>
#include <vector>
#include <locale>
#include <tuple>
#include <numeric>
//
// outils divers...
//
// fonction à écrire...
//
// code de test...
//
#include <iostream>
int main() {
   using namespace std;
   int vals[] { 1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 5, 6, 6 };
   for (int i = 0; i < 6; ++i)
      tester_trouver_consecutifs(begin(vals), end(vals), i, cout);
   tester_plus_longue_sequence(begin(vals), end(vals), cout);
   tester_plus_longue_sequence(
      begin(vals), end(vals), [](int n) {
         return n % 2 != 0;
      }, "entiers impairs", cout
   );
   string tests[] {
      "   j'aime mon   prof! ", "j'aime mon prof!", "",
      j'aime mon   prof! ", "   j'aime mon   prof!", "x"
   };
   tester_inverser_mots(begin(tests), end(tests), cout);
   tester_inverser_lettres(begin(tests), end(tests), cout);
}

Fonctions de tests

template <class It>
   void tester_trouver_consecutifs(It debut, It fin, int n, std::ostream &os) {
      using namespace std;
      afficher_sequence(debut, fin, os);
      os << '\n';
      if (auto pos = trouver_consecutifs(debut, fin, n); pos == fin)
         os << "Pas de sous-sequence de longueur " << n
            << " dans cette sequence\n" << endl;
      else
         os << "La 1re sous-sequence de longueur " << n
            << " dans cette sequence debute a la position "
            << distance(debut, pos) << '\n' << endl;
   }

template <class It>
   void tester_plus_longue_sequence(It debut, It fin, std::ostream &os) {
      using namespace std;
      if (auto [d,f] = plus_longue_sequence(debut, fin); d == f)
         os << "La sequence est vide\n";
      else {
         os << "La plus longue sequence est de longueur "
            << distance(d, f) << " et contient ";
         afficher_sequence(res.first, res.second, os);
         os << '\n';
      }
      os << endl;
   }

template <class It, class Pred>
   void tester_plus_longue_sequence
      (It debut, It fin, Pred pred, const std::string &nom_predicat, std::ostream &os) {
      using namespace std;
      if (auto [d,f] = plus_longue_sequence(debut, fin, pred); d == f)
         os << "La sequence est vide\n";
      else {
         os << "La plus longue sequence de " << nom_predicat
            << " est de longueur " << distance(d, f)
            << " et contient ";
         afficher_sequence(d, f, os);
         os << '\n';
      }
      os << endl;
   }

template <class It>
   void tester_inverser_mots(It debut, It fin, std::ostream &os) {
      using namespace std;
      for_each(debut, fin, [&os](const string &s) {
         os << "Avant : \"" << s << "\"\nApres : \"" << inverser_mots(s) << "\"\n" << endl;
      });
   }

template <class It>
   void tester_inverser_lettres(It debut, It fin, std::ostream &os) {
      using namespace std;
      for_each(debut, fin, [&os](const string &s) {
         os << "Avant : \"" << s << "\"\nApres : \"" << inverser_lettres(s) << "\"\n" << endl;
      });
   }

Algorithmes à écrire

L'approche que j'ai pris pour chacun des algorithmes qui devaient être écrits va comme suit.

template <class It>
   It trouver_consecutifs(It debut, It fin, int n) {
      using namespace std;
      if (debut == fin || n <= 0) return fin;
      for (auto p = consecutifs(debut, fin); p.second != fin; debut = p.second, p = consecutifs(debut, fin))
         if (distance(p.first, p.second) >= n)
            return p.first;
      return fin;
   }

template <class It>
   auto plus_longue_sequence(It debut, It fin) {
      using namespace std;
      auto res = pair{ fin, fin };
      for (auto p = consecutifs(debut, fin); p.second != fin; debut = p.second, p = consecutifs(debut, fin))
         if (distance(p.first, p.second) >= distance(res.first, res.second))
            res = p;
      return res;
   }

template <class It, class Pred>
   auto plus_longue_sequence(It debut, It fin, Pred pred) {
      using namespace std;
      auto res = pair{ fin, fin };
      auto p = consecutifs(debut, fin, pred);
      for (; debut = p.second, p = consecutifs(debut, fin, negation_logique(pred)), p.second != fin;
           debut = p.second, p = consecutifs(debut, fin, pred))
         if (distance(p.first, p.second) >= distance(res.first, res.second))
            res = p;
      if (distance(p.first, p.second) >= distance(res.first, res.second))
         res = p;
      return res;
   }

template <class It, class Pred>
   auto separer_sous_sequences(It debut, It fin, Pred pred) {
      using namespace std;
      vector<pair<It, It>> oui, non;
      for (bool use_neg = pred(*debut); debut != fin; use_neg = !use_neg)
         if (use_neg) {
            auto [d,f] = consecutifs(debut, fin, negation_logique(pred));
            oui.emplace_back(debut, f);
            debut = f;
         } else {
            auto [d,f] = consecutifs(debut, fin, pred);
            non.emplace_back(debut, f);
            debut = f;
         }
      return pair{ oui, non };
   }

std::string inverser_mots(const std::string &s) {
   using namespace std;
   using It = string::iterator;
   if (s.empty()) return s;
   const auto &loc = locale{ "" };
   auto [blancs, mots] = separer_sous_sequences(begin(s), end(s), est_blanc(loc));
   reverse(begin(mots), end(mots));
   auto v = isspace(s.front(), loc) ?
      fusionner_alternance(std::move(blancs), std::move(mots)) :
      fusionner_alternance(std::move(mots), std::move(blancs));
   return accumulate(begin(v), end(v), string{}, [](const string &s, auto &&p) {
      return s + string(p.first, p.second);
   });
}

std::string inverser_lettres(std::string s) {
   using namespace std;
   using It = string::iterator;
   if (s.empty()) return s;
   const auto &loc = locale{ "" };
   auto [blancs, mots] = separer_sous_sequences(begin(s), end(s), est_blanc(loc));
   for(auto & [d,f] : mots)
      reverse(d, f);
   auto v = isspace(s.front(), loc) ?
      fusionner_alternance(std::move(blancs), std::move(mots)) :
      fusionner_alternance(std::move(mots), std::move(blancs));
   return accumulate(begin(v), end(v), string{}, [](const string &s, auto &&p) {
      return s + string(p.first, p.second);
   });
}

Outils construits en cours de route

Ce qui suit montre des outils construits au fur et à mesure de ma progression à travers les exercices proposés.

template <class It, class Pred>
   std::pair<It, It> consecutifs(It debut, It fin, Pred pred) {
      return { debut, std::find_if(debut, fin, pred) };
   }

template <class It>
   std::pair<It, It> consecutifs(It debut, It fin) {
      return debut == fin?
                std::pair{ debut,fin } :
                consecutifs(debut, fin, [x = *debut](auto val) { return val != x; });
   }

template <class Pred>
   class negation_logique_ {
      Pred pred;
   public:
      negation_logique_(Pred pred) : pred{ pred } {
      }
      template <class T>
         bool operator()(const T &arg) {
            return !pred(arg);
         }
   };
template <class Pred>
   negation_logique_<Pred> negation_logique(Pred pred) {
      return { pred };
   }

template<class Pred>
   auto negation_logique(Pred pred) {
      return [=](const auto &arg) { return !pred(arg);  };
   }

auto est_blanc(const std::locale &loc) {
   return [&loc](char c) { return std::isspace(c, loc); };
}

template <class It>
   void afficher_sequence(It debut, It fin, std::ostream &os) {
      using namespace std;
      if (debut == fin) return;
      os << *debut;
      for_each(next(debut), fin, [&os](auto val) { os << ' ' << val; });
   }

//
// precondition: premier.size() >= second.size()
//
template <class T, class R = T>
   R fusionner_alternance(T premier, T second) {
      using namespace std;
      R res;
      for (auto p = begin(premier), q = begin(second); p != end(premier); ++p) {
         res.insert(end(res), *p);
         if (q != end(second)) {
            res.insert(end(res), *q);
            ++q;
         }
      }
      return res;
   }

#include <iostream>
#include <string>
#include <vector>
#include <cassert>
#include <iterator>
#include <utility>
#include <locale>
#include <algorithm>
using namespace std;

template <class T>
   void inverser_elements(vector<T> &v) {
      for (T &elem : v)
         reverse(begin(elem), end(elem));
   }

string fusionner(vector<string> v0, vector<string> v1) {
   string res;
   for (auto i0 = begin(v0), i1 = begin(v1);
        i0 != end(v0) && i1 != end(v1); ++i0, ++i1)
      res += *i0 + *i1;
   if (v0.size() > v1.size()) res += v0.back();
   return res;
}

template <class Pred>
   auto separer(string s, Pred pred) {
      vector<string> v[2]; // oui, non
      if (s.empty()) return pair{ v[0], v[1] };
      bool oui = pred(s.front());
      int n = 0;
      for (auto p = begin(s); p != end(s); oui = !oui) {
         auto q = oui ? find_if_not(p, end(s), pred) : find_if(p, end(s), pred);
         v[n].emplace_back(p, q);
         p = q;
         n = n ? 0 : 1;
      }
      return pair{ v[0], v[1] };
   }

string inverser_mots(string s) {
   auto est_blanc = [loc = locale{ "" }](char c){ return isspace(c, loc); };
   auto [v0, v1] = separer(std::move(s), est_blanc);
   inverser_elements(!v0.empty() && !est_blanc(v0.front()[0])? v0 : v1);
   return fusionner(std::move(v0), std::move(v1));
}

int main() {
   cout << '\"' << inverser_mots("") << '\"' << endl;
   cout << '\"' << inverser_mots(" j'aime mon prof ") << '\"' << endl;
   cout << '\"' << inverser_mots("j'aime mon prof ") << '\"' << endl;
   cout << '\"' << inverser_mots(" j'aime mon prof") << '\"' << endl;
   cout << '\"' << inverser_mots("j'aime mon prof") << '\"' << endl;
}