Checker le seum

Cette semaine, c'est Kevin qui vous propose un #KataOfTheWeek : Formule de Luhn

Briefing du Kata : L'algorithme procède en trois étapes.

1. L'algorithme multiplie par deux un chiffre sur deux, en commençant par l'avant dernier et en se déplaçant de droite à gauche. Si un chiffre qui est multiplié par deux est plus grand que neuf (comme c'est le cas par exemple pour 8 qui devient 16), alors il faut le ramener à un chiffre entre 1 et 9. Pour cela, il y a 2 manières de faire (pour un résultat identique) :
2. Soit les chiffres composant le doublement sont additionnés (pour le chiffre 8: on obtient d'abord 16 en le multipliant par 2 puis 7 en sommant les chiffres composant le résultat : 1+6).
3. Soit on lui soustrait 9 (pour le chiffre 8 : on obtient 16 en le multipliant par 2 puis 7 en soustrayant 9 au résultat).
4. La somme de tous les chiffres obtenus est effectuée.
5. Le résultat est divisé par 10. Si le reste de la division est égal à zéro, alors le nombre original est valide.

Saurez-vous résoudre le problème ?

Bon courage !

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

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