^{Avis de non-responsabilité: le codage Levenshtein n'a aucun lien avec la métrique de distance d'édition Levenshtein .}

<Insérer une longue histoire sur la raison pour laquelle les codes Levenshtein doivent être calculés ici.>

Le code

Le codage Levenshtein est un système d'attribution de codes binaires à des entiers non négatifs qui conserve une propriété étrange en probabilité qui n'est pas pertinente pour ce défi. Nous désignerons ce code par L ( n ). Wikipedia décrit cela comme un processus en cinq étapes:

1. Initialisez la variable de comptage de pas C à 1.
2. Écrivez la représentation binaire du nombre sans le mener 1au début du code.
3. Soit M le nombre de bits écrits à l'étape 2.
4. Si M n'est pas 0, incrémentez C , répétez à partir de l'étape 2 avec M comme nouveau numéro.
5. Écrivez C 1 bits et a 0au début du code.

Cependant, le code peut également être décrit de manière récursive:

1. Si le nombre est 0, alors son code est 0.
2. Écrivez la représentation binaire du nombre sans le mener 1au début du code.
3. Soit M le nombre de bits écrits à l'étape 2.
4. Écrivez L ( M ) au début du code.
5. Écrivez un 1peu au début du code.

Pour ceux qui préfèrent les exemples, voici le processus récursif pour L (87654321), avec dénotation de concaténation:

Le défi

Écrivez un programme ou une fonction qui, étant donné un nombre n , sort la chaîne de bits L ( n ) dans n'importe quel format raisonnable (cela inclut le retour d'un nombre avec lesdits bits). Les failles standard sont, comme toujours, interdites.

Exemples

Contribution: 5

Production: 1110001

Contribution: 30

Production: 111100001110

Contribution: 87654321

Production: 111110000101001001110010111111110110001

Contribution: 0

Production: 0

Gelée , 13 11 octets

Ḣ;LÑ$;
BÇṀ¡

Essayez-le en ligne! ou vérifiez tous les cas de test .

Comment ça fonctionne

La soumission consiste en une paire de liens mutuellement récursifs.

BÇṀ¡    Main link. Argument: n

B       Convert n to binary.
   ¡    Execute...
 Ç        the helper link...
  Ṁ       m times, where m is the maximum of n's binary digits.

Ḣ;LÑ$;  Helper link. Argument: A (array of binary digits)

Ḣ       Head; remove and return the first element of A.
    $   Combine the two links to the left into a monadic chain.
  L       Yield the length (l) of A without its first element.
   Ñ      Call the main link with argument l.
 ;      Concatenate the results to both sides.
     ;  Append the tail of A.

Haskell, 70 octets

b 0=[]
b n=b(div n 2)++[mod n 2]
f 0=[0]
f n|1:t<-b n=1:f(length t)++t

Définit une fonction f : Int -> [Int]. Par exemple f 5 == [1,1,1,0,0,0,1],.

Python, 49 octets

f=lambda n:n and'1%s'%f(len(bin(n))-3)+bin(n)[3:]

Testez-le sur Ideone .

Mathematica, 61 octets

f@0={0};f@n_:=Join[{1},f@Length@#,#]&@Rest@IntegerDigits[n,2]

JavaScript (ES6), 54 52 octets

f=n=>(s=n.toString(2)).replace(1,_=>1+f(s.length-1))

<input type=number oninput=o.textContent=f(+this.value)><pre id=o>

Edit: sauvé 2 octets grâce à @Arnauld.

Pyth, 12 octets

L&bX1.Bbyslb

Manifestation

(Le y fin est d'exécuter la fonction résultante sur l'entrée)

Explication:

L&bX1.Bbyslb
L               def y(b):
 &b             If b is 0, return 0. This is returned as an int, but will be cast
                to a string later.
          lb    Take the log of b
         s      Floor
        y       Call y recursively
   X1           Insert at position 1 into
     .Bb        Convert b to binary.

SQF, 110

Fonction récursive:

f={params[["i",0],["l",[]]];if(i<1)exitWith{[0]};while{i>1}do{l=[i%2]+l;i=floor(i/2)};[1]+([count l]call f)+l}

Appelez comme: [NUMBER] call f

Notez que cela ne fonctionne pas réellement pour 87654321 ou d'autres grands nombres en raison d'un bogue dans le moteur ArmA. Bien qu'il sera probablement corrigé bientôt, et devrait fonctionner selon les spécifications.

( Ce ticket ici )

PHP, 116 114 octets

<?$f=function($i)use(&$f){$b=decbin($i);return!$b?0:preg_replace('/^1/',1 .$f(~~log10($b)),$b);};echo$f($argv[1]);

Fournissez le nombre comme premier argument.

Mise à jour:

• Enregistré un octet en remplaçant strlen($b)-1par ~~log10($b)(enfin compris pourquoi tout le monde utilisait le logarithme) et un autre en concaténant différemment.

Rubis, 38 octets

Très similaire à la réponse JavaScript de Neil .

f=->n{("%b"%n).sub(/1\K/){f[$'.size]}}

Voir sur repl.it: https://repl.it/CnhQ

Java 8 (programme complet), 257 249 octets

interface M{static void main(String[]a)throws Exception{int i=0,j;while((j=System.in.read())>10)i=i*10+j-48;System.out.print(L(i));}static String L(int i){if(i==0)return "0";String s=Integer.toString(i,2);return "1"+L(s.length()-1)+s.substring(1);}}

Version lisible avec explication (il s'agit principalement de récursivité):

interface M {
    static void main(String[]a) throws Exception { // Using Exception is unadvised in real coding, but this is Code Gold
        int i = 0, j; // i stores the input; j is a temporary variable
        while ((j = System.in.read()) > 10) // Read the input to j and stop if it is a newline. Technically this stops for tabulators as well, but we shouldn't encounter any of those...
            i = i * 10 + j - 48; // Looping this step eventually reads the whole number in from System.in without using a reader (those take up a lot of bytes)
        System.out.print(L(i)); // Make a method call
    }

    static String L(int i) { // This gets the actual Levenshtein Code
        if (i == 0)
            return "0"; // The program gets a StackOverflowException without this part
        String s = Integer.toString(i, 2); // Shorter than toBinaryString
        return "1" + L(s.length() - 1) + s.substring(1); // Write in the first character (which is always a one), followed by the next L-code, followed by the rest of the binary string
    }
}

EDIT 1 : 8 octets enregistrés : Le premier caractère de la chaîne binaire est toujours 1; par conséquent, plutôt que d'utiliser s.charAt(0), une meilleure option est tout simplement "1".