Test Driven Developement – Kata : Facteurs premiers (Prime Factors)
Dans le Premier Kata WordWrap, nous avons vu comment la technique d’appliquer le TDD en faisant des petits pas nous emmène à construire l’algorithme de façon simple et automatique. Nous allons voir un deuxième exemple de cette technique via un deuxième Kata, Le kata populaire Facteurs Premiers (PrimeFactors).
Dans ce Kata, nous verrons encore s’appliquer la prémisse de “Transformations” que nous rapporte Uncle Bob.
Prenez un peu de temps pour suivre les étapes du Kata et vous pourrez forker et utiliser le code depuis Github.
Sommaire
Enoncé du Kata
Ecrire une classe “PrimeFactors” qui a une seule méthode statique “generate”. Cette méthode prend un argument de type entier et retourne un tableau d’entiers représentant les facteurs premiers.
Implémentation
Commençons par créer un test PrimeFactorsTest vide
class PrimeFactorsTest extends PHPUnit_Framework_TestCase
{
}
et s’assurer que notre PHPUnit nous affiche bien un warning qui ressemble a ceci :
No tests found in class "PrimeFactorsTest".
FAILURES!
Tests: 1, Assertions: 0, Failures: 1.
Le premier test
Testons tout d’abord qu’il n’y a pas de facteur premier pour l’entier 1.
class PrimeFactorsTest extends PHPUnit_Framework_TestCase
{
public function testOne()
{
$this->assertSame(array(), PrimeFactors::generate(1));
}
}
Bien évidemment, la classe PrimeFactors et sa methode generate n’existent pas et le test échoue à ce stade. Ajoutons alors cette classe et faisons marcher le test.
ceci est suffisant pour faire réussir le premier test.
Le deuxième test
Ecrivons un test qui s’assure que le facteur premier de 2 est un tableau contenant 2. Ajoutons la méthode testTwo à notre test :
Le test échoue, faisons le passer avec un minimum d’effort :
class PrimeFactors
{
public static function generate($n)
{
$primes = array();
if ($n > 1) {
$primes[] = 2;
}
return $primes;
}
}
Nous avons tout simplement traité le cas spécifique du test en testant que si l’argument passé est supérieur à 1, nous retournons la valeur que nous voulons tester. Ceci couvre notre test, qui passe maintenant!. Continuons avec un troisième test!
Troisième test
Testons le facteur premier de 3 maintenant.
Nous nous attendions bien sur à avoir 3 dans notre tableau, mais nous avons reçu 2 comme retour, puisque le test précédent “hardcode” cette valeur. Comment faire pour fixer ceci en une seule passe?
class PrimeFactors
{
public static function generate($n)
{
$primes = array();
if ($n > 1) {
$primes[] = $n;
}
return $primes;
}
}
remplacer la valeur de retour par $n. Bon, c’est facile jusque la, et tant mieux pour nous! 🙂 Continuons avec un quatrième test :
Quatrième test
Quand on arrive à tester le nombre 4, le résultat va changer pour être un tableau contenant deux facteurs premiers qui ont la même valeur, soit 2 et 2. Ecrivons un test pour ça.
Le test échoue bien sur, Comment nous pouvons fixer ce test? Pour traiter notre cas spécifique du nombre 4, nous pouvons tester que dans le cas ou $n est plus grand que 1, si il est divisible par 2, nous ajoutons 2 à notre tableau et nous effectuons la division de $n par 2.
class PrimeFactors
{
public static function generate($n)
{
$primes = array();
if ($n > 1) {
if (0 === $n%2) {
$primes[] = 2;
$n /= 2;
}
if ($n > 1) {
$primes[] = $n;
}
}
return $primes;
}
}
Le test passe.. mais le code devient bizarre. Remarquez bien le if ($n > 1) qui est inclut dans un même if .. Bon. Continuons pour le moment quant même avec le test suivant!
Cinquième test
5 étant un nombre premier, ce cas ne changera rien, testons la prochaine valeur, soit 6. Les facteurs premiers de 6 sont 2 et 3.
Ça passe! Tant mieux! Ecrivons un prochain test!
Sixième test
Les facteurs premiers de 8 sont une liste de 3 valeurs : 2,2 et 2. Testons ce cas.
le test échoue, le code retourne un tableau de 2 et 4.
Comment nous pouvons fixer ce test avec une seule passe?
class PrimeFactors
{
public static function generate($n)
{
$primes = array();
if ($n > 1) {
while (0 === $n%2) { // <=== !!
$primes[] = 2;
$n /= 2;
}
if ($n > 1) {
$primes[] = $n;
}
}
return $primes;
}
}
Remplacer le if avec un while! C’est étonnant à chaque fois 🙂
Continuons avec un prochain test.
Septième test
Voyons voir pour le cas du nombre 9 dont les facteurs premiers sont 3 et 3
Le test échoue puisque nous ne gérons pas encore la division par 3. Essayons de fixer ceci.
Nous avons un peu de travail à faire. Nous allons y aller petit à petit en s’assurant que c’est toujours le même test qui échoue, jusqu’à ce qu’on arrive à faire passer le test.
Commençons par transformer la valeur spécifique de 2 en une variable $candidate :
class PrimeFactors
{
public static function generate($n)
{
$primes = array();
if ($n > 1) {
$candidate = 2;
while (0 === $n%$candidate) {
$primes[] = $candidate;
$n /= $candidate;
}
if ($n > 1) {
$primes[] = $n;
}
}
return $primes;
}
}
C’est toujours le même test qui échoue. Avant de continuer, faisons un petit cleaning.
Place au refactoring
Essayons de revoir un peu le code pour améliorer la situation des deux if qui font la même chose.
Nous pouvons sortir maintenant le if imbriqué comme ceci :
class PrimeFactors
{
public static function generate($n)
{
$primes = array();
if ($n > 1) {
$candidate = 2;
while (0 === $n%$candidate) {
$primes[] = $candidate;
$n /= $candidate;
}
}
if ($n > 1) {
$primes[] = $n;
}
return $primes;
}
}
et aussi l’initialisation de la variable $candidate en dehors du if :
class PrimeFactors
{
public static function generate($n)
{
$primes = array();
$candidate = 2;
if ($n > 1) {
while (0 === $n%$candidate) {
$primes[] = $candidate;
$n /= $candidate;
}
}
if ($n > 1) {
$primes[] = $n;
}
return $primes;
}
}
Maintenant que le code est mieux organisé, nous sommes prêts à faire passer le test.
Devinez quoi?
class PrimeFactors
{
public static function generate($n)
{
$primes = array();
$candidate = 2;
while ($n > 1) { // <== !!!!!
while (0 === $n%$candidate) {
$primes[] = $candidate;
$n /= $candidate;
}
$candidate++; // <==
}
if ($n > 1) {
$primes[] = $n;
}
return $primes;
}
}
Même passe! if transformé en while et bang! Quelle élégance!! Encore mieux, maintenant le if laid et bizarre peut sauter :
class PrimeFactors
{
public static function generate($n)
{
$primes = array();
$candidate = 2;
while ($n > 1) {
while (0 === $n % $candidate) {
$primes[] = $candidate;
$n /= $candidate;
}
$candidate++;
}
return $primes;
}
}
Le test passe comme par magie!
Mieux encore, Finissons le travail avec un petit refactoring des while en for :
class PrimeFactors
{
public static function generate($n)
{
$primes = array();
for ($candidate =2; $n > 1; $candidate++) {
for (;0 === $n % $candidate;$n /= $candidate) {
$primes[] = $candidate;
}
}
return $primes;
}
}
3 lignes de code si nous ne considérons pas les accolades!
Qu’avez vous à dire sinon que c’est Génial! C’est magique cette affaire de transformations!.
Conclusion
Certains de vous diront que c’est un exemple simple! Mais je trouve toutefois que ceci démontre deux points cruciaux :
– la prémisse des transformations des “if” en “while”. l’une des techniques de transformation que Uncle Bob évoque. Pour plus d’informations voir : L’état actuel de cette prémisse
– Comment faire des petits pas nous emmène à avoir un algorithme simple. Et pour moi, la qualité d’un design réside essentiellement en sa simplicité.
À une prochaine Kata!!