Récursion dangereuse !

Cette semaine, c'est Thomas qui vous propose un #KataOfTheWeek : Algorithme mystère

Briefing du Kata : Parlons de ce fameux algorithme, avec des termes bien mathématiques : Soit la fonction récursive T qui à n associe un tableau. Le premier élément de la suite est défini comme suit :

T(1) = [0, 1]

Les autres éléments de la fonction T(n + 1) sont définis en prenant 2 copies T(n). On inverse la seconde copie. On place un 0 devant chaque élément de la première copie, et un 1 devant chaque élément de la seconde et on les concatène. Ceci nous donne donc :

T(2) = [00, 01, 11, 10]
T(3) = [000, 001, 011, 010, 110, 111, 101, 100]
T(4) = [0000, 0001, 0011, 0010 ... 1010, 1011, 1001, 1000]

Maintenant parlons d'une autre fonction M(x) où x est un entier constitué de n bit. M(x) correspondra à la xieme entrée du tableau T(n) convertie du binaire vers la base 10.

Ceci devrait être un peu plus clair avec un exemple… Typiquement M(6) = 5, parce que 6 est constitué de 3 bits (110) et que la 6eme entrée de T(3) est 101 soit 5 en base 10 ! Je vous laisse le temps de digérer avec d'autres exemples : M(3) = 2, M(5) = 7 et M(10) = 15.

Votre mission sera de coder M dans un premier temps, ensuite si le cœur vous en dit, vous pourrez vous attaquer à I qui est la fonction inverse. Grosso modo, M(6) = 5, I(5) = 6. Donc I(2) = 3, I(7) = 5 et I(15) = 10.

J'oubliais, vos fonctions M et I doivent pouvoir fournir un résultat en un temps raisonnable (< 5s) pour des nombres un peu grand (> 100).

Bon courage !

Saurez-vous résoudre le problème ?

Bon courage !

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

Bon j'espère que vous vous en êtes sorti ! D'abord, parlons de l'algorithme en lui-même : il s'agit ni plus ni moins que de l'algorithme du code de gray. Je vous laisse la page wikipédia qui saura mieux vous en parler que moi !

Le piège ici était de partir sur une implémentation de l'algorithme comme il a été décrit dans le briefing. Il fallait écrire ses propres cas de test et comprendre comment l'algorithme fonctionnait réellement. Pour l'encodage, il ne s'agit que d'un XOR entre le nombre donné en paramètre et ce même nombre décalé d'un bit vers la droite. Pour le décodage, c'est un peu plus compliqué. Il faut faire un XOR par rapport au nombre décalé vers la droite pour chaque bit.

En ce qui concerne la solution la voici :

public class GrayCode {
    // M(x)
    public static long encode(long x) {
        return x ^ x >> 1;
    }

    // I(x)
    public static long decode(long num) {
        long mask = num >> 1;
        while (mask != 0) {
            num ^= mask;
            mask >>= 1;
        }
        return num;
    }
}

Votre équipe TakiVeille