On commence…

… donc avec un problème super simple, super bien compris, afin d’axer l’effort sur une bonne exécution du TDD. Le but de l’exercice d’aujourd’hui:

Exprimer un nombre entre 1 et 3999 en chiffres romains.

Avant de commencer, voici comment je comprends le problème, à vue de nez. Les nombres ne sont pas exprimés en chiffres romains de manière fondamentalement différente des suites de chiffres arabes que nous connaissons. La notation romaine sépare les unités, les dizaines, les centaines et les milliers. Ainsi, les règles d’expression des nombres pour une puissance de dix donnée sont complexes, mais elles s’appliquent récursivement, avec des symboles distincts. On peut donc dire, pour tout terme f × 10ⁿ formant le nombre d’intérêt:

• Si f = 0, alors la notation du nombre exclut ce terme. Chaîne vide.
• Si f = 1, 2 ou 3, alors la notation est une séquence de longueur f du symbole U_n: le symbole d’unité pour la nème puissance de 10.
• Si f = 4, alors la notation est U_nM_n, où M_n est le symbole intermédaire pour la nème puissance de 10.
• Si f = 5, 6, 7 ou 8, la notation est M_n suivie d’une séquence de (f - 5) instances du symbole U_n.
• Finalement, pour f = 9, la notation est U_nG_n, où G_n désigne le symbole de groupe pour la nème puissance de 10.

On définit donc les symboles pour utilisés pour décrire chaque terme décomposant le nombre:

Je crois donc qu’une bonne solution au problème des chiffres romains devrait implanter une structure conditionnelle complexe seulement sur les nombres de 0 à 9, puis généraliser la mise en oeuvre de ces règles en employant un ensemble de symboles qui dépend de la puissance de 10.

Infrastructure technique

Comme je désire me concentrer sur l’exécution d’un bon TDD, je vais résoudre ce problème dans un langage avec lequel je suis totalement à l’aise, soit Python 2.7 préinstallé sur mon Mac Book Pro. J’exécute le développement dans mon environnement préféré, soit une fenêtre de terminal qui roule tmux, où j’édite mon programme et mes tests à l’aide de Vim. Pour rédiger et automatiser l’exécution des tests, j’utilise la librairie unittest, incluse avec Python.

Pour suivre le développement

Le lecteur intéressé peut cloner le dépôt Git qui contient ma solution complétée. La suite des commits correspond aux étapes que j’ai suivies dans l’exécution du cycle rouge-vert-refac.

Échafaudage

Je commence par me créer un projet Git, où j’ajoute un répertoire nommé test, qui contiendra les tests unitaires. J’insère aussi le script d’assistance suivant:

   1   #!/bin/bash
   2   python -m unittest discover -s test -p '*.py'

Je mets aussi en place un fichier de configuration de Git pour éviter de considérer dans le contrôle de source les fichiers d’extension pyc, créés par Python lorsqu’il inclut un fichier comme un module.

   1   *.pyc

Ce script exécutera les tests compris dans tous les fichiers Python dans le répertoire test.

Un premier survol

À l’étape du survol, on recense du mieux qu’on peut un ensemble de tests unitaires envisageables en regard de notre compréhension initiale du problème. Ici, le problème est simple: exprimer des nombres en chiffres romains. Il est donc évident que les tests unitaires doivent comparer une représentation en chiffres romains connue à celle calculée.

Devant cette évidence, j’ai carrément omis la rédaction d’un test de guidage. Je m’attends à ce que mes tests unitaires en viennent, à mesure que je progresse, à couvrir tout cas intéressant pour le problème décrit. Donc! Je devrais commencer par représenter les nombres plus simples, puis progresser vers les plus complexes.

Cycle 1: nombres 1 à 3

Rouge

Je démarre en créant mon premier fichier de tests unitaires.

   1   import os.path
   2   import sys
   3   import unittest
   4   
   5   sys.path.append(os.path.join(os.path.dirname(__file__), ".."))
   6   import roman
   7   
   8   
   9   class TestCase(unittest.TestCase):
  10     def check(self, n, roman_rep):
  11       self.assertEqual(roman_rep, roman.to_roman(n))
  12   
  13   class Main(TestCase):
  14     def test_1_3(self):
  15       self.check(1, "I")
  16       self.check(2, "II")
  17       self.check(3, "III")

Par réflexe, j’ai créé une classe TestCase distincte de la classe Main, où j’encode les méthodes de test. À ce stade, il s’agit d’une erreur: je ne sais pas encore si j’aurai plus d’une classe où j’implanterai des tests.

Sinon, j’ai mis en oeuvre une méthode check qui compare la représentation en chiffres romains attendue à celle calculée. Rendu là, mon test ne compile pas: il n’arrive pas à trouver le module roman. Je veux mettre ce module dans le fichier roman.py à la racine du projet. En ce sens, l’énoncé à la ligne 5 ajoute la racine du projet comme répertoire où Python recherchera ses modules. J’ajoute aussi:

   1   def to_roman(n):
   2     return None
   3   
   4   
   5   # EOF

Maintenant, les tests roulent, mais l’unique test échoue sur la première assertion.

Vert

Les nombres 1 à 3 se représentent simplement avec une séquence correspondante de I.

   1   def to_roman(n):
   2     return n * "I"
   3   
   4   
   5   # EOF

Refac

Pas besoin.

Cycle 2: le nombre 5

Rouge

On saute 4 pour le moment, car sa représentation est plus complexe que celle de 5.

  13   class Main(TestCase):
  14   
  15     def test_1_3(self):
  16       self.check(1, "I")
  17       self.check(2, "II")
  18       self.check(3, "III")
  19   
  20     def test_5(self):
  21       self.check(5, "V")
  22   
  23   
  24   # EOF

Vert

Pour le moment, 5 est un cas distinct de 1 à 3.

   2   def to_roman(n):
   3     if n == 5:
   4       return "V"
   5     return n * "I"

Refac

Je n’aime pas la conditionnelle, mais je ne vois pas comment faire autrement pour le moment. Poursuivons.

Cycle 3: 6 à 8

Rouge

Les nombres 6 à 8 combinent simplement la logique de représentation de 5 à celle des nombres 1 à 3.

  23   def test_6_8(self):
  24       self.check(6, "VI")
  25       self.check(7, "VII")
  26       self.check(8, "VIII")

Vert

La solution la plus simple, qui ne modifie pas le code déjà présent, m’apparaît d’ajouter un cas à la structure conditionnelle en place.

   2   def to_roman(n):
   3     if n == 5:
   4       return "V"
   5     if n >= 5:
   6       return "V" + "I" * (n - 5)
   7     return n * "I"

Refac

On voit premièrement que la logique pour la génération d’une séquence de symboles est dupliquée sur les lignes 6 et 7. Extrayons une fonction pour éliminer cette duplication. De plus, il est clair et net que le cas pour 5 et celui pour 6 à 8 peuvent être combinés. Exécutons ces deux refactorisations d’un coup – attention à ceci, mieux vaut le faire en deux étapes.

   1   def roman_units(u):
   2     return u * "I"
   3   
   4   def to_roman(n):
   5     if n >= 5:
   6       return "V" + roman_units(n - 5)
   7     return roman_units(n)

Cycle 4: le nombre 4

Rouge

  17   self.check(2, "II")
  18       self.check(3, "III")
  19   
  20     def test_4(self):
  21       self.check(4, "IV")
  22   
  23     def test_5(self):
  24       self.check(5, "V")

Vert

Un cas de plus.

   4   def to_roman(n):
   5     if n == 4:
   6       return "IV"
   7     if n >= 5:
   8       return "V" + roman_units(n - 5)
   9     return roman_units(n)

Refac

Je ne vois pas comment faire mieux pour le moment.

Cycle 5: le nombre 9

Rouge

C’est le dernier cas qui exclut les dizaines.

  28   self.check(7, "VII")
  29       self.check(8, "VIII")
  30   
  31     def test_9(self):
  32       self.check(9, "IX")
  33   
  34   
  35   # EOF

Vert

   4   def to_roman(n):
   5     if n == 4:
   6       return "IV"
   7     if n == 9:
   8       return "IX"
   9     if n >= 5:
  10       return "V" + roman_units(n - 5)
  11     return roman_units(n)

Refac

Je n’aime pas beaucoup la structure conditionnelle complexe, mais je n’ai toujours pas de meilleure idée.

Cycle 6: nombres 10, 20 et 30

Rouge

Bien qu’on change de dizaine, on voit bien que le problème de représentation est tout à fait analogue à celui des nombres 1 à 9.

  31   def test_9(self):
  32       self.check(9, "IX")
  33   
  34     def test_10_30(self):
  35       self.check(10, "X")
  36       self.check(20, "XX")
  37       self.check(30, "XXX")

Vert

La solution bête et rapide, c’est d’ajouter encore un cas à la structure conditionnelle. Le parallèle connu avec le cas des unités me commande cependant de modifier immédiatement la fonction roman_units, en la généralisant pour générer des séquences de symboles choisis (plutôt que seulement de I).

   1   def roman_units(u, symbol):
   2     return u * symbol
   3   
   4   def to_roman(n):
   5     if n >= 10:
   6       return roman_units(n / 10, "X")
   7     if n == 4:
   8       return "IV"
   9     if n == 9:
  10       return "IX"
  11     if n >= 5:
  12       return "V" + roman_units(n - 5, "I")
  13     return roman_units(n, "I")

Refac

Conformément à mon idée que la logique de représentation est la même pour tous les termes de décomposition du nombre, j’extrais cette logique dans une nouvelle fonction, que je nomme to_roman_part. En rétrospective, je trouve ce nom mal choisi: je parle de termes, mais mon code parle maintenant de parties.

   4   def to_roman_part(n, symb_unit, symb_half, symb_group):
   5     if n == 4:
   6       return "IV"
   7     if n == 9:
   8       return "IX"
   9     if n >= 5:
  10       return "V" + roman_units(n - 5, "I")
  11     return roman_units(n, "I")
  12   
  13   def to_roman(n):
  14     if n >= 10:
  15       return roman_units(n / 10, "X")
  16     return to_roman_part(n, "I", "V", "X")

Cette solution intermédiaire gère donc le problème des unités avec la nouvelle fonction et celui des dizaines avec un cas particulier. Je pourrai résoudre ce problème après avoir généralisé la logique de ma nouvelle routine to_roman_part.

   4   def to_roman_part(n, symb_unit, symb_half, symb_group):
   5     if n == 4:
   6       return symb_unit + symb_half
   7     if n == 9:
   8       return symb_unit + symb_group
   9     if n >= 5:
  10       return "V" + roman_units(n - 5, symb_unit)
  11     return roman_units(n, symb_unit)

Oui, cher lecteur, j’ai fait une erreur dans ma refactorisation! J’ai laissé à la ligne 10 une instance du symbole V, que j’aurais dû remplacer par symb_half… Nous y reviendrons.

Pour le moment, je me rends maintenant compte que la routine to_roman_part peut convertir les unités ou les dizaines en une représentation romaine. Elle convertit donc un chiffre arabe en son équivalent romain contextuel. Je la renomme donc pour exprimer cet aspect.

   4   def digit_to_roman(n, symb_unit, symb_half, symb_group):

J’ai aussi changé le nom à l’invocation à la ligne 13. Dans le même ordre d’idées, maintenant que je comprends mieux l’utilité de cette routine, son paramètre n sera inévitablement le chiffre à convertir. Je renomme donc ce paramètre à digit pour exprimer cette idée.

   4   def digit_to_roman(digit, symb_unit, symb_half, symb_group):

Le reste du corps de la méthode est modifié par un simple cherche-et-remplace. Finalement, considérant mon problème d’exprimer en chiffres romains les nombres 1 à 9, ainsi que 10, 20 et 30, je vois qu’il me suffit de décomposer mon nombre à exprimer en dizaines et unités, puis appliquer la routine de conversion à chaque chiffre respectivement. Ainsi, j’unifie la structure conditionnelle de la routine to_roman.

  13   def to_roman(n):
  14     return (
  15         digit_to_roman(n / 10, "X", "L", "C") +
  16         digit_to_roman(n % 10, "I", "V", "X")
  17         )

Cycle 7: nombres 40, 50… 90.

Rouge

La précédente amélioration du code suggère que cette solution élégante peut certainement gérer toutes les tranches de 10. Je remplace alors le test test_10_30 par test_tens.

  34   def test_tens(self):
  35       self.check(10, "X")
  36       self.check(20, "XX")
  37       self.check(30, "XXX")
  38       self.check(40, "XL")
  39       self.check(50, "L")
  40       self.check(60, "LX")
  41       self.check(70, "LXX")
  42       self.check(80, "LXXX")
  43       self.check(90, "XC")

Le test échoue, ce qui me surprend.

Vert

Un coup d’oeil à la routine me montre le bogue remarqué précédemment. Il est résolu facilement.

   9   if digit >= 5:
  10       return symb_half + roman_units(digit - 5, symb_unit)
  11     return roman_units(digit, symb_unit)

Refac

C’est bien comme ça.

Cycle 8: zéro

Rouge

Les romains ne manipulent pas explicitement zéro, mais zéro est néanmoins exprimé dans leurs nombres. Lorsqu’un nombre a zéro dizaines ou unités, sa réprésentation ne comporte tout simplement pas de chiffres pour représenter les dizaines ou les unités, respectivement. En d’autres termes, en chiffres romains, zéro est une chaîne vide.

  45   def test_zero(self):
  46       self.check(0, "")

Vert

Rien à changer: le test passe avec l’implantation actuelle! En effet, zéro est traité avec la dernière branche de la conditionnelle, et s’avère un cas unifiable à 1, 2 et 3.

Refac

Rien à faire.

Cycle 9: nombres avec dizaines et unités à la fois

Rouge

Nous avons tous les ingrédients pour gérer les nombres plus complexes.

  48   def test_tens_and_units(self):
  49       self.check(23, "XXIII")
  50       self.check(45, "XLV")
  51       self.check(89, "LXXXIX")
  52       self.check(91, "XCI")

Vert, refac

Rien à changer: le test passe.

Cycle 10: nombres entre 100 et 999

Rouge

Si la logique que nous avons peut gérer si simplement les nombres de 1 à 99, les centaines constituent la suite logique.

  54   def test_hundreds(self):
  55       self.check(305, "CCCV")
  56       self.check(459, "CDLIX")
  57       self.check(590, "DXC")
  58       self.check(700, "DCC")
  59       self.check(937, "CMXXXVII")

Vert

Dans un nombre avec des centaines, c’est un peu moins évident d’extraire les dizaines:

  13   def to_roman(n):
  14     return (
  15         digit_to_roman(n / 100, "C", "D", "M") +
  16         digit_to_roman((n % 100) / 10, "X", "L", "C") +
  17         digit_to_roman(n % 10, "I", "V", "X")
  18         )

Refac

L’expression des lignes 15 à 17 me dérange: ça sent la duplication de code. L’idée exprimée est qu’il faut traiter le chiffre des centaines avec tel triplet de symboles, puis le chiffre des dizaines avec tel autre triplet, puis celui des unités avec un troisième triplet. Ça ressemble donc à une itération: transformons l’expression complexe de concaténation avec une itération.

  13   def to_roman(n):
  14     roman = []
  15     for symbs in [("I", "V", "X"), ("X", "L", "C"), ("C", "D", "M")]:
  16       roman.append(digit_to_roman(n % 10, *symbs))
  17       n /= 10
  18     return "".join(reversed(roman))

Il s’agit d’une grosse modification au code. Je vois là une faiblesse dans ma maîtrise de la refactorisation: aurais-je pu faire cette modification en une séquence d’étapes plus simples? Je n’en ai aucune idée.

Je traite donc le nombre des unités aux centaines. J’obtiens donc une séquence inversée de termes en chiffres romains, que je désinverse pour avoir la solution finale.

Cycle 11: nombres >= 1000

Rouge

Il s’agit du dernier cas, le plus complexe.

  61   def test_thousands(self):
  62       self.check(1111, "MCXI")
  63       self.check(2597, "MMDXCVII")
  64       self.check(3848, "MMMDCCCXLVIII")
  65       self.check(3999, "MMMCMXCIX")

Vert

Le code ci-haut rend la logique pour les milliers simple à intégrer. Il s’agit simplement d’une itération de plus.

  13   def to_roman(n):
  14     roman = []
  15     for symbs in [("I", "V", "X"), ("X", "L", "C"), ("C", "D", "M"), ("M", "", "")]:
  16       roman.append(digit_to_roman(n % 10, *symbs))
  17       n /= 10
  18     return "".join(reversed(roman))

Refac

C’est tout beau et à mon goût. Projet complété!

Rétrospective

J’ai entrepris cet exercice simple pour pratiquer la direction du développement par les tests, selon le cycle rouge-vert-refac. Je suis convaincu d’avoir réussi: je suis parti d’un cas simple et j’ai fait grandir ma solution par petites étapes simples, chacune vérifiée par un test unitaire. La difficulté appréhendée de bien articuler la solution au gré du cycle a été dûment gérée.

Le principal problème décelé durant l’exécution du kata a consisté en la refactorisation. Je n’ai lu que très peu de chose sur le sujet, et j’ai attaqué le problème avec des connaissances a priori naïves. De plus, mon environnement de développement, dans son état actuel, n’offre aucune facilité sur laquelle m’appuyer pour refactoriser. Je sais que certains IDEs offrent des options et des fonctionnalités pour automatiser certaines refactorisations.

Je ne donne cependant pas crédit complet aux routines de refactorisation automatiques. Par exemple, le bogue introduit au cycle 6 n’aurait pas pu être évité, car je ne crois pas qu’il existe de routine automatique pour généraliser la logique d’une fonction ou d’une méthode. Cela exige, de manière générale, une compréhension sémantique du code qui est hors de portée d’un algorithme (incalculable). Quant à la mise en oeuvre de refactorisations trop gourmandes, je pense qu’il s’agit principalement d’une question d’expérience. En fin de compte, avant de changer mes outils, je crois qu’il me faudrait lire sur la systématisation du processus de refactorisation.