Kata Digital Romain

Laisser une réponse

Pour m’amuser, je me suis intéressé à un exercice qu’on demande souvent en entretien pour tester les réflexes des candidats : la conversion d’un nombre dans sa représentation romaine, en Java.

Le sujet de cet exercice est relativement simple. On prend un nombre et on doit calculer sa représentation romaine.

Pour rappel, la représentation romaine se base sur une série de lettres : I (1), V (5), X (10), L (50), C (100), D (500) et M (1000). Pour le chiffre avant l’unité, on a une règle spéciale : IV (4), IX (9), XL (40), etc. Ainsi, on écrira « CCCLXIX » pour « 369 » et « MMDCCLI » pour « 2751 »…

Pour une explication plus complète, je vous renvoie vers les liens suivants :

Alors, comment prendre cette affaire quand on est en entretien ? en temps limité, avec quelqu’un qui vous ausculte… Garder son calme pour commencer. Ça c’est toujours une bonne idée. Respirer. Faire les choses bien, même si ça prend du temps.

Note : Si le commercial qui vous interroge s’impatiente en vous voyant bien faire, le mieux est encore de rassembler vos affaires et d’aller voir ailleurs, par exemple dans une société qui privilégie les bonnes pratiques et la qualité. Claquez la porte, ça fait du bien et ça fait comprendre au commercial de ne pas rappeler ;-) Hummm Petit guide de survie en SSII… Si au contraire la personne semble intéressée par la suite, voire même vous fait un clin d’œil, c’est bon signe. Continuez…

Etape 1 : Péfléchir, un peu…


D’abord faire connaissance avec le sujet. Pour ma part je connaissais déjà les chiffres romains mais seulement sur l’horloge de ma grand mère. D’ailleurs, sur son horloge, le « 4 » est représenté par « IIII » pour ne pas le confondre avec le « 6 » qui est représenté par « VI ». En effet « IV » et « VI » sont symétriques et risquent de tromper le lecteur… Mais oublions ce détails pour nous concentrer sur le sujet.

Je crois que c’est assez simple. Il y a des exemples et pas vraiment de piège. Je note toutefois que ce système ne permet pas de représenter le zéro (il y a en réalité un moyen mais c’est hors sujet) et encore moins les chiffres négatifs. Je devine rapidement que le nombre le plus grand sera représenté par « MMM DCCC LXXX VIII » (3888).

Edit : je crois que je viens de dire une bêtise. On dire que c’est sous la pression… En fait, je devine qu’on peut représenter « 3999 » avec la séquence « MMM CM XC IX ». Du coup, il faudra modifier le reste du code pour tenir compte de cette limite. Mais l’idée reste la même.

Etape 2 : Poser le problème, faire du TDD, des tests…

Vous savez que j’ai proposé 3T (Tests en Trois Temps) comme une alternative aux TDD. On va donc s’y prendre doucement et de façon mécanique.

Temps 1 : l’interface

D’abord, je rassemble toutes les informations et je crée une interface (ou une simple classe) dans laquelle je vais mettre tout ça. Voici un premier jet qui devrait largement suffire dans le temps limité d’un entretien :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Traducteur specifique a la representation romaine d'un nombre.
 *
 * Les valeurs simples sont : I (1), V (5), X (10), L (50), C (100), D (500) et
 * M (1000).
 *
 * Les valeurs "speciales" sont : IV (4), IX (9), XL (40), etc.
 *
 * Quelques exemples : <br />
 * - CCCLXIX = CCC LX IX = 369 <br />
 * - MMDCCLI = MM DCC LI = 2751
 *
 * La valeur minimale est dont 1 (I) et la valeur maximale dans ce systeme est
 * donc 3888 (MMMDCCCLXXXVIII).
 *
 * @author Thierry
 *
 */
public interface TraducteurRomain {

    /**
     * Calcule la valeur associe à une representation romain d'un nombre.
     *
     * @param romain
     *            Un nombre romain comme VIII (8).
     * @return La valeur numerique (ie. digitale) associee a la representation
     *         romaine.
     * @throws IllegalArgumentException
     *             si la representation romain est nulle ou invalide.
     */
    int romainToDigital(final String romain);

    /**
     * Calcule la representation romain d'un nombre.
     *
     * @param digital
     *            Un nombre digital comme 8 (VIII).
     * @return La representation en chiffres romains du nombre passe en
     *         parametre.
     * @throws IllegalArgumentException
     *             si le nombre est zero, negatif ou superieur aux possibilites
     *             de representation romain (ie. 9999).
     */
    String digitalToRomain(final int digital);

}

A ce stade, je n’essaie même pas (ie. je m’interdit) de penser à une solution. Je me concentre sur l’ordre des choses.

Pour bien faire, je crée une implémentation par défaut :

1
2
3
4
5
6
7
8
9
10
11
12
13
public class DefaultTraducteurRomain implements TraducteurRomain {

    @Override
    public int romainToDigital(String romain) {
        throw new UnsupportedOperationException("Cette fonction n'est pas encore disponible.");
    }

    @Override
    public String digitalToRomain(int digital) {
        throw new UnsupportedOperationException("Cette fonction n'est pas encore disponible.");
    }

}

Note : J’aurais pu également tout mettre dans la classe directement mais je préfère vraiment les interfaces.

Bien, je pense que le plus gros du travail est fait alors qu’on n’a écrit aucun test en encore moins codé l’application. En tous cas, j’ai le sentiment que le travail d’un ingénieur s’arrête ici. Dans la suite, je prendrai juste la casquette de développeur.

Temps 2 : les tests

Je vais maintenant écrire des tests. N’oubliez pas qu’un gars m’observe car je fais comme si j’étais en entretien. J’ai de nombreux cas de tests qui sont proposés dans l’interface. Par lequel commencer ? Hummm. Chacun est libre de choisir en fonction de ses préférence. Pour ma part, faute de mieux je commence par le début…

Il s’agit donc de tester la « calculette » avec des valeurs. Pour cela je vais utiliser JUnit (ou un équivalent car ça ne fait pas grande différence sur papier durant un RdV). Je commence par créer une classe de test. Pour le nom je reprend simplement celui de la classe à tester et j’ajoute « Test » à la fin, comme une convention :

1
2
3
public class DefaultTraducteurRomainTest {

}

Je déclare ensuite ma calculette comme variable. Au passage je la déclare en tant qu’interface et non en tant que classe :

1
2
3
public class DefaultTraducteurRomainTest {
    private static TraducteurRomain traducteur;
}

Et puis je fais une méthode annotée « @BeforeClass » histoire d’initialiser une bonne fois pour toute. Ici pas la peine de réinitialiser la calculette à chaque test ; ça serait vraiment bizarre si un calcul dépendait du précédent…

1
2
3
4
5
6
7
8
public class DefaultTraducteurRomainTest {
    private static TraducteurRomain traducteur;

    @BeforeClass
    public static void doBeforeClass() {
        traducteur = new DefaultTraducteurRomain();
    }
}

Ma classe de test est maintenant prête. Je vais pouvoir passer à la suite. A titre personnel, j’aime bien vérifier que ça fonctionne à l’aide d’un test bidon, juste pour voir si tout est bien installé (au passage ça m’a été bien utile lors de l’écriture de ce billet) :

1
2
3
4
@Test
public void testBidon() {
    assertFalse(1 == 2);
}

Bref, je vais commencer par tester si ça renvoie bien « I » quand je demande « 1 ». Je vais utiliser pour cela le formalisme AAA (Arrange Act Assert) conseillé par 3T :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Test la traduction d'un digital.
 *
 * PARAM digital = 1
 * RESULT I
 */
@Test
public void testTraductionOf1() {
    // Arrange
    final int digital = 1;
    final String expected = "I";
   
    // Act
    final String romain = traducteur.digitalToRomain(digital);
   
    // Assert
    Assert.assertEquals(expected, romain);
}

Je prend soin de faire un peu de doc.

Je passe maintenant à la suite, en prenant comme ça vient. Je vais maintenant tester que la traduction de « 5 » est bien « V ». Je découvre vite que je vais faire la même chose et j’en profite pour factoriser :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Test la traduction d'un digital.
 *
 * PARAM digital = 1 <br />
 * RESULT I
 */
@Test
public void testTraductionOf1() {
    // Arrange
    final int digital = 1;
    final String expected = "I";

    // Act and Assert
    doTest(digital, expected);
}

/**
 * Test la traduction d'un digital.
 *
 * PARAM digital = 5 <br />
 * RESULT V
 */
@Test
public void testTraductionOf5() {
    // Arrange
    final int digital = 5;
    final String expected = "V";

    // Act and Assert
    doTest(digital, expected);
}

Avec, bien entendu :

1
2
3
4
5
6
7
8
private void doTest(final int digital, final String expected) {

    // Act
    final String romain = traducteur.digitalToRomain(digital);

    // Assert
    Assert.assertEquals(expected, romain);
}

Evidemment, vous l’aurez compris, je risque de faire ça pour toutes les valeurs. Autant travailler directement avec des listes :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Test la traduction d'une liste de digitaux.
 *
 * Les valeurs simples sont : I (1), V (5), X (10), L (50), C (100), D (500)
 * et M (1000).
 *
 * PARAM digital = {1, 5, 10, 50, 100, 500, 1000} <br />
 * RESULT {"I", "V", "X", "L", "C", "D", "M"}
 */
@Test
public void testListe() {
    // Arrange
    final int[] digitals = { 1, 5, 10, 50, 100, 500, 1000 };
    final String[] expecteds = { "I", "V", "X", "L", "C", "D", "M" };

    // Act and Assert
    doTestListes(digitals, expecteds);
}

avec :

1
2
3
4
5
6
7
8
private void doTestListes(final int[] digitals, final String[] expecteds) {

    // Pas besoin de tester les tests eux-memes...

    for (int i = 0; i < digitals.length; i++) {
        doTest(digitals[i], expecteds[i]);
    }
}

Je peux faire pareil avec les autres valeurs proposées. J'aime bien ne pas tout mettre dans le même test, surtout quand je sens qu'il peut y avoir un loup (même s'il est bien caché, le loup) :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Test la traduction d'une liste de digitaux speciaux.
 *
 * PARAM digital = {4, 9, 40} <br />
 * RESULT {"IV", "IX", "XL"}
 */
@Test
public void testListeSpeciale() {
    // Arrange
    final int[] digitals = { 4, 9, 40 };
    final String[] expecteds = { "IV", "IX", "XL" };

    // Act and Assert
    doTestListes(digitals, expecteds);
}

/**
 * Test la traduction d'une liste de digitaux pris dans les exemples.
 *
 * PARAM digital = {369, 2751, 3888} <br />
 * RESULT {"CCCLXIX", "MMDCCLI", "MMMDCCCLXXXVIII"}
 */
@Test
public void testListeExemples() {
    // Arrange
    final int[] digitals = { 369, 2751, 3888 };
    final String[] expecteds = { "CCCLXIX", "MMDCCLI", "MMMDCCCLXXXVIII" };

    // Act and Assert
    doTestListes(digitals, expecteds);
}

Pour finir, il reste les cas interdits, càd pour les nombres négatifs ou hors capacité :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Test la traduction d'un digital négatif.
 *
 * PARAM digital = -1 <br />
 * RESULT IllegalArgumentException
 */
@Test(expected = IllegalArgumentException.class)
public void testTraductionOfNegatif() {
    // Arrange
    final int digital = -1;
    final String expected = null;

    // Act and Assert
    doTest(digital, expected);
}

/**
 * Test la traduction d'un digital nul.
 *
 * PARAM digital = 0 <br />
 * RESULT IllegalArgumentException
 */
@Test(expected = IllegalArgumentException.class)
public void testTraductionOfZero() {
    // Arrange
    final int digital = 0;
    final String expected = null;

    // Act and Assert
    doTest(digital, expected);
}

/**
 * Test la traduction d'un digital trop grand.
 *
 * PARAM digital = 9999 <br />
 * RESULT IllegalArgumentException
 */
@Test(expected = IllegalArgumentException.class)
public void testTraductionOf9999() {
    // Arrange
    final int digital = 9999;
    final String expected = null;

    // Act and Assert
    doTest(digital, expected);
}

Note : Je préfère séparer ces trois derniers cas.

A ce stade, tous les tests doivent être en rouge et c’est bien ce qu’on souhaite

Temps 3 : le code

Je peux enfin coder, même si ça m’étonnerait que le commercial m’ait laissé aller jusque là (ma pause déjeuner y est passé en entier). Dans la suite, il « suffit » de se laisse guider par les tests qui ont été écrits. Ces tests donnent d’ailleurs de très bonnes indications…

Dans quel ordre écrire tout ça ? Faute de mieux dans l’ordre d’arrivée des tests. Ici je remarque une structure dans les informations et je vais l’exploiter. Mais avant cela, je vais me débarrasser des cas aux limites :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class DefaultTraducteurRomain implements TraducteurRomain {

    @Override
    public int romainToDigital(String romain) {
        throw new UnsupportedOperationException("Cette fonction n'est pas encore disponible.");
    }

    @Override
    public String digitalToRomain(int digital) {
       
        if(digital <= 0) {
            throw new IllegalArgumentException("Ca ne fonctionne pas pour les nombres negatifs.");
        }
       
        if(3888 < digital) {
            throw new IllegalArgumentException("Le nombre demande est hors limite.");
        }
       
        throw new UnsupportedOperationException("Cette fonction n'est pas encore disponible.");
    }
}

Pour la suite, je vais avoir du mal à faire passer chaque test un par un sans jouer à l'idiot. Une méthode qui me vient tout de suite à l'esprit est de séparer chaque digit. Commençons doucement tout de même avec les petites valeurs :

1
2
3
4
public class DefaultTraducteurRomain implements TraducteurRomain {

    private final static String[][] CORRESPONDANCES =
        {{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}};

Il reste à exploiter ce tableau :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
@Override
public String digitalToRomain(int digital) {

    if (digital <= 0) {
        throw new IllegalArgumentException("Ca ne fonctionne pas pour les nombres negatifs.");
    }

    if (3888 < digital) {
        throw new IllegalArgumentException("Le nombre demande est hors limite.");
    }

    final StringBuilder sb = new StringBuilder();
    addRomainToResult(digital, 0, sb);
    return sb.toString();
}

private void addRomainToResult(final int digital, final int rang, final StringBuilder sb) {

    final int digit = digital % 10;

    if (10 <= digital) {
        addRomainToResult(digital / 10, rang + 1, sb);
    }

    final String trad = CORRESPONDANCES[rang][digit];
    sb.append(trad);
}

Je fais ça de manière récursive car c'est ce qu'il me vient à l'esprit en premier. Rien n’empêchera d'améliorer ça plus tard. Cela dit, pour des valeurs maximales de "3888", je ne vais surement pas y consacrer beaucoup de temps, encore moins durant l'entretien.

Un certain nombre de tests devraient maintenant être verts. Pour finir, il suffit de compléter le tableau :

1
2
3
4
5
    private final static String[][] CORRESPONDANCES = { //
        { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" }, //
        { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" }, //
        { "","C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "DM" }, //
        { "","M", "MM", "MMM", "", "", "", "", "", "" } };

Tout est maintenant vert et je peux légitimement penser que j’ai fini.

Etape 3 : Expliquer tout ça au commercial

Bon, là ça dépend de qui vous avez en face de vous. S’il a réussi à tout suivre jusque là, c’est bon signe. Sinon, bonne chance. Le reste dépend de vous. Faire un beau sourire ; ça aidera…

En raison des nombreux problèmes de spam sur les blog de Developpez.com, les commentaires sont fermés mais vous pouvez me répondre par email ou sur Twitter…

Laisser un commentaire