Le demi-cercle (épisode 21 -- Échantillons)

Exemple d'entrée AAAAAABCCCC 12344

Exemple de sortie 6A1B14C 11123124

Tu étires les bras et croise les mains derrière ta nuque. Audrey se lève et dit « Je vais me faire un café. Je réfléchis mieux quand je bouge. Quelqu’un veut quelque chose? »

Farid et toi dites : « non merci ». Jérémie marmonne une réponse presqu’inaudible. Il est assis à la table de gauche et se concentre sur une feuille A4. Avec un crayon à papier il note des valeurs dans un tableau, entoure certaines valeurs, passe à la ligne, gomme une valeur, recommence.

Farid est en train de coder sur son PC. Il tape sans hésiter quelques lignes de code, puis fait une pause en plissant les yeux devant son écran comme pour se concentrer sur une partie plus ardue du problème.

Tu énumères mentalement une liste de tests possibles qui seraient autant d’étapes dans ta progression pour résoudre cet exercice.

Une entrée à 1 caractère: A donne 1A1 Une entrée à 1 caractère différent : B donne 1B1 Une entrée à 2 caractères différents : CD donne 1CD1 Une entrée à 2 caractères identiques : EE donne 2E Une entrée à 9 caractères identiques : FFFFFFFFF donne 9F Une entrée à 10 caractères identiques : GGGGGGGGGG donne …

Tu demandes : - Pour une séquence de 10 X, on doit répondre 9X 1X ou bien 9X 1X1 ?

Jérémie lève la tête et dit : - C’est dans la spéc’. Tu encodes 9 caractères; ensuite il te reste 1 seul caractère, donc tu dois l’entourer avec des 1.

Audrey se rassoit devant son clavier en disant : - Je me demande si on ne pourrait pas utiliser des expressions régulières…

Tu crées un nouveau fichier source, ouvres un commentaire et entres ta liste de tests. Tu somnoles. C’est un problème amusant mais futile. Tu aurais besoin de faire une sieste, pas de programmer ce truc.

Tu codes le premier test. Tu le fais passer avec une valeur de retour codée en dur. C’est un jeu d’enfant. Tu codes le second test. Tu le fais passer à l’aide d’un if else outrageusement naïf. Tu réaménages le code afin de généraliser la méthode. Tu codes le troisième test. Pour le faire passer, il te faut une boucle à la place du if. Tu codes le quatrième test. Tu le fais passer en insérant un nouveau if au sein de la boucle. Tu codes le cinquième test. Celui-ci passe déjà. Tu codes le sixième test. Tu essaies de le faire passer en ajoutant une nouvelle condition dans la deuxième branche du if qui se trouve au sein de la boucle. Ton test passe, alors tu en profites pour tout de suite gérer le cas où la ligne se termine sur une séquence de caractères uniques. Parfait. Maintenant tu peux ajouter les cas de tests nominaux. C’est une salle vide tapissée de rouge, qui n’est pas plus grande qu’un cagibi. Il y a une lumière miniature suspendue au milieu de cette pièce miniature. En dessous de la lumière, se trouve une table, une chaise. Sur la table, posée au milieu, un sous-main sur lequel on voit trois balles, une bleue, une orange, une violette. Une balle rouge se trouve à un des pieds de la table. Dans le coin gauche de la pièce, il y a une deuxième lumière et une étagère murale vide. Devant l’étagère, une caisse, ouverte, qui semble contenir elle même des dizaines de petites boites. Il y a une troisième lumière dans le coin au fond à droite. À mi-chemin entre la table et ce coin de la pièce, une caisse est renversée, et son contenu — un ensemble de boites encore plus petites — s’étale sous la petite table. On imagine aisément ce qui s’est passé. Le propriétaire de cette caisse voulait la porter, ou la faire glisser vers le coin au fond à droite, sans déplacer ni choquer la table qui se trouve au milieu, mais la caisse s'est renversée en chemin.

Expected 6A1B14C but got 6AB 14C

Tu déclares : - Bon. J'ai besoin d'un café. C'est pas évident, ce truc.

Jérémie est devant son écran maintenant, les sourcils froncés, il entre du code. Il répond sans te regarder : - Mais si…

Audrey, confortablement assise à son bureau, lit un tutoriel sur les expressions régulières. Farid semble absorbé dans ses réflexions. Il scrute son écran tout en titillant sa moustache.

Tu te diriges vers le café.

Quand le caractère que tu lis n'est pas identique au précédent, il faut remettre à zéro le décompte des caractères. Ou bien à 1 ?

Quand le caractère que tu lis est identique au précédent alors qu'avant tu n'étais pas dans un groupe de caractères identiques, alors il faut insérer un 1.

Pourquoi est-ce que mon avant-dernier test ne passe plus ? Il était passé du premier coup quand je l'ai écrit.

Tu reviens à ton poste. Tu demandes : - On est d'accord qu'on peut s'entraider quand même, durant le premier exercice ?

Farid répond : - Ah ! Oui, mais, on est censé finir son propre programme avant, non ?

Audrey annonce : - Bon pour les regexps, c'était peut être une fausse piste en fait…

Soudain, Jérémie s'écrie : - Bam ! J'ai fini ! Mon programme passe sur le juge en ligne. - Déjà ? - La vache. - Fais voir ?

Le téléphone de Jérémie émet un bruit de sirène faite au synthétiseur analogique. Jérémie annonce : - Soixante minutes ! Fin du premier round.

Farid, sans quitter son écran des yeux, s’écrie : - Donne-moi encore cinq minutes !

Cinq minutes plus tard, il annonce : - J’ai fini ! Mon programme passe aussi !

Jérémie te regarde. Tu dis : - Le mien n'est pas terminé.

Audrey dit : - Le mien non plus.

Tu proposes qu'on fasse une revue des quatre programmes, quinze minutes par revue. On commence par celui de Jérémie.

Jérémie : Alors c'est assez simple : on est dans une boucle infinie, et on lit une chaîne caractère par caractère. Audrey : Une boucle infinie ? Jérémie : Je te rassure, on sort de la boucle quand on lit une fin de ligne, en fait. Farid : Ta boucle, elle fait quand même trois pages de code ! Jérémie : C'est parce que je n'ai pas eu le temps de factoriser. Farid : Admettons. Jérémie : Donc, on a deux types de séquences : run-length ou enclosure. À l'entrée de la boucle, on se demande si le caractère est égal ou différent du caractère précédemment lu. S'il est égal, on se demande si on était déjà dans une séquence run-length, et dans ce cas là on se contente d'incrémenter la longueur de la séquence. Sauf si la longueur est déjà de neuf, car dans ce cas là on doit produire la séquence run-length existante en sortie, et recommencer une nouvelle séquence, qui sera, a priori, une enclosure. Si on n'était pas dans une séquence run-lengthAudrey : C'est compliqué, ta solution. Farid : Oui, il y a bien plus simple, en fait. Jérémie : C'est compliqué parce que vous ne me laissez pas terminer. Audrey : Non, c'est compliqué parce que c'est compliqué. Ça demande un certain temps à comprendre, et ton code n'est pas très modulaire, non plus. Jérémie : Au moins, il passe le test. Audrey : Il passe le test, mais si personne ne peut le maintenir ? Jérémie : Bref. Si on n'était pas dans une sequence run-length, il faut s'y mettre. Toi : Qu'est-ce que tu veux dire par il faut s'y mettre ? Jérémie : Il faut en commencer une.

Vous finissez par comprendre le code de Jérémie, non sans avoir pris plusieurs exemples. Farid dit : - Effectivement, c'est astucieux, mais il y a plus simple.

Jérémie répond qu'il demande à voir. Farid prend le clavier du PC qui a le projecteur, charge son code et commence à son tour une explication :

Farid : Alors, plutôt que de faire une boucle compliquée, on fait deux passes par ligne : la première passe trouve tous les groupes de caractères identiques et les range dans une liste de groupes. Ici, vous avez la classe Groupe, avec un champ caractpre et un champ longueur. Jérémie : Une classe pour ça, c'est cher payé. Farid : Mais non. Toi : Et quand le caractère ne se répète pas ? Farid : Dans ce cas on a simplement un groupe de 1. Jérémie : Ah… Audrey : Mais si un groupe fait plus de 9 de long ? Farid : Comme tu vois ici, quand le caractère est le même que le précédent, on est sur le même groupe, donc on augmente la longueur du groupe, et si cette longeur va dépasser 9, alors on recommence un nouveau groupe. Jérémie : OK. Ensuite ? Farid : Une fois qu'on a tous les groupes dans la liste, on parcourt cette liste en se demandant : est-ce que c'est un groupe de longueur supérieure à 1 ? Si oui, on imprime ce groupe. Jérémie : Et sinon, on affiche un 1, et on sait qu'on est dans une séquence de caractères uniques. Farid : Exactement ! Audrey : D'accord. Et quand c'est un groupe de longueur 1 et de caractère 1, on affiche deux fois le 1. Farid : Voilà ! Jérémie : Quand même, il y a deux passes par ligne. Toi : Note que ça ne va pas changer grand chose… Jérémie : Eh bien ça double le temps d'exécution, quand même. Farid : Pas tout à fait… Audrey : Bon, ce n’est pas le sujet. Si on parlait lisibilité, plutôt ? Déjà, ça n’est pas très aéré comme code. Farid : Tu trouves ? Audrey : Oui. Et je trouve aussi que ça manque de bonnes abstractions. Jérémie : Qu'est-ce que tu voudrais comme abstraction sur un problème algorithmique comme ça ? Audrey : Je ne sais pas exactement, mais tel que c'est écrit ce n'est pas auto-portant. Farid : Je peux ajouter des commentaires… Toi : On regarde les autres programmes ? Audrey : Moi je n’ai rien codé, j’ai regardé si des expressions régulières pouvaient faire le travail. Jérémie : Et elles peuvent ? Audrey : Ça dépend des librairies et du standard que tu choisis… Toi : Je n’ai pas terminé, mais j’ai des tests à la TDD. Jérémie : OK. Je propose qu’on fasse ensemble l’exercice de décodage maintenant. Farid : OK, mais si on peut faire un break avant, s’il te plaît.

Vous vous rendez au coin cuisine. Tu aurais aimé que les autres voient tes tests et te disent  ce qu’ils en pensent. Tu compares le code d’XXL sur lequel vous étiez en train de travailler ce matin, au code de l’exercice que vous venez de faire cette après-midi. Tu te demandes comment des personnes aussi différentes dans leur style de programmation peuvent bien se retrouver à travailler le code d’une même application. C’est peut-être la force de ce système que d’absorber toutes les différences, et d’imposer son style ancien, baroque, bariolé, balafré, bricolé. Tu penses : le legacy, ce monument écrasant, qui met tout le monde d’accord.

(à suivre) Episodes Précédents : 1 -- Si le code pouvait parler 2 -- Voir / Avancer 3 -- Communication Breakdown 4 -- Driver / Navigator 5 -- Brown Bag Lunch 6 -- Conseils à emporter 7 -- Crise / Opportunité 8 -- Le Cinquième Étage 9 -- Que faire ? 10 -- Soit... Soit... 11 -- Boîtes et Flêches 12 -- Le prochain Copil 13 -- La Faille 14 -- Poussière 15 -- L'hypothèse et la Règle 16 - Déplacements 17 -- Jouer et ranger 18 -- Arrangements 19 -- Mise au point 20 -- Expérimentation