De Python à PHP 7 : L'algorithme du jeu Dobble

« A quelle sauce vais-je être mangé ? »

C'est la question que je me suis posée toute une semaine, jusqu'à ce lundi 26 octobre quand François m'a accueilli dans les locaux de marmelab pour mon premier jour. J'étais à la fois excité et inquiet !

Marmelab est bien connu à Nancy pour être composée de pointures et j'ai vite compris que j'allais devoir faire mes preuves dans l'équipe.

Chose que l'on m'a confirmé dix minutes après avoir passé la porte : « Tu n'as pas fait de PHP depuis la version 5.3 ? Très bien ! Alors tu vas coder, en PHP 7, un petit jeu très simple. Tu connais Dobble ? Tu as cinq jours. »

De Python à PHP

J'étais très loin de m'imaginer à quel point cette cinquantaine de cartes avec huit images par carte allaient m'arracher les cheveux et me donner une migraine.

Alors je suis parti confiant. Symfony fournit un composant console très facile à utiliser, mes souvenirs de la syntaxe PHP me reviennent doucement et les tests unitaires ne sont pas bien compliqués avec PHPUnit.

Ce sera donc assez similaire à Django que je maîtrise parfaitement. Une semaine, c'est large ! Le plus difficile, j'imagine alors, est de faire tout cela en PHP 7 qui est très récent.

Ma première question est de savoir si Travis, le service d'intégration continue qu'utilise marmelab est compatible avec cette version. Et je tombe rapidement sur un tweet qui me confirme que c'est bien le cas. Parfait !

Il ne me reste plus alors qu'à lancer un docker où je pourrai exécuter mon code PHP sans devoir installer la nouvelle version en local.

docker run --rm -it -v $(pwd):/app coderstephen/php7 php -h

Une fois l'alias dans mon bashrc, les commits commencent à fuser.

PHP 7 ressemble de plus en plus à Python, les namespaces peuvent être comparés aux imports, les fonctions natives sont nombreuses et verbeuses mais on y trouve son compte, entre array_map et array_unique.

La commande se porte bien, les classes sont là, les var_dump aidant, je prends mon temps pour tout inclure dans mes tests unitaires, jusqu'à la méthode de classe qui fait un simple "count" en pensant que cela impressionnerait quelqu'un que mon code soit couvert à 100%.

<?php
public function testDeckConstructorAcceptsEmpty()
{
    $deck = new Deck();
    $this->assertEmpty($deck->getCards());
}

public function testDeckConstructorAcceptsValidCards($cards)
{
    $deck = new Deck($cards);
    $this->assertEquals($deck->getCards(), $cards);
}

Seule ombre au tableau, la syntaxe PHP qui doit respecter les PSR (PHP Standards Recommendations), l'équivalent de PEP8 en Python. Ici php-cs-fixer m'a été d'une grande aide.

Me voila déjà avec une classe Deck et une classe Card qui interagissent bien entre elle, testées, validées ... Nous sommes mercredi, je dois rendre le projet vendredi et je me pose seulement la question : « Mais comment je vais générer mes cartes ? »

L'algorithme de Dobble

Aïe. Voila où l'on a voulu m'amener. Au fur et à mesure que mes recherches me ramenaient sur des articles universitaires et autres théories plus mathématiques les unes que les autres, j'ai compris que ce ne serait pas une mince affaire. Mieux vaut tard que jamais.

Ni une, ni deux, je me suis empressé de chercher une solution maison à ce problème relativement simple. Les règles pour générer un jeu de cartes à la Dobble sont très faciles :

• Chaque carte est unique
• Toutes les cartes ont le même nombre de symboles
• Chaque carte a une et une seule paire de symboles en commun, avec TOUTES les autres cartes

Après une solution qui consistait à générer une première carte et à itérer sur tous ses symboles pour créer les cartes suivantes (voir schéma incompréhensible ci-dessus), j'ai fini par me pencher à nouveau sur des articles universitaires en mathématiques et notamment celui que m'a conseillé Jonathan rédigé par un professeur de l'Université de Lyon, modestement nommé « Plans projectifs, arithmétique modulaire et Dobble ».

Sans entrer dans les détails, ce dernier explique de manière assez claire comment les propriétés particulières des plans projectifs réels et des corps d'entiers modulo ont été utilisées par le créateur de Dobble, Asmodée.

Après de longues heures à éplucher son article de fond en comble, j'ai enfin pu comprendre la manière de générer quelques maudites cartes avec des propriétés semblables au jeu Dobble et rendre mon projet dans les temps !

Il est par ailleurs disponible en open-source sur un repo Github de marmelab.

<?php
/**
 * @param $modulo Integer modulo
 * @param $matrix Matrix of unique values for given integer modulo
 * @param $infinity List of points at infinity for given integer modulo
 * @param $a Draw a line for f(x) = ax + b
 * @param $b Draw a line for f(x) = ax + b
 * @param $f For $f = 5, draw a line for f(5). If given, $a and $b will be ignored
 * @return array All points through which pass the line
 */
private function fetchLine($modulo, $matrix, $infinity, $a, $b, $f = null)
{
    $coords = []; // Coordinates of all points
    $points = [];
    for($i = 0; $i < $modulo; ++$i) {
        if ($f === null) {
            // f(x) = ax + b
            // We apply the modulo operation to results because
            // There is not integers but modulo integers
            $x = $i % $modulo;
            $y = ($a * $i + $b) % $modulo;
        } else {
            $x = $f;
            $y = $i % $modulo;
        }
        // Add the calculated coordinates to the list
        array_push($coords, [$x, $y]);
    }
    // Fetching the value for all points
    foreach($coords as $coord) {
        $x = $coord[0];
        $y = $coord[1];
        array_push($points, $matrix[$y][$x]);
    }
    // Add the last point at infinity
    if ($f === null) {
        array_push($points, $infinity[$a + 1]);
    } else {
        array_push($points, $infinity[0]);
    }
    return $points;
}

Conclusion

Je m'en suis sorti de justesse, j'ai commis beaucoup d'erreurs qui m'ont fait perdre un temps précieux : sous-évaluer la masse de travail, passer trop de temps sur des futilités (la génération du Deck n'a pas été testée, alors qu'un simple count si !), j'ai choisi la solution de facilité en travaillant mon algo en Python avant de l'implémenter en PHP, entre autres.

Mais au final, je suis assez fier de ce que j'ai accompli, et j'ai rendu mon projet à temps ! Même si, à mon avis, on attendait plus de moi de prendre de bonnes habitudes que de finir le projet à 100% pour cette première semaine qui a confirmé ce que je pensais de marmelab, et j'en suis d'autant plus content d'y travailler.

Au moment où je vous écrit, je suis déjà en retard pour le second projet que l'on m'a confié, une application en NodeJS qui utilise l'API Github, alors que je n'en ai évidemment jamais fait et que je suis nul en JavaScript !

Je vous donne donc rendez-vous la semaine prochaine, pour savoir si mon cerveau aura tenu le coup.

Crédits: CNRS, Marc Deléglise