^{Haftungsausschluss: Die Levenshtein-Codierung hat nichts mit der Levenshtein-Editierdistanzmetrik zu tun .}

<Fügen Sie hier eine lange Geschichte darüber ein, warum Levenshtein-Codes berechnet werden müssen.>

Der Code

Die Levenshtein-Codierung ist ein System zum Zuweisen von Binärcodes zu nichtnegativen Ganzzahlen, das eine seltsame Eigenschaft in der Wahrscheinlichkeit beibehält, die für diese Herausforderung nicht relevant ist. Wir werden diesen Code als L ( n ) bezeichnen. Wikipedia beschreibt dies als einen fünfstufigen Prozess:

1. Initialisieren Sie die Schrittzählvariable C auf 1.
2. Schreiben Sie die binäre Darstellung der Zahl, ohne dass dies 1zum Anfang des Codes führt.
3. Sei M die Anzahl der in Schritt 2 geschriebenen Bits.
4. Wenn M nicht 0 ist, erhöhen Sie C und wiederholen Sie ab Schritt 2 mit M als neuer Zahl.
5. Schreiben Sie C- 1 Bits und a 0an den Anfang des Codes.

Der Code kann jedoch auch rekursiv beschrieben werden:

1. Wenn die Zahl 0 ist, lautet der Code 0.
2. Schreiben Sie die binäre Darstellung der Zahl, ohne dass dies 1zum Anfang des Codes führt.
3. Sei M die Anzahl der in Schritt 2 geschriebenen Bits.
4. Schreiben Sie L ( M ) an den Anfang des Codes.
5. Schreiben Sie ein 1bisschen an den Anfang des Codes.

Für diejenigen, die Beispiele bevorzugen, ist hier der rekursive Prozess für L (87654321) mit der Bezeichnung Verkettung:

Die Herausforderung

Schreiben Sie ein Programm oder eine Funktion, die bei gegebener Zahl n den Bitstring L ( n ) in einem beliebigen vernünftigen Format ausgibt (dies schließt die Rückgabe einer Zahl mit diesen Bits ein). Standardlücken sind wie immer nicht erlaubt.

Beispiele

Eingang: 5

Ausgabe: 1110001

Eingang: 30

Ausgabe: 111100001110

Eingang: 87654321

Ausgabe: 111110000101001001110010111111110110001

Eingang: 0

Ausgabe: 0

Gelee , 13 11 Bytes

Ḣ;LÑ$;
BÇṀ¡

Probieren Sie es online aus! oder überprüfen Sie alle Testfälle .

Wie es funktioniert

Die Übermittlung besteht aus zwei sich gegenseitig rekursiven Links.

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 Bytes

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

Definiert eine Funktion f : Int -> [Int]. Zum Beispiel f 5 == [1,1,1,0,0,0,1].

Python, 49 Bytes

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

Testen Sie es auf Ideone .

Mathematica, 61 Bytes

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

JavaScript (ES6), 54 52 Byte

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>

Bearbeiten: 2 Bytes dank @Arnauld gespeichert.

Pyth, 12 Bytes

L&bX1.Bbyslb

Demonstration

(Am yEnde wird die resultierende Funktion am Eingang ausgeführt.)

Erläuterung:

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

Rekursive Funktion:

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}

Rufen Sie an als: [NUMBER] call f

Beachten Sie, dass dies bei 87654321 oder anderen großen Zahlen aufgrund eines Fehlers in der ArmA-Engine nicht funktioniert. Obwohl es wahrscheinlich bald behoben sein wird und gemäß Spezifikation funktionieren sollte.

( Dieses Ticket hier )

PHP, 116 114 Bytes

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

Geben Sie die Nummer als erstes Argument an.

Aktualisieren:

• Ein Byte wurde durch Ersetzen strlen($b)-1durch ~~log10($b)(endlich verstanden, warum alle anderen Logarithmus verwendeten) und ein anderes durch anderes Verketten gespeichert.

Ruby, 38 Bytes

Sehr ähnlich zu Neils JavaScript-Antwort .

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

Siehe es auf repl.it: https://repl.it/CnhQ

Java 8 (Vollprogramm), 257 249 Bytes

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);}}

Lesbare Version mit Erklärung (meistens nur Rekursion):

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 Bytes gespeichert : Das erste Zeichen der Binärzeichenfolge ist immer 1; Daher ist s.charAt(0)eine bessere Option einfach , anstatt sie zu verwenden "1".