Du côté de chez Fouad

Du code et de l'architecture logicielle mais pas que...

Kata TDD - La Suite de Conway

Une démonstration de Kata incrémental

Profile picture
Fouad Hamdi
👨🏻‍💻 • 22 avril 2022

Introduction

Cet article illustre comment utiliser le Test Driven Development pour implémenter un exercise de programmation (qu’on appelle communément Kata).

Si vous souhaitez voir l’implémentation du Kata, c’est possible sans les commentaires:

Description du Kata

Il existe différents Katas: celui que j’ai choisi pour cet article est d’être capable de générer une suite de Conway telle que décrite ici.

Pour résumer: en entrée, on a une suite de chiffres, par exemple “1”, ainsi qu’un niveau de profondeur, par exemple “5” et en sortie, on a quelque chose comme:

1
11
21
12 11
11 12 21

Chaque ligne de la sortie se lit en énonçant les chiffres de la ligne précédente associé au nombre de fois que chacun de ces chiffres se répète.

Ainsi, “1” donne “un 1” (11), “11” donne “deux 1” (21), “21” donne “un 2 un 1” (1211), etc.

En anglais, cette suite a un nom plus évocateur: “Look And Say Sequence”.

L’approche TDD

Cet article n’a pas vocation à expliquer ce qu’est le TDD, je considère le lecteur familier avec ce sujet même si débutant. Si ce n’est pas le cas, je vous invite à lire TDD by Example puis de revenir éventuellement ici après si vous êtes motivé.

La méthode abordée pour ce kata est de tenter d’implémenter la solution avec un nombre minimal de modifications dans mon code de production pour faire passer les tests. Cela signifie qu’il peut y avoir des longs refactorings mais que la phase “Green” du cycle TDD doit être courte.

C’est ce que Kent Beck décrit comme “first, make the change easy then make the easy change” et c’est mon approche préférée du TDD car elle met un certain rythme et qu’elle me force à réfléchir à toutes les micro-décisions que je dois prendre à chacune des étapes du développement.

Concernant ces refactorings justement, ils seront décrits step by step tels que Martin Fowler les présente dans son livre: les tests sont lancés après chaque petite modification pour s’assurer qu’aucune grosse bêtise n’a été commise. Donc, pas de rehacktoring ici, à savoir des grosses modifications de code sans lancer les tests.

Il est recommandé de lire cet article avec un IDE à côté pour saisir le code décrit et mesurer les subtilités rencontrées notamment lors des refactorings.

Un dernier point avant de commencer et pour éviter tout malentendu: lors de cet execice, je ne vais m’occuper que du cas nominal et ne pas traiter les cas d’erreur. Dans le vrai monde de la réalité vraie, ce ne serait évidemment pas le cas.

Un peu de design mais pas trop

Avant d’écrire un premier test, réfléchissons un petit peu à l’API que l’on souhaite mettre en place.

Après avoir analysé le problème pendant quelques secondes, je me suis rendu compte que je n’avais pas vraiment envie de me prendre la tête avec la gestion des espaces et des retour chariot présents dans la sortie du programme.

Du coup, j’ai décidé de me concentrer sur le coeur de l’algorithme, une méthode qui prend en entrée une suite de chiffres sans espaces et qui retourne une ligne avec pour chaque chiffre, le nombre de fois qu’il apparait consécutivement.

Une fois cette méthode implémentée, il sera facile de la formater pour ajouter les espaces puis d’avoir une méthode qui boucle pour ajouter les retour chariot.

La seconde chose que je fais avant de commencer à écrire du code, c’est de définir une première liste de cas de tests pour cette méthode. Après réflexion, j’ai noté ceux-ci:

  • 1 -> 11
  • 12 -> 1112
  • 11 -> 21
  • 123 -> 111213
  • 112 -> 2112
  • 1121 -> 211211

Cette liste n’est pas du tout figée et pourra évoluer au fur et à mesure de ma compréhension du problème.

Finis les blabla, on commence enfin à coder

On peut enfin écrire notre premier test:

public class ConwaySuiteTests {
    @Test
    void oneDigit() {
        assertEquals("11", new ConwaySuite().lookAndSay("1"));
    }
}

Bien qu’il y ait très peu de lignes de code, un certain nombre de décisions sont prises ici:

  • la solution est orientée objet avec la déclaration d’une classe (ConwaySuite qui n’existe pas encore)
  • la méthode qui prend en entrée un seul argument est également nommée (lookAndSay)

Bien entendu, le test ne peut pas encore être exécuté. Le compilateur affiche le message:

Cannot resolve symbol 'ConwaySuite'

Créons la classe manquante pour le satisfaire:

public class ConwaySuite {
}

Le compilateur se plaint à présent que la méthode lookAndSay n’existe pas:

Cannot resolve method 'lookAndSay' in 'ConwaySuite'

Créons la méthode demandée pour lui faire plaisir à nouveau:

public class ConwaySuite {
    public String lookAndSay(String input) {
        return null;
    }
}

On retourne null pour faire en sorte que le test échoue.

Lançons les tests et vérifions que c’est bien le cas:

org.opentest4j.AssertionFailedError: 
Expected :11
Actual   :null

Le test plante pour la raison attendue: on souhaite avoir 11 en sortie et nous avons null à la place car la méthode créée ne fait encore rien.

TDD nous invite à écrire le code le plus simple possible pour faire passer le test. Dans cette optique, retournons 11 pour ne pas réfléchir trop longtemps:

public class ConwaySuite {
    public String lookAndSay(String input) {
        return "11";
    }
}

Cette simple modification fait passer les tests.

Cette technique de retourner la valeur attendue est une des stratégies décrites par Kent Beck pour faire passer les tests. Elle se nomme Fake It Til You Make It.

Nous pouvons rayer ce test de notre liste de départ:

  • 1 -> 11
  • 12 -> 1112
  • 11 -> 21
  • 123 -> 111213
  • 112 -> 2112
  • 1121 -> 211211

Evidemment, notre implémentation ne résout pas notre problème qui est de pouvoir générer une suite de Conway. Afin d’aller plus dans la direction souhaitée, nous devons forcer le code à ne plus retourner une constante.

On peut faire cela en rajoutant un exemple similaire au premier test mais avec une autre valeur, par exemple 2. Kent Beck parle dans ce cas de triangulation.

Avant d’écrire ce cas de test, ajoutons-le à notre liste (en 2ème position):

  • 1 -> 11
  • 2 -> 12
  • 12 -> 1112
  • 11 -> 21
  • 123 -> 111213
  • 112 -> 2112
  • 1121 -> 211211

Je modifie le test existant pour ajouter le nouveau cas de test car fondamentalement, il s’agit toujours de tester un argument avec un seul chiffre:

public class ConwaySuiteTests {
    @Test
    void oneDigit() {
        assertEquals("11", new ConwaySuite().lookAndSay("1"));
        assertEquals("12", new ConwaySuite().lookAndSay("2"));
    }
}

Voici l’erreur obtenue cette fois-ci:

org.opentest4j.AssertionFailedError: 
Expected :12
Actual   :11

Ce qui correspond bien à ce que l’on s’attend vu que notre méthode lookAndSay retourne une constante en dur.

Comment faire passer ce test simplement ?

Une première approche consiste à rajouter une condition sur l’argument d’entrée en suivant à nouveau la stratégie Fake It. Par exemple:

public String lookAndSay(String input) {
    if (input.equals("2"))
        return "12";
    
    return "11";
}

Le test va clairement passer mais il faudra trianguler à nouveau pour continuer l’implémentation puis refaire un Fake It, etc. Cela pourrait durer ad vitam eternam si nous en avions le temps.

En plus, rajouter à chaque fois une condition augmente la complexité de notre implémentation.

La question que l’on peut se poser alors est s’il y a un moyen de rendre ce code un peu plus générique pour qu’il soit un peu moins couplé à nos tests existants.

La réponse est oui. Comment ? En utilisant l’argument passé en entrée de la méthode.

Si on y réfléchit quelques secondes, ce que la méthode retourne est le nombre de fois (ici 1) qu’apparaît la chaine passée en argument (1 ou 2). On peut donc l’écrire ainsi:

public class ConwaySuite {
    public String lookAndSay(String input) {
        return "1" + input;
    }
}

Et le test passe ! Nous avons rendu notre code de production un peu plus générique et c’est une très bonne chose: en TDD, un adage veut que plus les tests deviennent spécifiques, plus le code de production devient générique.

Mettons à jour notre liste:

  • 1 -> 11
  • 2 -> 12
  • 12 -> 1112
  • 11 -> 21
  • 123 -> 111213
  • 112 -> 2112
  • 1121 -> 211211

Notre algorithme est capable de compter correctement les chaines de longueur 1: c’est un bon début !

Est-ce qu’on sera capable de compter 2 chiffres différents ?

Le cas de test suivant considère une entrée avec deux chiffres différents. Voici le test de ce scenario:

@Test
void twoDifferentDigits() {
    assertEquals("1112", new ConwaySuite().lookAndSay("12"));
}

Si on lance les tests, on a évidemment une erreur:

org.opentest4j.AssertionFailedError: 
Expected :1112
Actual   :112

On peut de nouveau utiliser la stratégie du Fake It pour faire passer le test en utilisant une condition:

public String lookAndSay(String input) {
    if (input.length() == 2) {
        return "1112";
    } else {
        return "1" + input;
    }
}

Pourquoi ai-je fait ça ? Parce que je n’ai aucune idée de comment implémenter l’algorithme plus simplement que ça à cette étape. J’ai besoin de plus d’exemples (donc de tests) pour commencer à entrevoir quelque chose.

Lançons les tests, ça passe sans surprise !

Rayons ce cas de test.

  • 1 -> 11
  • 2 -> 12
  • 12 -> 1112
  • 11 -> 21
  • 123 -> 111213
  • 112 -> 2112
  • 1121 -> 211211

On peut rajouter un nouveau cas de test pour trianguler:

  • 1 -> 11
  • 2 -> 12
  • 12 -> 1112
  • 21 -> 1211
  • 11 -> 21
  • 123 -> 111213
  • 112 -> 2112
  • 1121 -> 211211

Ce qui donne:

@Test
void twoDifferentDigits() {
    assertEquals("1112", new ConwaySuite().lookAndSay("12"));
    assertEquals("1211", new ConwaySuite().lookAndSay("21"));
}

L’erreur obtenue est la suivante:

org.opentest4j.AssertionFailedError: 
Expected :1211
Actual   :1112

L’implémentation pour faire passer ce test est assez simple: on remplace la constante retournée par la concaténation de chacun des caractères de l’argument précédé de 1:

public String lookAndSay(String input) {
    if (input.length() == 2) {
        return "1" + input.charAt(0) + "1" + input.charAt(1);
    } else {
        return "1" + input;
    }
}

Si on lance les tests, tout est vert, excellent !

A présent, notre algorithme sait compter les chaines de longueur 1 et celles de longueur 2 contenant des chiffres différents. On progresse !

En terme de refactoring, j’aimerais rendre le bloc else un peu plus symmétrique avec le bloc if en remplaçant input par input.charAt(0):

public String lookAndSay(String input) {
    if (input.length() == 2) {
        return "1" + input.charAt(0) + "1" + input.charAt(1);
    } else {
        return "1" + input.charAt(0);
    }
}

Mon détecteur de code smell me dit qu’il y a comme de la duplication dans ce code. Je suis confronté à une décision à prendre: dois-je refactorer le code pour éliminer cette duplication ou dois-je ajouter plus de tests ?

J’opte pour la seconde option car on a cette constante “1” qui est susceptible d’être différente pour les prochains exemples et qui peut avoir une influence sur les refactorings à effectuer. Parfois, il faut savoir patienter en tant que développeur pour avoir plus d’informations.

Mettons à jour notre liste de tests avant de continuer:

  • 1 -> 11
  • 2 -> 12
  • 12 -> 1112
  • 21 -> 1211
  • 11 -> 21
  • 123 -> 111213
  • 112 -> 2112
  • 1121 -> 211211

Le jour refactoring le plus long

On a justement un cas de test dans notre liste où l’on a une chaîne contenant deux chiffres identiques et qui va nous forcer à nous intéresser à cette constante:

@Test
void twoIdenticalDigits() {
    assertEquals("21", new ConwaySuite().lookAndSay("11"));
}

Lançons les tests et observons l’erreur obtenue:

org.opentest4j.AssertionFailedError: 
Expected :21
Actual   :1111

On va encore utiliser la technique du Fake It pour faire passer le test:

public String lookAndSay(String input) {
    if (input.length() == 2) {
        if (input.charAt(0) == input.charAt(1))
            return "2" + input.charAt(0);
        else
            return "1" + input.charAt(0) + "1" + input.charAt(1);
    } else {
        return "1" + input.charAt(0);
    }
}

Ce n’est pas très beau mais ça fait passer les tests et ça nous donne une structure de départ que l’on va pouvoir améliorer.

Mettons à jour notre liste:

  • 1 -> 11
  • 2 -> 12
  • 12 -> 1112
  • 21 -> 1211
  • 11 -> 21
  • 123 -> 111213
  • 112 -> 2112
  • 1121 -> 211211

Mon détecteur de code smell s’alarme encore plus que précédemment: il y a de la duplication mais elle n’est pas totalement explicite. C’est en général un signe qu’il faut refactorer pour:

  • d’abord rendre explicite cette ou ces duplications
  • ensuite simplifier le code

Comment rend-on la duplication explicite ? En faisant en sorte de rendre le plus similaire possible les différents blocs conditionnels de notre méthode car, fondamentalement, chacun de ces blocs fait la même chose: compter le nombre de chiffres dans la chaine.

Je vais décrire les étapes suivies pas à pas et entre chacune de ces étapes, je vais lancer les tests pour vérifier qu’ils passent toujours même si je ne l’écris pas.

Commençons par extraire une variable qui va contenir le résultat de la méthode dans le bloc else imbriqué:

else {
    var result = "";
    return "1" + input.charAt(0) + "1" + input.charAt(1);
}

Utilisons cette variable pour compter le 1er chiffre de l’argument:

else {
    var result = "";
    result += "1" + input.charAt(0);
    return "1" + input.charAt(0) + "1" + input.charAt(1);
}

Puis le second chiffre:

else {
    var result = "";
    result += "1" + input.charAt(0);
    result += "1" + input.charAt(1);
    return "1" + input.charAt(0) + "1" + input.charAt(1);
}

Retournons cette variable:

else {
    var result = "";
    result += "1" + input.charAt(0);
    result += "1" + input.charAt(1);
    return result;
}

Ce bloc de code dit: “je construis le résultat en indiquant combien de fois le premier chiffre apparait puis combien de fois le second chiffre apparait”.

Voici la méthode complète dans son nouvel état:

public String lookAndSay(String input) {
    if (input.length() == 2) {
        if (input.charAt(0) == input.charAt(1))
            return "2" + input.charAt(0);
        else {
            var result = "";
            result += "1" + input.charAt(0);
            result += "1" + input.charAt(1);
            return result;
        }
    } else {
        return "1" + input.charAt(0);
    }
}

Faisons apparaitre une structure similaire dans le second bloc else:

} else {
    var result = "";
    return "1" + input.charAt(0);
}

Concaténons le résultat à la variable:

} else {
    var result = "";
    result += "1" + input.charAt(0);
    return "1" + input.charAt(0);
}

Retournons la variable à présent:

} else {
    var result = "";
    result += "1" + input.charAt(0);
    return result;
}

Là, le code dit: “je construis le résultat en indiquant combien de fois le premier chiffre apparait”.

Essayons de faire la même chose dans le bloc if:

if (input.charAt(0) == input.charAt(1)) {
    var result = "";
    return "2" + input.charAt(0);
}

Comme précédemment, on concatène:

if (input.charAt(0) == input.charAt(1)) {
    var result = "";
    result += "2" + input.charAt(0);
    return "2" + input.charAt(0);
}

Et on retourne la variable:

if (input.charAt(0) == input.charAt(1)) {
    var result = "";
    result += "2" + input.charAt(0);
    return result;
}

La méthode complète:

if (input.length() == 2) {
    if (input.charAt(0) == input.charAt(1)) {
        var result = "";
        result += "2" + input.charAt(0);
        return result;
    } else {
        var result = "";
        result += "1" + input.charAt(0);
        result += "1" + input.charAt(1);
        return result;
    }
} else {
    var result = "";
    result += "1" + input.charAt(0);
    return result;
}

Est-ce que vous commencez à mieux voir la duplication ? Moi, oui en tout cas !

La variable result est utilisée dans tous les blocs, on peut donc la déclarer au début de la méthode:

public String lookAndSay(String input) {
    var result = "";
    if (input.length() == 2) {
        if (input.charAt(0) == input.charAt(1)) {
            result += "2" + input.charAt(0);
            return result;
        } else {
            result += "1" + input.charAt(0);
            result += "1" + input.charAt(1);
            return result;
        }
    } else {
        result += "1" + input.charAt(0);
        return result;
    }
}

On peut extraire le dernier return result du else global:

public String lookAndSay(String input) {
    var result = "";
    if (input.length() == 2) {
        if (input.charAt(0) == input.charAt(1)) {
            result += "2" + input.charAt(0);
            return result;
        } else {
            result += "1" + input.charAt(0);
            result += "1" + input.charAt(1);
            return result;
        }
    } else {
        result += "1" + input.charAt(0);
    }
    return result;
}

Puis supprimer un second return:

public String lookAndSay(String input) {
    var result = "";
    if (input.length() == 2) {
        if (input.charAt(0) == input.charAt(1)) {
            result += "2" + input.charAt(0);
            return result;
        } else {
            result += "1" + input.charAt(0);
            result += "1" + input.charAt(1);
        }
    } else {
        result += "1" + input.charAt(0);
    }
    return result;
}

Et enfin, le dernier:

public String lookAndSay(String input) {
    var result = "";
    if (input.length() == 2) {
        if (input.charAt(0) == input.charAt(1)) {
            result += "2" + input.charAt(0);
        } else {
            result += "1" + input.charAt(0);
            result += "1" + input.charAt(1);
        }
    } else {
        result += "1" + input.charAt(0);
    }
    return result;
}

Ce qui nous embête à présent, ce sont les constantes “1” et “2” qui ne sont pas toutes pareil.

Le concept qui se trouve derrière est le nombre de fois que chaque chiffre apparait. Extrayons une variable count dans le 2nd bloc else pour représenter ce concept:

} else {
    var count = 1;
    result += "1" + input.charAt(0);
}

Utilisons cette variable dans la construction du résultat:

} else {
    var count = 1;
    result += count + "" + input.charAt(0);
}

Faisons la même chose dans l’autre bloc else:

} else {
    var count = 1;
    result += "1" + input.charAt(0);
    result += "1" + input.charAt(1);
}

Utilisons la variable dans la 1ère concaténation pour que ce soit symmétrique avec le bloc précédemment traité:

} else {
    var count = 1;
    result += count + "" + input.charAt(0);
    result += "1" + input.charAt(1);
}

Les deux premières lignes du bloc sont plutôt bien mais la troisième a l’air un peu plus embêtante.

La question que je me pose est: est-ce le count de la première concaténation est le même que le “1” de la deuxième concaténation. En terme de valeur, oui mais certainement pas en terme d’instance: dans le premier cas, count correspond au nombre de fois qu’apparait le premier chiffre et “1” au nombre de fois qu’apparait le second chiffre. C’est une coincidence accidentelle dûe à notre test que ces deux nombres ont la même valeur !

Comment donc faire apparaitre cette différence.

Le plus simple, selon moi, est de réinitialiser cette variable count à la valeur 1 après la première concaténation:

} else {
    var count = 1;
    result += count + "" + input.charAt(0);

    count = 1;
    result += "1" + input.charAt(1);
}

Puis on la réutilise dans la seconde concaténation:

} else {
    var count = 1;
    result += count + "" + input.charAt(0);

    count = 1;
    result += count + "" + input.charAt(1);
}

Le code dit à présent: “je compte combien de fois le premier chiffre apparait (1) puis je compte le nombre de fois que le second chiffre apparait (1 aussi)“. C’est très subtil mais ça nous permet de rendre encore plus explicite la duplication.

Passons au bloc if à présent dans lequel on va également déclarer une variable count:

if (input.charAt(0) == input.charAt(1)) {
    var count = 1;
    result += "2" + input.charAt(0);
}

La concaténation est un peu différente des précédentes car on a un “2” cette fois-ci au lieu d’un “1”. Comment peut-on passer faire en sorte d’utiliser la variable count à la place de ce “2” pour que la ligne soit semblable aux autres blocs ?

En incrémentant count:

if (input.charAt(0) == input.charAt(1)) {
    var count = 1;
    count++;
    result += "2" + input.charAt(0);
}

On peut à présent utiliser la variable count comme dans les autres blocs:

if (input.charAt(0) == input.charAt(1)) {
    var count = 1;
    count++;
    result += count + "" + input.charAt(0);
}

Voici l’état actuel de la méthode à présent:

public String lookAndSay(String input) {
    var result = "";
    if (input.length() == 2) {
        if (input.charAt(0) == input.charAt(1)) {
            var count = 1;
            count++;
            result += count + "" + input.charAt(0);
        } else {
            var count = 1;
            result += count + "" + input.charAt(0);

            count = 1;
            result += count + "" + input.charAt(1);
        }
    } else {
        var count = 1;
        result += count + "" + input.charAt(0);
    }
    return result;
}

Nous avons réussi à rendre visible ces duplications implicites en y a allant à petits pas et avec les tests qui sont restés verts après chacune de ces étapes. Maintenant, on va pouvoir simplifier le code.

La variable count apparaît partout et est toujours initialisée à 1, sortons-là de là:

public String lookAndSay(String input) {
    var count = 1;
    var result = "";
    if (input.length() == 2) {
        if (input.charAt(0) == input.charAt(1)) {
            count++;
            result += count + "" + input.charAt(0);
        } else {
            result += count + "" + input.charAt(0);

            count = 1;
            result += count + "" + input.charAt(1);
        }
    } else {
        result += count + "" + input.charAt(0);
    }
    return result;
}

Je vais me concentrer dans un premier temps sur le bloc if...else imbriqué.

Ahhhh, je me rends compte que le code dans chaque bloc n’est pas tout à fait similaire. Dans le bloc if, on a:

count++; // on compte
result += count + "" + input.charAt(0); // on concatène

et dans le bloc else:

count = 1; // on compte
result += count + "" + input.charAt(1); // on concatène

Vous voyez la petite subtilité: dans le premier cas, on a input.charAt(0) et dans le second input.charAt(1). Est-ce qu’on ne pourrait pas arranger ça ?

Eh bien si, en fait car dans le bloc if, input.charAt(0) et input.charAt(1) sont identiques ! On peut donc tout à fait remplacer input.charAt(0) par input.charAt(1) dans ce bloc:

if (input.charAt(0) == input.charAt(1)) {
    count++;
    result += count + "" + input.charAt(1);
} else {
    result += count + "" + input.charAt(0);

    count = 1;
    result += count + "" + input.charAt(1);
}

Grâce à cela, on peut sortir la dernière ligne des blocs if...else car elles sont à présent identiques:

if (input.length() == 2) {
    if (input.charAt(0) == input.charAt(1)) {
        count++;
    } else {
        result += count + "" + input.charAt(0);
        count = 1;
    }
    result += count + "" + input.charAt(1);
}

Passons au bloc if...else global. Le bloc if se termine avec la ligne:

result += count + "" + input.charAt(1);

et le bloc else correspondant contient uniquement la ligne:

result += count + "" + input.charAt(0);

Ahhhhh et là, on a également une petite différence qui nous empêche de refactorer comme précédemment. Car cette fois-ci, dans le bloc if, input.charAt(0) n’est plus forcément égal à input.charAt(1) et dans le bloc else, il n’y a qu’un caractère dans la chaîne, on n’a pas de input.charAt(1) !!!

On dirait qu’on est bien bloqué et qu’on doive revenir en arrière…sauf que…un instant, svp !

Si on y réfléchit quelques secondes, dans le bloc if, l’argument a deux caractères donc input.charAt(1) correspond au dernier caractère de cette chaîne. Et dans le bloc else, l’argument n’a qu’un seul caractère et donc input.charAt(0) correspond aussi au dernier caractère de cette chaîne !

Il est donc tout à fait possible d’égaliser ces deux chaînes en utilisant input.charAt(input.length() - 1) !!! Essayons pour voir, dans le bloc else pour commencer:

public String lookAndSay(String input) {
    var count = 1;
    var result = "";
    if (input.length() == 2) {
        if (input.charAt(0) == input.charAt(1)) {
            count++;
        } else {
            result += count + "" + input.charAt(0);
            count = 1;
        }
        result += count + "" + input.charAt(1);
    } else {
        result += count + "" + input.charAt(input.length() - 1);
    }
    return result;
}

Puis dans le bloc if:

public String lookAndSay(String input) {
    var count = 1;
    var result = "";
    if (input.length() == 2) {
        if (input.charAt(0) == input.charAt(1)) {
            count++;
        } else {
            result += count + "" + input.charAt(0);
            count = 1;
        }
        result += count + "" + input.charAt(input.length() - 1);
    } else {
        result += count + "" + input.charAt(input.length() - 1);
    }
    return result;
}

A présent, les blocs du 1er if...else se terminent de la même façon, on peut extraire cette dernière ligne de ces blocs:

public String lookAndSay(String input) {
    var count = 1;
    var result = "";
    if (input.length() == 2) {
        if (input.charAt(0) == input.charAt(1)) {
            count++;
        } else {
            result += count + "" + input.charAt(0);
            count = 1;
        }
    } else {
    }
    result += count + "" + input.charAt(input.length() - 1);
    return result;
}

Notre bloc else global est vide à présent, supprimons-le:

public String lookAndSay(String input) {
    var count = 1;
    var result = "";
    if (input.length() == 2) {
        if (input.charAt(0) == input.charAt(1)) {
            count++;
        } else {
            result += count + "" + input.charAt(0);
            count = 1;
        }
    }
    result += count + "" + input.charAt(input.length() - 1);
    return result;
}

C’est plutôt pas mal, je trouve.

Maintenant, nos tests ne contiennent que des exemples avec 1 ou 2 chiffres en entrée. Si on doit rajouter plus de chiffres, on aura forcément besoin d’une boucle (ou d’une récursion) pour rendre notre code plus générique.

Dans l’esprit du “First, make it easy then make the easy change”, préparons notre code à accueillir cette future boucle qui fera passer notre prochain test.

Qui dit boucle dit variable d’itération qu’on va appeler index et initialiser à 0 pour correspondre au premier chiffre traité:

public String lookAndSay(String input) {
    var count = 1;
    var result = "";
    var index = 0;
    if (input.length() == 2) {
        if (input.charAt(0) == input.charAt(1)) {
            count++;
        } else {
            result += count + "" + input.charAt(0);
            count = 1;
        }
    }
    result += count + "" + input.charAt(input.length() - 1);
    return result;
}

Remplaçons nos .charAt(0) par des .charAt(index). D’abord dans l’expression du bloc if:

public String lookAndSay(String input) {
    var count = 1;
    var result = "";
    var index = 0;
    if (input.length() == 2) {
        if (input.charAt(index) == input.charAt(1)) {
            count++;
        } else {
            result += count + "" + input.charAt(0);
            count = 1;
        }
    }
    result += count + "" + input.charAt(input.length() - 1);
    return result;
}

puis dans le bloc else:

public String lookAndSay(String input) {
    var count = 1;
    var result = "";
    var index = 0;
    if (input.length() == 2) {
        if (input.charAt(index) == input.charAt(1)) {
            count++;
        } else {
            result += count + "" + input.charAt(index);
            count = 1;
        }
    }
    result += count + "" + input.charAt(input.length() - 1);
    return result;
}

Et à nouveau dans l’expression du bloc if pour désigner le prochain chiffre de la chaîne:

public String lookAndSay(String input) {
    var count = 1;
    var result = "";
    var index = 0;
    if (input.length() == 2) {
        if (input.charAt(index) == input.charAt(index + 1)) {
            count++;
        } else {
            result += count + "" + input.charAt(index);
            count = 1;
        }
    }
    result += count + "" + input.charAt(input.length() - 1);
    return result;
}

Une dernière petite chose: générifions la condition du if pour que la condition soit valable lorsque la longueur de l’argument est plus grande que 1.

public String lookAndSay(String input) {
    var count = 1;
    var result = "";
    var index = 0;
    if (input.length() > 1) {
        if (input.charAt(index) == input.charAt(index + 1)) {
            count++;
        } else {
            result += count + "" + input.charAt(index);
            count = 1;
        }
    }
    result += count + "" + input.charAt(input.length() - 1);
    return result;
}

Toutes nos petites modifications ont permis de préparer la résolution du test suivant.

C’est trop simple maintenant qu’on a tout préparé

Voici le test:

@Test
void threeDifferentDigits() {
    assertEquals("111213", new ConwaySuite().lookAndSay("123"));
}

Le test ne passe pas car, comme prévu, nous n’avons pas encore de boucle pour traiter un chiffre supplémentaire. Grâce au refactoring précédent, il est très simple de la rajouter:

public String lookAndSay(String input) {
    var count = 1;
    var result = "";
    for (var index = 0; index < input.length() - 1; index++) {
        if (input.length() > 1) {
            if (input.charAt(index) == input.charAt(index + 1)) {
                count++;
            } else {
                result += count + "" + input.charAt(index);
                count = 1;
            }
        }
    }
    result += count + "" + input.charAt(input.length() - 1);
    return result;
}

Et les tests passent, c’est magique !

C’est une des choses que j’adore dans le TDD: on refactore par petites touches en identifiant les code smells, sans vraiment réfléchir à l’algorithme complet et si c’est bien fait, il est très facile de faire passer le test suivant.

On n’a plus besoin de la condition input.length() > 1 puisqu’elle sera toujours vraie si on entre dans la boucle:

public String lookAndSay(String input) {
    var count = 1;
    var result = "";
    for (var index = 0; index < input.length() - 1; index++) {
        if (input.charAt(index) == input.charAt(index + 1)) {
            count++;
        } else {
            result += count + "" + input.charAt(index);
            count = 1;
        }
    }
    result += count + "" + input.charAt(input.length() - 1);
    return result;
}

Mettons à jour notre liste de tests:

  • 1 -> 11
  • 2 -> 12
  • 12 -> 1112
  • 21 -> 1211
  • 11 -> 21
  • 123 -> 111213
  • 112 -> 2112
  • 1121 -> 211211

Eh, on n’a pas oublié de refactorer un peu les tests, là ?

C’est vrai, il y a aussi un peu de duplication dans nos tests: ajoutons une méthode d’assertion qui va appeler la méthode testée et en vérifier le résultat.

Commençons par extraire des variables dans la méthode oneDigit. Le résultat attendu d’abord:

@Test
void oneDigit() {
    var expected = "11";
    assertEquals(expected, new ConwaySuite().lookAndSay("1"));
    assertEquals("12", new ConwaySuite().lookAndSay("2"));
}

Puis l’argument testé ensuite:

@Test
void oneDigit() {
    var expected = "11";
    var input = "1";
    assertEquals(expected, new ConwaySuite().lookAndSay(input));
    assertEquals("12", new ConwaySuite().lookAndSay("2"));
}

On peut extraire une méthode du premier assertEquals (et si, vous utilisez un bon IDE (IntelliJ par exemple), il fera le refactoring automatique de toutes les autres méthodes de test pour vous):

@Test
void oneDigit() {
    var expected = "11";
    var input = "1";
    assertLookAndSay(expected, input);
    assertLookAndSay("12", "2");
}

private void assertLookAndSay(String expected, String input) {
    assertEquals(expected, new ConwaySuite().lookAndSay(input));
}

On peut inliner les variables créées précédemment:

@Test
void oneDigit() {
    assertLookAndSay("11", "1");
    assertLookAndSay("12", "2");
}

Les tests complets après ce refactoring:

public class ConwaySuiteTests {
    @Test
    void oneDigit() {
        assertLookAndSay("11", "1");
        assertLookAndSay("12", "2");
    }

    @Test
    void twoDifferentDigits() {
        assertLookAndSay("1112", "12");
        assertLookAndSay("1211", "21");
    }

    @Test
    void twoIdenticalDigits() {
        assertLookAndSay("21", "11");
    }

    @Test
    void threeDifferentDigits() {
        assertLookAndSay("111213", "123");
    }

    private void assertLookAndSay(String expected, String input) {
        assertEquals(expected, new ConwaySuite().lookAndSay(input));
    }
}

Mmmm, je n’aime pas l’ordre des arguments de la méthode assertLookAndSay: il ne correspond pas vraiment au nommage des tests. Par exemple, dans la méthode twoIdenticalDigits, on a assertLookAndSay("21", "11"): les deux chiffres identiques sont à la fin, ça fait un peu bizarre.

Ce n’est pas grave, on va utiliser le refactoring qui change la signature d’une méthode pour inverser l’ordre des arguments. Avec un bon IDE, c’est aussi assez simple. Voici le résultat obtenu:

public class ConwaySuiteTests {
    @Test
    void oneDigit() {
        assertLookAndSay("1", "11");
        assertLookAndSay("2", "12");
    }

    @Test
    void twoDifferentDigits() {
        assertLookAndSay("12", "1112");
        assertLookAndSay("21", "1211");
    }

    @Test
    void twoIdenticalDigits() {
        assertLookAndSay("11", "21");
    }

    @Test
    void threeDifferentDigits() {
        assertLookAndSay("123", "111213");
    }

    private void assertLookAndSay(String input, String expected) {
        assertEquals(expected, new ConwaySuite().lookAndSay(input));
    }
}

J’aime beaucoup mieux !

Mais attends, là, ça marche encore sans qu’on fasse rien, c’est une blague ?

Passons au test suivant:

@Test
void twoConsecutiveIdenticalDigitsWithinThree() {
    assertLookAndSay("112", "2112");
}

Lançons les tests et…ils passent !

Est-ce que l’on aurait implémenté l’algorithme sans nous en rendre compte ? Essayons avec le test suivant:

@Test
void sameDigitAtDifferentLocations() {
    assertLookAndSay("1121", "211211");
}

Et ça passe également, c’est top !!!

Du coup, tous nos tests passent:

  • 1 -> 11
  • 2 -> 12
  • 12 -> 1112
  • 21 -> 1211
  • 11 -> 21
  • 123 -> 111213
  • 112 -> 2112
  • 1121 -> 211211

Si on relit notre implémentation, il semblerait que l’algorithme parcourt bien chaque chiffre de notre argument et pour chacun de ces chiffres, il comptabilise combien de fois il apparaît avant de concaténer cette info dans le résultat attendu en sortie.

Revoici le code complet:

public class ConwaySuite {
    public String lookAndSay(String input) {
        var count = 1;
        var result = "";
        for (var index = 0; index < input.length() - 1; index++) {
            if (input.charAt(index) == input.charAt(index + 1)) {
                count++;
            } else {
                result += count + "" + input.charAt(index);
                count = 1;
            }
        }
        result += count + "" + input.charAt(input.length() - 1);
        return result;
    }
}

Extrayons une méthode et quelques variables explicatives pour faciliter la lecture du code:

public String lookAndSay(String input) {
    var count = 1;
    var result = "";
    for (var index = 0; index < input.length() - 1; index++) {
        char currentDigit = input.charAt(index);
        char nextDigit = input.charAt(index + 1);
        if (currentDigit == nextDigit) {
            count++;
        } else {
            result += say(count, currentDigit);
            count = 1;
        }
    }
    char lastDigit = input.charAt(input.length() - 1);
    result += say(count, lastDigit);
    return result;
}

private String say(int count, char digit) {
    return count + "" + digit;
}

Je n’ai pas détaillé les étapes ce coup-ci mais vous voyez l’idée. On pourrait également utiliser un StringBuilder pour concaténer les résultats et faire d’autres petits refactorings mais je vais m’arrêter là car le code est suffisamment compréhensible et flexible pour supporter de futures évolutions si nécessaire.

Le formatage avant le dessert

Notre API n’est pas encore terminée ! Nous devons à présent rajouter un espace après avoir compté un chiffre. Modifions nos tests pour tenir compte de cette évolution:

@Test
void twoDifferentDigits() {
    assertLookAndSay("12", "11 12");
    assertLookAndSay("21", "12 11");
}

@Test
void threeDifferentDigits() {
    assertLookAndSay("123", "11 12 13");
}

@Test
void twoConsecutiveIdenticalDigitsWithinThree() {
    assertLookAndSay("112", "21 12");
}

@Test
void sameDigitAtDifferentLocations() {
    assertLookAndSay("1121", "21 12 11");
}

Les méthodes oneDigit et twoIdenticalDigits n’ont pas changé.

Les tests ne passent pas. Voici la sortie pour twoDifferentDigits:

org.opentest4j.AssertionFailedError: 
Expected :11 12
Actual   :1112

Pour faire passer les tests, rien de plus simple: on ajoute l’espace dans la méthode say:

private String say(int count, char digit) {
    return count + "" + digit + " ";
}

et on supprime le dernier espace à la fin de la chaîne construite dans lookAndSay:

public String lookAndSay(String input) {
    var count = 1;
    var result = "";
    for (var index = 0; index < input.length() - 1; index++) {
        char currentDigit = input.charAt(index);
        char nextDigit = input.charAt(index + 1);
        if (currentDigit == nextDigit) {
            count++;
        } else {
            result += say(count, currentDigit);
            count = 1;
        }
    }
    char lastDigit = input.charAt(input.length() - 1);
    result += say(count, lastDigit);
    return result.trim();
}

Et les tests passent ! On a bien fait de garder la gestion des espaces pour après.

On y est presque

La dernière étape pour terminer notre kata est d’ajouter la méthode qui prend une chaîne en entrée et le niveau de profondeur souhaité pour la suite.

Pour le coup, je vais aller un peu plus vite dans cette section car on a vu l’essentiel auparavant.

Voici les tests qu’on va utiliser:

  • 1, 1 -> 1\n
  • 1, 2 -> 1\n11\n
  • 1, 4 -> 1\n11\n21\n12 11\n

Le premier test:

@Test
void depthOfOne() {
    assertEquals("1\n", new ConwaySuite().lookAndSay("1", 1));
}

J’ai pris ici la décision d’appeler cette méthode comme notre première méthode mais en lui ajoutant un second argument correspondant au nombre de lignes souhaitées en sortie.

Créons la méthode qui n’existe pas:

public String lookAndSay(String input, int depth) {
    return null;
}

Pour faire passer test, concaténons l’argument avec un retour chariot:

public String lookAndSay(String input, int depth) {
    return input + "\n";
}

Je vais un peu plus vite que précédemment mais, évidemment si je rencontre un problème que je n’arrive pas à résoudre facilement, je reviens en arrière et je ralentis.

Passons au test suivant:

@Test
void depthOfTwo() {
    assertEquals("1\n11\n", new ConwaySuite().lookAndSay("1", 2));
}

Faire passer ce test n’est pas trop compliqué:

public String lookAndSay(String input, int depth) {
    if (depth > 1) {
        return input + "\n" + lookAndSay(input) + "\n";
    }
    return input + "\n";
}

Et le test suivant pour trianguler et finaliser la méthode:

@Test
void depthOfFour() {
    assertEquals("1\n11\n21\n12 11\n", new ConwaySuite().lookAndSay("1", 4));
}

Ce coup-ci, je vais le faire en récursif pour changer:

public String lookAndSay(String input, int depth) {
    if (depth > 1) {
        var next = lookAndSay(input.replace(" ", ""));
        return input + "\n" + lookAndSay(next, depth - 1);
    } else {
        return input + "\n";
    }
}

La petite subtilité ici est la suppression des espaces dans la variable input afin de pouvoir appeler la première méthode lookAndSay.

En guise de test de bout en bout, voici la suite de Conway générée avec notre programme jusqu’à 20:

1
11
21
12 11
11 12 21
31 22 11
13 11 22 21
11 13 21 32 11
31 13 12 11 13 12 21
13 21 13 11 12 31 13 11 22 11
11 13 12 21 13 31 12 13 21 13 21 22 21
31 13 11 22 21 23 21 12 11 13 12 21 13 12 11 32 11
13 21 13 21 32 11 12 13 12 21 12 31 13 11 22 21 13 11 12 21 13 12 21
11 13 12 21 13 12 11 13 12 31 12 11 13 11 22 21 12 13 21 13 21 32 21 13 31 22 21 13 11 22 11
31 13 11 22 21 13 11 12 31 13 11 12 13 21 12 31 13 21 32 21 12 11 13 12 21 13 12 11 13 22 21 23 11 32 21 13 21 22 21
13 21 13 21 32 21 13 31 12 13 21 13 31 12 11 13 12 21 12 13 21 13 12 11 13 22 21 12 31 13 11 22 21 13 11 12 31 13 32 11 12 13 21 13 22 21 13 12 11 32 11
11 13 12 21 13 12 11 13 22 21 23 21 12 11 13 12 21 23 21 12 31 13 11 22 21 12 11 13 12 21 13 11 12 31 13 32 21 12 13 21 13 21 32 21 13 31 12 13 21 23 12 31 12 11 13 12 21 13 32 21 13 11 12 21 13 12 21
31 13 11 22 21 13 11 12 31 13 32 11 12 13 12 21 12 31 13 11 22 11 12 13 12 21 12 13 21 13 21 32 21 12 31 13 11 22 21 13 31 12 13 21 23 22 21 12 11 13 12 21 13 12 11 13 22 21 23 21 12 11 13 12 11 12 13 11 12 13 21 12 31 13 11 22 21 23 22 21 13 31 22 21 13 11 22 11
13 21 13 21 32 21 13 31 12 13 21 23 12 31 12 11 13 11 22 21 12 13 21 13 21 22 31 12 11 13 11 22 21 12 11 13 12 21 13 12 11 13 22 21 12 13 21 13 21 32 21 23 21 12 11 13 12 11 12 13 32 21 12 31 13 11 22 21 13 11 12 31 13 32 11 12 13 12 21 12 31 13 11 12 31 12 11 13 31 12 11 13 12 21 12 13 21 13 21 32 11 12 13 32 21 23 11 32 21 13 21 22 21
11 13 12 21 13 12 11 13 22 21 23 21 12 11 13 12 11 12 13 11 12 13 21 12 31 13 21 32 21 12 11 13 12 21 13 12 11 22 13 21 12 31 13 21 32 21 12 31 13 11 22 21 13 11 12 31 13 32 21 12 11 13 12 21 13 12 11 13 22 11 12 13 12 21 12 31 13 11 12 31 12 11 23 22 21 12 13 21 13 21 32 21 13 31 12 13 21 23 12 31 12 11 13 11 22 21 12 13 21 13 31 12 13 21 12 31 23 21 12 31 13 11 22 21 12 11 13 12 21 13 12 11 13 12 31 12 11 23 22 11 12 13 21 13 22 21 13 12 11 32 11

J’ai vérifié (faites-moi confiance) qu’elle correspondait bien à l’exemple du Wikipedia.

Pour référence, voici les tests complets:

import static org.junit.jupiter.api.Assertions.assertEquals;

public class ConwaySuiteTests {
    @Test
    void oneDigit() {
        assertLookAndSay("1", "11");
        assertLookAndSay("2", "12");
    }

    @Test
    void twoDifferentDigits() {
        assertLookAndSay("12", "11 12");
        assertLookAndSay("21", "12 11");
    }

    @Test
    void twoIdenticalDigits() {
        assertLookAndSay("11", "21");
    }

    @Test
    void threeDifferentDigits() {
        assertLookAndSay("123", "11 12 13");
    }

    @Test
    void twoConsecutiveIdenticalDigitsWithinThree() {
        assertLookAndSay("112", "21 12");
    }

    @Test
    void sameDigitAtDifferentLocations() {
        assertLookAndSay("1121", "21 12 11");
    }

    @Test
    void depthOfOne() {
        assertEquals("1\n", new ConwaySuite().lookAndSay("1", 1));
    }

    @Test
    void depthOfTwo() {
        assertEquals("1\n11\n", new ConwaySuite().lookAndSay("1", 2));
    }

    @Test
    void depthOfFour() {
        assertEquals("1\n11\n21\n12 11\n", new ConwaySuite().lookAndSay("1", 4));
    }

    private void assertLookAndSay(String input, String expected) {
        assertEquals(expected, new ConwaySuite().lookAndSay(input));
    }

    @Test
    void example() {
        System.out.println(new ConwaySuite().lookAndSay("1", 20));
    }
}

et la classe complète:

public class ConwaySuite {
    public String lookAndSay(String input) {
        var count = 1;
        var result = "";
        for (var index = 0; index < input.length() - 1; index++) {
            char currentDigit = input.charAt(index);
            char nextDigit = input.charAt(index + 1);
            if (currentDigit == nextDigit) {
                count++;
            } else {
                result += say(count, currentDigit);
                count = 1;
            }
        }
        char lastDigit = input.charAt(input.length() - 1);
        result += say(count, lastDigit);
        return result.trim();
    }

    private String say(int count, char digit) {
        return count + "" + digit + " ";
    }

    public String lookAndSay(String input, int depth) {
        if (depth > 1) {
            var next = lookAndSay(input.replace(" ", ""));
            return input + "\n" + lookAndSay(next, depth - 1);
        } else {
            return input + "\n";
        }
    }
}

Conclusion

Nous avons vu dans cet article comment implémenter incrémentalement un algorithme en mode TDD.

Est-ce la meilleure solution ? Probablement pas et ce n’est certainement pas la seule.

Ce qui est sûr, c’est que la méthode implémentant l’algorithme principal est compréhensible (à mon goût) et peut évoluer facilement si nécessaire en cas de futurs besoins et c’est bien là l’essentiel.

© 2023 Du côté de chez Fouad. Tous droits réservés.