Mon premier défi : un Dobble generator en TDD

Gildas Garcia
Gildas GarciaApril 07, 2015
#node-js#testing#integration

Je me souviendrais longtemps de mon arrivée chez marmelab et de la période d'intégration qui ne fait que commencer. François m'avait prévenu :

Chaque semaine, tu devras réaliser un projet dans un domaine que tu ne connais pas, avec une techno que tu ne connais pas non plus. Tu vas te planter, c'est normal.

Finalement, j'ai eu un langage que je connaissais presque (ECMAScript6) et un domaine que j'aime et pratique depuis longtemps : les jeux de société et en particulier Dobble. Par contre, je me suis effectivement planté... mais j'ai appris des choses importantes au passage.

Pour ceux qui ne connaissent pas, le principe de Dobble est le suivant :

Chaque joueur a une carte en main et doit trouver avant les autres le seul et unique symbole commun entre sa carte et celle du dessus de la pioche, auquel cas, il ramasse cette carte. Objectif de ce mode de jeu : ramasser plus de cartes que ses copains. Le jeu contient 55 cartes et chaque carte n'a qu'un seul symbole en commun avec chacune des 54 autres. Simple et efficace, je vous conseille vivement ce jeu :)

Le défi est de trouver comment générer un paquet de cartes qui respecte les règles de Dobble en utilisant ECMAScript6 :

  • un symbole ne peut apparaître qu'une fois par carte
  • deux cartes ont toujours exactement un symbole en commun

Il doit être possible de générer ce paquet en spécifiant le nombre de symboles par carte souhaité (2, 8, 42, etc.). Facile! Surtout quand les maths n'ont jamais été votre spécialité...

Hajime !

Première étape, la mise en place du projet. Chez marmelab, il y a des règles à respecter :

  • sur la branche master jamais directement tu ne travailleras
  • la branche master tous les tests toujours passeront
  • pour modifier master, par pull-request tu procéderas
  • chaque pull-request, par un autre membre de l'équipe revue sera
  • chaque pull-request, par un autre membre de l'équipe fusionnée dans master sera

Je commence par installer nvm sur ma nouvelle machine (un sympathique Dell XPS 13 édition 2015 que je recommande par ailleurs), j'initialise un nouveau projet git, j'installe mocha, babel et debug. C'est parti, commençons par les cartes.

Les tests :

let assert = require("assert");
let Card = require("../lib/Card");

describe("Card", () => {
  describe("constructor()", () => {
    it("should throw an error when called with no values", () => {
      assert.throws(() => new Card());
    });

    it("does not accept something that is not an array", () => {
      assert.throws(() => new Card(42));
    });

    it("accepts an array of values", () => {
      let card = new Card(["a", "b", "c"]);
      assert.equal(3, card.symbols.length);
    });
  });

  describe("isValid()", () => {
    it("should return true when initialized with unique symbols", () => {
      let card = new Card(["A", "B", "C", "D", "E", "F", "G", "H", "I"]);
      assert.ok(card.isValid());
    });

    it("should return false when initialized with non unique symbols", () => {
      let card = new Card(["B", "C", "A", "D", "A", "F", "G", "H", "A"]);
      assert.ok(!card.isValid());
    });
  });
});

L'implémentation :

let debug = require("debug")("Card");

class Card {
  constructor(symbols) {
    if (symbols == null || !(symbols instanceof Array)) {
      throw new Error(
        "You must specify the card symbols as an array: new Card(['x', 'y', 'z']);"
      );
    }

    this._symbols = symbols;
  }

  /** Returns a copy of the card's symbols */
  get symbols() {
    return this._symbols.slice();
  }

  isValid() {
    if (this._symbols == null || !(this._symbols instanceof Array)) {
      return false;
    }

    return !this._symbols.find((symbol1, index1) => {
      return this._symbols.find((symbol2, index2) => {
        return index1 !== index2 && symbol1 === symbol2;
      });
    });
  }

  toString() {
    return this._symbols.join("\t");
  }
}

module.exports = Card;

Jusqu'ici tout va bien, je commit/push et crée une pull request.

1er commentaire :

you're missing a makefile

Pourquoi ? Nouvelle règle marmelab :

  • aucune connaissance de ton projet chez tes collègues / utilisateurs / clients / toi_même_dans_5_ans tu n'assumeras

Quel que soit la techo employée, n'importe qui doit pouvoir travailler/vérifier ton projet avec

  • make install
  • make test

Oui, c'est du bons sens...


.PHONY: test

install:
  npm install

test:
  @NODE_ENV=test ./node_modules/mocha/bin/mocha --compilers js:babel/register

On remarque aussi ici l'utilisation d'un mocha local au projet. Ma 1ère version utilisait mocha installé globalement... Nouvelle règle marmelab (toujours du bon sens) :

  • aucun environnement chez tes collègues / utilisateurs / clients / toi_même_dans_5_ans tu n'assumeras

Round 2 : les paires

Les tests :

let assert = require("assert");
let Card = require("../lib/Card");
let Pair = require("../lib/Pair");

describe("Pair", () => {
  describe("constructor()", () => {
    it("should throw an error when instanciated with no arguments", () => {
      assert.throws(() => new Pair());
    });

    it("should throw an error when instanciated with only one card", () => {
      assert.throws(() => new Pair(new Card([1, 2])));
    });

    it("should throw an error when instanciated with non Card arguments", () => {
      assert.throws(() => new Pair(1, 2));
    });
  });

  describe("isValid()", () => {
    it("should return false when any card is not valid", () => {
      let card1 = new Card(["A", "B", "C", "D", "E", "F", "G", "H", "I"]);
      let card2 = new Card(["A", "A", "K", "L", "M", "N", "O", "P", "Q"]);
      let pair = new Pair(card1, card2);
      assert.ok(!pair.isValid());
    });

    it("should return true when cards have only one identical symbol", () => {
      let card1 = new Card(["A", "B", "C", "D", "E", "F", "G", "H", "I"]);
      let card2 = new Card(["I", "J", "K", "L", "M", "N", "O", "P", "Q"]);
      let pair = new Pair(card1, card2);
      assert.ok(pair.isValid());
    });

    it("should return false when cards have more than one identical symbol", () => {
      let card1 = new Card(["A", "B", "C", "D", "E", "F", "G", "H", "I"]);
      let card2 = new Card(["A", "B", "K", "L", "M", "N", "O", "P", "Q"]);
      let pair = new Pair(card1, card2);
      assert.ok(!pair.isValid());
    });

    it("should return false when cards do not have any identical symbol", () => {
      let card1 = new Card(["A", "B", "C", "D", "E", "F", "G", "H", "I"]);
      let card2 = new Card(["J", "K", "L", "M", "N", "O", "P", "Q", "R"]);
      let pair = new Pair(card1, card2);
      assert.ok(!pair.isValid());
    });
  });
});

L'implémentation :

let debug = require("debug")("Pair");
let Card = require("../lib/Card");

class Pair {
  constructor(card1, card2) {
    if (!(card1 instanceof Card) || !(card2 instanceof Card)) {
      throw new Error("Pair must be instantiated with two instances of Card");
    }

    this._card1 = card1;
    this._card2 = card2;
  }

  toString() {
    return `\tCard 1 = ${this._card1} \n\tCard 2 = ${this._card2}`;
  }

  isValid() {
    if (this._card1 == null || !(this._card1 instanceof Card)) {
      return false;
    }

    if (this._card2 == null || !(this._card2 instanceof Card)) {
      return false;
    }

    if (!this._card1.isValid() || !this._card2.isValid()) {
      return false;
    }

    let total = this._card1.symbols.reduce((count, symbolFromCard1) => {
      let found = this._card2.symbols.reduce((count, symbolFromCard2) => {
        let result = symbolFromCard1 === symbolFromCard2;
        debug(`${symbolFromCard1} === ${symbolFromCard2} => ${result}`);

        return result ? ++count : count;
      }, 0);

      return (count += found);
    }, 0);

    return total === 1;
  }
}

module.exports = Pair;

Jusqu'ici c'est facile et ça me permet de prendre en main tranquillement ECMAScript6. C'est déjà plus léger à lire et écrire même si je préfère toujours coffeescript que j'utilise sur quasiment tous mes projets.

Deuxième pull request, quelques allers/retours via commentaires et c'est fusionné. On attaque maintenant le coeur du problème !

Round 3 : le paquet de cartes

J'ai passé presque une journée à tenter plusieurs approches en m'efforçant de ne pas chercher algorithme dobble sur google, sans succès. Je discute avec différents membres de marmelab qui ont déjà réfléchi au problème mais se sont également cassé les dents dessus.

Je finis par me résoudre à chercher si d'autres se sont posé la question et découvre de nombreux articles :

Je finis la journée avec la tête comme une pastèque et sans une seule pull request. Nouvelle règle de Marmelab :

  • tous les jours une pull request tu feras
  • si bloqué plus de 10 mins, de l'aide auprès de tes collègues tu chercheras

Vainqueur : Dobble par KO

Round 4

Le lendemain, je me décide à adapter l'algorithme C++ trouvé la veille en javascript. Après plusieurs tentatives, cela fonctionne pour 2, 3, 4, 6 et 8 symboles par cartes mais pas pour 5, 7, 9 et plus symboles.

Le deck, tests d'abord :

let assert = require("assert");
let Card = require("../lib/Card");
let Deck = require("../lib/Deck");

describe("Deck", () => {
  describe("constructor()", () => {
    it("should throw an error when called with no values", () => {
      assert.throws(() => new Deck());
    });

    it("does not accept anything that is not an array", () => {
      assert.throws(() => new Deck(42));
    });

    it("does not accept an array which contain something else than cards", () => {
      assert.throws(() => new Deck([41, new Card([41, 42])]));
    });

    it("accepts an array of cards", () => {
      let deck = new Deck([new Card(["A", "B"]), new Card(["A", "A"])]);

      assert.equal(2, deck.cards.length);
    });
  });

  describe("isValid()", () => {
    it("should return false when deck is empty", () => {
      let deck = new Deck([]);
      assert.ok(!deck.isValid());
    });

    it("should return false when any card is invalid", () => {
      let card1 = new Card(["A", "B", "C", "D", "E", "F", "G", "H", "I"]);
      let card2 = new Card(["A", "A", "K", "L", "M", "N", "O", "P", "Q"]);
      let deck = new Deck([card1, card2]);

      assert.ok(!deck.isValid());
    });

    it("should return false when any possible pair is invalid", () => {
      let card1 = new Card(["A", "B", "C", "D", "E", "F", "G", "H", "I"]);
      let card2 = new Card(["A", "B", "L", "M", "N", "O", "P", "Q", "R"]);
      let deck = new Deck([card1, card2]);

      assert.ok(!deck.isValid());
    });

    it("should return true when cards and pairs are valid", () => {
      let card1 = new Card(["A", "B", "C", "D", "E", "F", "G", "H", "I"]);
      let card2 = new Card(["A", "K", "L", "M", "N", "O", "P", "Q", "R"]);
      let deck = new Deck([card1, card2]);

      assert.ok(deck.isValid());
    });
  });
});

L'implémentation :

let debug = require("debug")("Deck");
let Card = require("./Card");
let Pair = require("./Pair");

class Deck {
  constructor(cards) {
    if (cards == null) {
      throw new Error("You must specify the cards as an array");
    }

    if (cards.find(card => !(card instanceof Card))) {
      throw new Error("You can only pass an array of cards");
    }

    this.cards = cards;
  }

  isValid() {
    debug(`Deck contains ${this.cards.length} cards`);

    if (this.cards.length == 0) {
      return false;
    }

    if (
      this.cards.find(card => {
        let result = !card.isValid();

        if (result) {
          debug(`card = ${card} is invalid`);
        }

        return result;
      })
    ) {
      return false;
    }

    let invalidPairs = [];
    let invalid = this.cards.filter((card1, indexCard1) => {
      return this.cards.find((card2, indexCard2) => {
        if (indexCard1 !== indexCard2) {
          let pair = new Pair(card1, card2);

          if (!pair.isValid()) {
            invalidPairs.push(pair);

            debug(`invalid pair = \n ${pair}`);
            return true;
          }
        }

        return false;
      });
    });

    if (invalid.length > 0) {
      debug("=".repeat(80));
      debug(`Invalid pairs: ${invalidPairs.length}`);
      invalidPairs.forEach(p => {
        debug(p);
      });
    }

    return invalid.length == 0;
  }

  toString() {
    let result = `Deck of ${this.cards.length} cards \n`;
    result += "-".repeat(80);
    result += `\n`;

    this.cards.forEach(card => {
      result += `${card}\n`;
    });

    return result;
  }
}

module.exports = Deck;

La génération de symboles par défaut, les tests :

let assert = require("assert");
let generateSymbol = require("../lib/generateSymbol");

describe("generateSymbol", () => {
  it("should throw an error when called anything but a number", () => {
    assert.throws(() => generateSymbol());
    assert.throws(() => generateSymbol("g"));
    assert.throws(() => generateSymbol(null));
    assert.throws(() => generateSymbol([]));
  });

  it("should returns a Set of 10 symbols when called with 10", () => {
    let symbols = generateSymbol(10);
    assert.ok(symbols instanceof Set);
  });

  it("should returns a Set of 20 symbols when called with 20", () => {
    let symbols = generateSymbol(20);
    assert.ok(symbols instanceof Set);
  });
});

L'implémentation:

let debug = require("debug")("generateSymbols");

let generateSymbols = number => {
  if (typeof number != "number") {
    throw new Error("You must specify the number of symbols to generate.");
  }

  let symbols = new Set();

  for (let i = 0; i < number; i++) {
    symbols.add("S" + i);
  }

  return symbols;
};

module.exports = generateSymbols;

Et enfin, la génération du deck pour laquelle j'essaie d'appliquer certaines bonnes pratiques apprises en chemin comme par exemple dans l'article de François From Objects To Functions: Service Closures.

Les tests :

let assert = require("assert");
let Card = require("../lib/Card");
let Pair = require("../lib/Pair");
let Deck = require("../lib/Deck");
let deckGenerator = require("../lib/deckGenerator");
let debug = require("debug")("deckGenerator");

describe("deckGenerator()", () => {
  it(`should return a function when called with no arguments`, () => {
    let generateDeck = deckGenerator();
    assert.equal("function", typeof generateDeck);
  });

  it(`should throw an error when called with anything other than a function`, () => {
    assert.throws(() => deckGenerator(42));
    assert.throws(() => deckGenerator("42"));
    assert.throws(() => deckGenerator([42]));
  });

  describe("deckGenerator().generateSymbol", () => {
    it(`should return a function when called without arguments`, () => {
      let generateDeck = deckGenerator();
      assert.equal("function", typeof generateDeck.generateSymbol);
    });
  });

  describe("deckGenerator()()", () => {
    let tests = [
      {
        dimensions: 2,
        expectedCards: 3,
        expectedSymbols: 2,
      },
      {
        dimensions: 3,
        expectedCards: 7,
        expectedSymbols: 3,
      },
      {
        dimensions: 4,
        expectedCards: 13,
        expectedSymbols: 4,
      },
      {
        dimensions: 5,
        expectedCards: 21,
        expectedSymbols: 5,
      },
      {
        dimensions: 6,
        expectedCards: 31,
        expectedSymbols: 6,
      },
      {
        dimensions: 7,
        expectedCards: 43,
        expectedSymbols: 7,
      },
      {
        dimensions: 8,
        expectedCards: 57,
        expectedSymbols: 8,
      },
      {
        dimensions: 9,
        expectedCards: 73,
        expectedSymbols: 9,
      },
    ];

    tests.forEach(test => {
      it(`should return a deck with cards containing ${
        test.expectedSymbols
      } when called with ${test.dimensions}`, () => {
        let generateDeck = deckGenerator();
        let deck = generateDeck(test.dimensions);

        debug(`${deck}`);

        let cards = deck.cards;

        let invalidCards = cards.filter(c => {
          return c.symbols.length != test.expectedSymbols;
        });

        assert.equal(
          0,
          invalidCards.length,
          `Found ${invalidCards.length} invalid cards\n${invalidCards.join(
            "\n"
          )}`
        );
      });
    });

    tests.forEach(test => {
      it(`should return a deck with ${
        test.expectedCards
      } cards when called with ${test.dimensions}`, () => {
        let generateDeck = deckGenerator();
        let deck = generateDeck(test.dimensions);

        debug(`${deck}`);

        let cards = deck.cards;

        assert.equal(
          test.expectedCards,
          cards.length,
          `Expected ${test.expectedCards} cards, found ${cards.length}`
        );
      });
    });

    tests.forEach(test => {
      it(`should return a deck with valid cards and pairs when called with ${
        test.dimensions
      }`, () => {
        let generateDeck = deckGenerator();
        let deck = generateDeck(test.dimensions);

        debug(`${deck}`);

        assert.ok(deck.isValid(), "Deck is invalid");
      });
    });
  });
});

L'implémentation :

let debug = require("debug")("deckGenerator");
let Card = require("./Card");
let Deck = require("./Deck");
let generateSymbol = require("./generateSymbol");

let _computeMinfactor = dimensions => {
  let minFactor = dimensions;
  let poweredDimensions = 1 + Math.floor(Math.pow(dimensions, 0.5));

  debug(`poweredDimensions = ${poweredDimensions}`);
  for (let i = 2; i < poweredDimensions; ++i) {
    if (dimensions % i == 0) {
      minFactor = i;
      break;
    }
  }

  return minFactor;
};

let deckGenerator = (generateSymbolFunc = generateSymbol) => {
  if (typeof generateSymbolFunc != "function") {
    throw new Error("generateSymbolFunc must be a function.");
  }

  let generator = (dimensions = 8) => {
    let dimensionsForComputations = dimensions - 1;
    debug(`dimensions: ${dimensions}`);
    if (typeof dimensions != "number") {
      throw new Error("dimensions must be a number.");
    }

    let numberOfDifferentCards = dimensions * dimensions - dimensions + 1;
    let numberOfDifferentSymbols =
      ((dimensions - 1) * (numberOfDifferentCards - 1)) / dimensions +
      dimensions;

    let symbols = Array.from(generateSymbolFunc(numberOfDifferentSymbols));
    let cards = [];
    let minFactor = _computeMinfactor(dimensionsForComputations);

    debug(`minFactor: ${minFactor}`);
    debug(`numberOfDifferentCards: ${numberOfDifferentCards}`);
    debug(`symbols (${numberOfDifferentSymbols}): ${Array.from(symbols)}`);

    for (let i = 0; i < dimensionsForComputations; ++i) {
      let cardSymbols = [];

      for (let j = 0; j < dimensionsForComputations; ++j) {
        cardSymbols.push(symbols[i * dimensionsForComputations + j]);
      }
      cardSymbols.push(
        symbols[dimensionsForComputations * dimensionsForComputations]
      );
      let card = new Card(cardSymbols);
      debug(`card: ${card}`);
      cards.push(card);
    }

    for (let i = 0; i < dimensionsForComputations; ++i) {
      for (let j = 0; j < dimensionsForComputations; ++j) {
        let cardSymbols = [];
        for (let k = 0; k < dimensionsForComputations; ++k) {
          cardSymbols.push(
            symbols[
              k * dimensionsForComputations +
                ((j + i * k) % dimensionsForComputations)
            ]
          );
        }

        cardSymbols.push(
          symbols[dimensionsForComputations * dimensionsForComputations + 1 + i]
        );
        let card = new Card(cardSymbols);
        debug(`card: ${card}`);
        cards.push(card);
      }
    }

    let cardSymbols = [];

    for (let i = 0; i < minFactor + 1; ++i) {
      cardSymbols.push(
        symbols[dimensionsForComputations * dimensionsForComputations + i]
      );
    }

    if (cardSymbols.length < dimensions) {
      for (let i = cardSymbols.length; i < dimensions; ++i) {
        cardSymbols.push(
          symbols[dimensionsForComputations * dimensionsForComputations + i]
        );
      }
    }

    let card = new Card(cardSymbols);
    debug(`card: ${card}`);
    cards.push(card);

    return new Deck(cards);
  };

  generator.generateSymbol = newGenerateSymbolFunc => {
    // getter if no arguments
    if (arguments.length == 0) return generateSymbolFunc;

    generateSymbolFunc = newGenerateSymbolFunc;
    return generator;
  };

  return generator;
};

module.exports = deckGenerator;

Conclusion

Le code est disponible sur GitHub, en MIT : marmelab/dobble. Le générateur fonctionne donc pour les dimensions 2, 3, 4, 6 et 8, mais pas pour les dimensions 5, 7 et 9.

3 jours seulement et j'ai appris certaines choses que j'appliquerai dès que possible sur mes projets existants. Je retiens particulièrement l'utilisation du makefile qui évite les maux de tête quand on reprend un projet après une longue période sans y toucher.

J'ai aussi pu appliquer la programmation fonctionnelle pour obtenir un code propre, lisible et extensible, et apprécier quelques nouveautés d'ECMAScript6.

J'attends maintenant avec impatience le prochain défi qui me demandera probablement d'apprendre un nouveau langage.

Did you like this article? Share it!