Descargo de responsabilidad: la codificación de Levenshtein no tiene ninguna relación con la métrica de distancia de edición de Levenshtein .
<Inserte una larga historia sobre por qué los códigos de Levenshtein deben calcularse aquí.>
El código
La codificación de Levenshtein es un sistema de asignación de códigos binarios a enteros no negativos que retiene alguna propiedad extraña en la probabilidad que no es relevante para este desafío. Denotaremos este código como L ( n ). Wikipedia describe esto como un proceso de cinco pasos:
- Inicialice la variable de conteo de pasos C a 1.
- Escriba la representación binaria del número sin
1
el inicio del código. - Sea M el número de bits escritos en el paso 2.
- Si M no es 0, incremente C , repita desde el paso 2 con M como el nuevo número.
- Escriba C
1
bits y0
a al principio del código.
Sin embargo, el código también se puede describir de forma recursiva:
- Si el número es 0, entonces su código es
0
. - Escriba la representación binaria del número sin
1
el inicio del código. - Sea M el número de bits escritos en el paso 2.
- Escriba L ( M ) al comienzo del código.
- Escribe un
1
poco al comienzo del código.
Para aquellos que prefieren ejemplos, aquí está el proceso recursivo para L (87654321), con denotación de concatenación:
El reto
Escriba un programa o función que, dado un número n , emite la cadena de bits L ( n ) en cualquier formato razonable (esto incluye devolver un número con dichos bits). Las lagunas estándar son, como siempre, no permitidas.
Ejemplos
Entrada: 5
Salida: 1110001
Entrada: 30
Salida: 111100001110
Entrada: 87654321
Salida: 111110000101001001110010111111110110001
Entrada: 0
Salida: 0
±
lugar de una funciónf
.JavaScript (ES6),
5452 bytesEditar: Guardado 2 bytes gracias a @Arnauld.
fuente
replace(1,...
lugar dereplace(/1/,...
=> 52 bytesPyth, 12 bytes
Demostración
(Los
y
final es ejecutar la función resultante en la entrada)Explicación:
fuente
SQF, 110
Función recursiva:
Llamar como:
[NUMBER] call f
Tenga en cuenta que esto realmente no funciona para 87654321 u otros números grandes debido a un error en el motor ArmA. Aunque probablemente se solucionará pronto, y debería funcionar de acuerdo con las especificaciones.
( Este boleto aquí )
fuente
PHP,
116114 bytesProporcione el número como primer argumento.
Actualizar:
strlen($b)-1
con~~log10($b)
(finalmente entendí por qué todos los demás estaban usando el logaritmo) y otro al concatenar de manera diferente.fuente
Rubí, 38 bytes.
Muy similar a la respuesta JavaScript de Neil .
Véalo en repl.it: https://repl.it/CnhQ
fuente
Java 8 (Programa completo),
257249 bytesVersión legible con explicación (es sobre todo solo recursión):
EDITAR 1 : 8 bytes guardados : el primer carácter de la cadena binaria es siempre 1; por lo tanto, en lugar de usar
s.charAt(0)
, una mejor opción es simplemente"1"
.fuente