Test Driven Developement – Kata : Facteurs premiers (Prime Factors)

tdd-kata-primefactors
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

<?php

class PrimeFactorsTest extends PHPUnit_Framework_TestCase
{
}

et s’assurer que notre PHPUnit nous affiche bien un warning qui ressemble a ceci :

1) Warning
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.

<?php

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.

<?php

class PrimeFactors
{
    public static function generate($n)
    {
        return array();
    }
}

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 :

    public function testTwo()
    {
        $this->assertSame(array(2), PrimeFactors::generate(2));
    }

Le test échoue, faisons le passer avec un minimum d’effort :

<?php

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.

    public function testThree()
    {
        $this->assertSame(array(3), PrimeFactors::generate(3));
    }

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?

<?php

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.

    public function testFour()
    {
        $this->assertSame(array(2,2), PrimeFactors::generate(4));
    }

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.

<?php

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.

    public function testSix()
    {
        $this->assertSame(array(2,3), PrimeFactors::generate(6));
    }

Ç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.

    public function testEight()
    {
        $this->assertSame(array(2,2,2), PrimeFactors::generate(8));
    }

le test échoue, le code retourne un tableau de 2 et 4.

1) PrimeFactorsTest::testEight
Failed asserting that Array &0 (
    0 => 2
    1 => 4
) is identical to Array &0 (
    0 => 2
    1 => 2
    2 => 2
).

Comment nous pouvons fixer ce test avec une seule passe?

<?php

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

    public function testNine()
    {
        $this->assertSame(array(3,3), PrimeFactors::generate(9));
    }

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 :

<?php

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 :

<?php

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 :

<?php

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?

<?php
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 :

<?php

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 :

<?php

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!!

Anis Berejeb

Anis est avant tout un passioné de l'agilité et du développement. Avec plus de 15 ans dans le domaine du développement web, son expertise combine des connaissances accrues dans l'ensemble des notions partant du développement logiciel jusqu'à l'organisation des équipes dans les environnements agiles à grande échelle.

You may also like...