Cette semaine, c'est Josquin qui vous propose un #KataOfTheWeek : Minimisation des code smells

Briefing du Kata : # Énoncé Félicitation ! Vos dernières réussites au Kata of the week ne sont pas passées inapperçues et vous avez été promu chef de projet.

Votre nouvelle mission est de superviser la réalisation from scratch d'une plateforme web découpée en deux parties : un front et un back. Pour cela, vous disposez d'une équipe de N développeurs fullstack surentrainés … mais flemmards. La partie back et la partie front étant développées de chaque côté de l'open-space, ceux-ci refusent de se lever et de traverser l'open-space, ce qui vous oblige à affecter chaque développeur à seulement une partie de l'application.

En tant qu'ancien dev, vous savez que chaque développeur apporte une quantité de code smells notée $W_i$ ($W_i$ étant la quantité de code smells apportée par le développeur $i$).
Le nombre de code smells présents dans une partie de l'application $W_p$ est défini par la somme des code smells des développeurs ayant travaillé sur cette partie $p$ de l'application :
$W_p = \sum_{i \in p}{W_i}$

Ce qui permet de définir la qualité $Q_p$ d'une partie de l'application comme le pro rata du nombre de code smells :
$Q_p = 1 - \frac{W_p}{W_{tot}}$

En tant que chef de projet consciencieux, vous mettez un point d'honneur à maximiser la qualité totale $Q$ de votre application ($Q \in [0; 1]$). Elle est définie par le produit de la qualité des différentes parties de l'application normalisé :
$Q = \frac{\prod{}{Q_p}}{W_{tot}} * (1 - \frac{1}{n})^{-n}$   avec $n$ le nombre de partie

Alors que vous pensiez résoudre ce problème facilement, des tensions sont apparues entre certains développeurs à propos d'une sombre histoire d'espace ou de tabulation, vous ne savez plus trop, et certains développeurs refusent de se parler entre eux.
Vous décidez donc de les répartir sur des parties différentes de l'application (heureusement pour vous, chaque paire de développeurs refusant de se parler accepte de parler à tous les autres développeurs).

Vous cherchez donc à optimiser la qualité de votre application tout en séparant les développeurs de façon à ce que deux développeurs refusant de se parler ne travaillent pas sur la même partie de l'application. De plus, votre prédisposition naturelle aux mathématiques et en particulier à l'arithmétique vous permettent de savoir en un clin d'oeil que ce problème explose combinatoirement et par conséquent qu'un programme générant l'ensemble des possibilités n'est pas souhaitable.

• Deux développeurs refusant de se parler ne doivent pas être assignés à la même partie
• Si Régis refuse de parler à Sacha, alors Sacha refuse de parler à Régis
• Tous les développeurs doivent être affectés à une partie
• Un développeur ne peut être affecté qu'à une seule partie
• Il existe au moins une répartition telle que toutes les contraintes sont respectées
• La quantité de code smells apportée par un développeur est fixe
• La somme de tous les code smells sur l'application sera toujours fixe, seule change sa répartition entre les différentes parties
• Le nombre total de code smell est au moins supérieur à 2
• Le nombre de code smells d'un développeur ne peut pas être négatif
• L'algorithme devra retourner un entier équivalent à la différence de code smell entre le back et le front

Exemple

Simple

• Régis possède une quantité de code smell de 10 et refuse de parler à Sacha qui possède une quantité de code smell de 15
• Loïc possède une quantité de code smell de 23
• Benjamin possède une quantité de code smell de 21 et refuse de parler à Kévin qui possède une quantité de code smell de 20

La meilleur répartition possible est : Régis-Loïc-Kévin avec 53 code smells sur la partie front (ou back) et Sacha-Benjamin avec 36 code smells sur la partie back (ou front)

Avancé

• Alice possède une quantité de code smell de 42 et refuse de parler à Bob qui possède une quantité de code smell de 21
• Jean possède une quantité de code smell de 13 et refuse de parler à Charles qui possède une quantité de code smell de 37
• Thibaut possède une quantité de code smell de 7 et refuse de parler à Alphonse qui possède une quantité de code smell de 12
• Patrick possède une quantité de code smell de 11
• Sandra possède une quantité de code smell de 24
• Elise possède une quantité de code smell de 17

La meilleur répartition possible est : Alice-Jean-Alphonse-Sandra avec 91 code smells sur la partie front (ou back) et Bob-Charles-Thibaut-Elise-Patrick avec 93 code smells sur la partie back (ou front)

Indices

Indice 1

Maximiser $Q = \frac{\prod{}{Q_p}}{W_{tot}} * (1 - \frac{1}{n})^{-n}$ revient à dire qu'il faut équilibrer le nombre de code smells entre le back et le front, de telle sorte que chacune des parties soit le plus proche de $\frac{W_{tot}}{2}$

Indice 2

Pour résoudre ce problème d'optimisation combinatoire, vous pouvez utiliser un algorithme de programmation dynamique

Généralisation

Si vous êtes toujours motivé, vous pouvez maintenant résoudre le problème en le généralisant avec $p$ parties et avec un graphe de développeurs refusant de se parler (/!\ attention, certaines configurations seront non soluble). …

Saurez-vous résoudre le problème ?

Bon courage !

Et voici une solution proposée par l'auteur en Java :

private static int getMinimumCodeSmellsGap(Map<Integer, Integer> enemies, List<Integer> weights) {
        int halfNumberOfWeight = weights.stream().mapToInt(x -> x).sum() / 2;
        // L(i, j) <-> if it is possible to have a side with weight j, considering
        // only the developers in the first i couples of enemies
        boolean[][] L = new boolean[enemies.size() + 1][halfNumberOfWeight + 1];

        // initialize to false
        for (int i = 0; i <= enemies.size(); i++) {
            for (int j = 0; j <= halfNumberOfWeight; j++) {
                L[i][j] = false;
            }
        }

        // L(0, 0) = true
        // L(0, j) = false for j != 0
        L[0][0] = true;

        // L(i+1, j) = L(i, j-w[k]) or L(i, j), where k is one of the developers
        // concerned by the (i+1)-th enemy
        int jWeight = 0; // How many enemies have been explored
        for (Map.Entry<Integer, Integer> rivalry : enemies.entrySet()) {
            for (int j = 0; j <= halfNumberOfWeight; j++) {
                if (rivalry.getValue() != -1) {
                    if (j - weights.get(rivalry.getKey()) >= 0) {
                        L[jWeight + 1][j] = L[jWeight][j - weights.get(rivalry.getKey())]
                                || L[jWeight + 1][j];
                    }
                    if (j - weights.get(rivalry.getValue()) >= 0) {
                        L[jWeight + 1][j] = L[jWeight][j - weights.get(rivalry.getValue())]
                                || L[jWeight + 1][j];
                    }
                } else {
                    if (j - weights.get(rivalry.getKey()) >= 0) {
                        L[jWeight + 1][j] = L[jWeight][j - weights.get(rivalry.getKey())]
                                || L[jWeight][j];
                    } else
                        L[jWeight + 1][j] = L[jWeight][j];
                }
            }
            jWeight++;
        }

        int maxNumberOfWeight = halfNumberOfWeight;
        while ((maxNumberOfWeight >= 0) && (!L[enemies.size()][maxNumberOfWeight])) {
            maxNumberOfWeight--;
        }

        return 2 * (halfNumberOfWeight - maxNumberOfWeight);
    }

Votre équipe TakiVeille