El libro de Randall Munroe "xkcd, volumen 0" utiliza un sistema de números bastante extraño para los números de página. Los primeros números de página son
1, 2, 10, 11, 12, 20, 100, 101, 102, 110, 111, 112, 120, 200, 1000, 1001, ...
Esto se parece un poco a ternario, pero tenga en cuenta que él salta de 20
directamente a 100
, de 120
a 200
y de 200
a 1000
. Una forma de definir esta secuencia es decir que enumera todos los números ternarios que contienen como máximo uno 2
y no 1
después de eso 2
. Puede encontrar esto en OEIS en la entrada A169683 . Este sistema de números se conoce como sesgo binario .
Su tarea es encontrar la representación de un entero positivo dado N
en este sistema de números.
Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).
La salida puede ser una cadena, un número con una representación decimal igual a la representación binaria sesgada, o una lista de dígitos (como enteros o caracteres / cadenas). No debe devolver ceros a la izquierda.
Este es el código de golf, por lo que gana la respuesta más corta (en bytes).
Dato curioso: en realidad hay algún mérito en este sistema de números. Al incrementar un número, siempre cambiará como máximo dos dígitos adyacentes; nunca tendrá que llevar el cambio a través del número completo. Con la representación correcta que permite incrementar en O (1).
Casos de prueba
1 => 1
2 => 2
3 => 10
6 => 20
7 => 100
50 => 11011
100 => 110020
200 => 1100110
1000 => 111110120
10000 => 1001110001012
100000 => 1100001101010020
1000000 => 1111010000100100100
1048576 => 10000000000000000001
1000000000000000000 => 11011110000010110110101100111010011101100100000000000001102
Daré una recompensa por la respuesta más corta que pueda resolver el último caso de prueba (y cualquier otra entrada de magnitud similar, así que no pienses en codificarlo) en menos de un segundo.
Tablas de clasificación
Aquí hay un fragmento de pila para generar una tabla de clasificación regular y una descripción general de los ganadores por idioma.
Para asegurarse de que su respuesta se muestre, comience con un título, usando la siguiente plantilla de Markdown:
# Language Name, N bytes
¿Dónde N
está el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:
# Ruby, <s>104</s> <s>101</s> 96 bytes
<script>site = 'meta.codegolf'; postID = 5314; isAnswer = true; QUESTION_ID = 51517</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)</code></pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>
fuente
59->60
y109->110
, con el extra 0.Respuestas:
Pyth, 17 bytes
Esto es algo ridículamente lento
O(output^log_2(3))
. Es exponencial en la longitud de la entrada, pero no doblemente exponencial, como algunas de las respuestas en la página. Algunas ideas tomadas de la respuesta de @ Dennis, aquí .Demostración.
Se hace uso de
.f
, Pyth de "bucle hasta que n se han encontrado coincidencias" función.fuente
CJam,
2423222119 bytesEste es un enfoque O (log n) , donde n es la entrada, que completa el último caso de prueba al instante. Convierte n directamente en binario sesgado, utilizando la división modular por los valores del dígito 1 .
Este código termina con un error que va a STDERR con el intérprete de Java, lo cual está permitido de acuerdo con el consenso sobre Meta .
Si prueba este código en el intérprete de CJam , simplemente ignore todo menos la última línea de salida.
El error puede eliminarse, a costa de 2 bytes, anteponiéndose
2>
aW%
.Gracias a @ MartinBüttner por jugar golf en un byte.
Antecedentes
La representación binaria sesgada a k ... a 0 corresponde al número entero n = (2 k + 1 -1) a k + ... + (2 1 -1) a 0 .
Dado que ambos (2 k -1) + ... + (2 1 -1) = 2 k + 1 - (k + 2) y (2 k -1) + ... + 2 (2 j -1) = 2 k + 1 - (2 j + 1 - 2 j + k + 1) son menos de 2 k + 1 -1 , los valores de un k a un 0 se puede recuperar por división modular sucesiva por 2 k + 1 -1 , 2 k -1 , etc.
Para comenzar, primero tenemos que encontrar el valor de 2 k + 1 -1 . Como n es como máximo 2 (2 k + 1 -1) , el número entero n + 1 debe ser estrictamente más pequeño que 2 k + 2 .
Por lo tanto, tomar la parte entera del logaritmo binario de n + 1 produce k + 1 .
Finalmente, observamos que el número entero n + 1 tiene ⌊log 2 (n + 1) ⌋ dígitos en la base 2.
Cómo funciona
En las últimas dos iteraciones, realizamos una división modular por 1 y 0 . El primero empuja un 0 no deseado en la pila. Los últimos intentos de ejecución
0 0 md
, que extraen los 0 s no deseados de la pila, salen inmediatamente en lugar de empujar cualquier cosa y vuelcan la pila a STDOUT.fuente
Python 2, 67 bytes
Parece funcionar para los casos de prueba dados. Si lo he entendido bien, esto debería ser
O(place values set in output)
así, por lo que hace el último caso con facilidad.Llama como
f(100)
. Devuelve una representación decimal igual al binario sesgado.Python 3, 65 bytes
Ligeramente menos eficiente pero aún logarítmico, por lo que el último caso es casi instantáneo.
Llama como
g(100)
. Devuelve una lista de dígitos.fuente
2and
compila en 3? Estoy en 2 y2and2
arroja un error de sintaxis2and2
no funcionaría porque se analizaría como2 and2
- try2and 2
, que debería funcionar si su versión de Python es lo suficientemente nueva (probado en Python 2.7.10)CJam,
222120 bytesEste es un enfoque O (e n n) , donde n es la entrada. Se enumera los primero ⌊e n ⌋ enteros no negativos en base 3, elimina las que tienen 2 s o 1 s después de la primera 2 (si lo hay) y selecciona el n + 1 º .
Pruébelo en línea en el intérprete de CJam .
Cómo funciona
fuente
Pyth, 20 bytes
Se ejecuta en O (log (input ())), bastante menos de un segundo para el caso de prueba final. Basado en un ciclo de ejecución hasta error. Sin nueva línea final.
Demostración.
Explicación:
J se inicializa al valor de la posición de dígitos binarios oblicuos más pequeña que es mayor que la entrada. Luego, cada vez a través del ciclo, hacemos lo siguiente:
J
deQ
con=%QJ
. Por ejemplo, siQ=10
yJ=7
, seQ
convierte3
, lo que corresponde al binario sesgado que cambia de110
a10
. Esto no tiene efecto en la primera iteración.J
al siguiente valor base binario sesgado más pequeño con=/J2
. Esta es la división de pisos por 2, cambiandoJ=7
aJ=3
, por ejemplo. Como esto sucede antes de queJ
salga el primer dígito, se inicializa una posición de un dígito más alta de lo necesario./QJ
(efectivamente).p
, en lugar de la impresión predeterminada de Pyth, para evitar la nueva línea final.Este ciclo se repetirá hasta que se
J
convierta en cero, momento en el cual se generará un error de división por cero y el ciclo finalizará.fuente
ES6, 105 bytes
El uso es:
f(1048576)
=> `" 10000000000000000001 "Prueba el último argumento bajo tu propio riesgo. Me di por vencido después de 5 segundos.
Y bonita impresión con comentarios!
fuente
f=
.f=n=>{for(o=0;~n--;o+=c?Math.pow(3,s.length+c):1)s=o.toString(3),c=~s.search(2);return s}
Math.pow(3,s.length+c)
con3**(s.length+c)
.Retina, 55 bytes
Toma entrada en unario.
Cada línea debe ir a su propio archivo, pero puede ejecutar el código como un archivo con la
-s
bandera. P.ej:Método: ejecuta el incremento en un número de entrada de cadena de tiempo comenzando desde la cadena
0
.Utilizamos las siguientes reglas de incremento:
2
:^2 -> ^12
;02 -> 12
;12 -> 20
2
:0$ -> 1$
;1$ -> 2$
(Puede haber como máximo uno
2
en la cadena;^
y$
marca el inicio y el final de la cadena en las reglas).Más información sobre Retina.
fuente
Java,
154148Esta respuesta toma la forma de una única función anónima que toma un argumento entero y devuelve la respuesta como una cadena. A continuación se muestra una clase completa para probar esta solución.
fuente
Bash + coreutils, 52
Este es un forzador de la fuerza bruta, por lo que es bastante lento para grandes cantidades.
Salida:
fuente
Java,
337335253246244 bytesUn método que toma el índice como a
long
y devuelve el resultado como una cadenaUtiliza un
long
para el índice, por lo que teóricamente puede manejar el último caso de prueba, pero realmente no lo sugeriría.fuente
if(j == 0)
declaración (cuatro bytes). No necesitas declarark
; puedes usarj
nuevamente (cuatro más). Puede usar la inferencia de tipo genérico (en Java 7) en su declaración de Lista (new ArrayList<>();
) (otro 4)Haskell,
7372¡Gracias a @nimi por 1 byte!
Esta solución no ganará recompensas, las últimas dos pruebas requieren una cantidad excesiva de tiempo para ejecutarse, pero creo que lo he jugado bastante bien.
Esta solución es un enfoque bastante ingenuo que calcula el número binario sesgado
n
incrementando 0n
veces.fuente
CJam, 24 bytes
Este es un enfoque O (n log n) , donde n es la entrada. Comienza con la representación binaria sesgada de 0 e incrementa el entero correspondiente n veces.
Pruébelo en línea en el intérprete de CJam .
Antecedentes
El incremento de un número en binario sesgado se puede hacer siguiendo dos sencillos pasos:
Reemplace un eventual 2 por un 0 .
Si se ha reemplazado un 2 , incremente el dígito a su izquierda.
De lo contrario, incremente el último dígito.
Cómo funciona
fuente
VBA,
209147142 bytesMi matemática es ineficiente y mi golf podría funcionar. Pero es mi primer intento de PoG y pensé en probarlo. Sin embargo, es una especie de fuerza bruta.
Solo cuenta por 1 a menos que el último dígito sea un 2, luego retrocede por 2 y salta hacia adelante 10. Además de los ceros al final.
Esto deja de funcionar en 65534 porque VBA insiste en dar salida en notación científica, pero la lógica debería funcionar bien para números aún más altos
En espera de sugerencias de golf, VBA no es muy amigable con el golf, pero a menudo no está representado, y creo que puede vencer a Java por la longitud.
Edit1: Gracias Manu por ayudar a reducir 62 bytes
Edit2: intercambiado
debug.print
pormsgbox
como salida. 5 bytes guardadosfuente
Debug.Print (q)
. Además, puede eliminar la mayoría de los espacios en blanco (el editor los volverá a colocar, pero no son necesarios). No necesita declarark as Long
, simplemente escribak
. Será una variable del tipo Variant y el código seguirá funcionando. Con estos consejos, debería bajar a ~ 165 bytes.InStr
, son opcionales.Trim()
no es necesario, ya que no tienes espacios en blanco. Aplicado correctamente, llego a 147 bytes .debug.print q
sería la salida estándar?msgbox q
es más corto pero parece que no es el resultado estándar.Sheet1.cells(1,1)
parece el resultado típico , pero supone que se ejecuta en Excel. Simplemente no estoy muy seguro de cuán estricto es el código golf sobre este tipo de cosas.MsgBox
, si alguien se queja, todavía puedes cambiarlo.Javascript ES6,
9986787672 caracteresPrueba:
Gracias por el hecho, es la base de mi solución :)
fuente
Octava,
107101 bytesDebería ser O (log n) si calculo esto bien ...
Bonito estampado:
Me sorprendió un poco abordar el desafío final, ya que Octave por defecto trata todo como números de coma flotante y no tenía la precisión necesaria para calcular el último. Lo solucioné gastando preciosos bytes para forzar que todo sea un entero sin signo. El resultado del último fue demasiado grande para tratarlo como un número, por lo que el resultado es una cadena.
Salida (incluyo
1e18 - 1
mostrar que puedo hacerlo con precisión, y el último conjunto de salidas muestra cuánto tiempo lleva calcular ese valor):fuente
T-SQL,
221189177 bytesEDITAR: Las versiones originales de este código producirían resultados incorrectos para algunos números, esto se ha corregido.
Con cada consulta aquí, simplemente agregue el número para calcular antes de la primera coma.
Todos saben que T-SQL es el mejor lenguaje de golf. Aquí hay una versión que calculará incluso el último caso de prueba. En la máquina en la que lo probé, funcionó en menos de un segundo, me interesaría ver cómo funciona para todos los demás.
Y aquí está de nuevo, pero legible:
Si solo uso ints, esto puede ser un poco más corto, con 157 bytes:
Y una vez más, más legible:
fuente
@
es un identificador válido en sql y lo más probable es que pueda salirse con la suya yChar(8000)
seguir siendo más barato que nvarchar (max). También puede convertir a enchar
lugar devarchar
, o usar lastr
función.@
, tonto de mí. ElCHAR(8000)
consejo es bastante bueno, lo intentaré. Siempre me olvido de la existencia deSTR()
gracias por el aviso.select @t=concat(@t,@/i)
que debería ser más pequeña. Sin embargo, requiere sql2012.CONCAT
, Estoy en 2008. Así que no puedo probarlo sin usar un violín SQL en este momento. Buena llamada sin embargo.Código de máquina de Turing,
333293 bytesEstoy usando una codificación como se usa aquí .
Esta máquina utiliza 9 estados y 11 colores.
Si se permite la entrada binaria, esto se puede reducir a solo 4 colores, ahorrando algunas decenas de bytes en el proceso.
Si el enlace anterior no funciona (a veces funciona para mí, otras veces la página se niega a cargar), también puede probar esto usando esta implementación de Java.
fuente
Perl, 66 bytes
El número se ingresará a través de STDIN.
fuente
(.?)
en$2
puesto(.*)
en$1
debe ser codicioso y conseguir que el personaje en primer lugar. ¡Pero si se elimina, el código ya no produce los resultados correctos! Por cierto, no necesitas la final;
.$c=<>;s/(.*)2(.*)/$1+1 .$2.0/e||$_++while($c--);print
. Tenía razón,(.?)
nunca capturaron nada.$_=1;$c=<>;s/(.?)2/1+$1.0/e||$_++while(--$c);print
, que es de 50 bytes..*
al principio o al final se puede optimizar, si lo reemplaza con el texto original. Además, no hay razón para agregar el 0 al final, ya que siempre hay ceros en el original$3
.Pyth, 19 bytes
Complejidad logarítmica. Termina fácilmente en el tiempo necesario. Salida en forma de una lista de dígitos.
Demostración .
fuente
Perl,
847067 bytesNo es muy golfista, estámejorando pero funciona muy rápido.La sugerencia de Dennis lo reduce a 51 (50 bytes + -p switch)
Se debe ser llamado como
perl -p skew_binary.pl num_list.txt
dondenum_list.txt
contiene una sola línea con el número para codificar en él.fuente
Mathematica, 65
Debería ser lo suficientemente rápido, aunque tengo que admitir que eché un vistazo a las otras presentaciones antes de hacer esto.
Uso:
Salida:
Comienza a dar mensajes de error MaxExtraPrecision en algún lugar pasado 10 ^ 228 (para el cual calcula el resultado en .03 segundos en mi máquina)
Después de eliminar el límite MaxExtraPrecision, manejará números de hasta alrededor de 10 ^ 8000 en un segundo.
Entrada:
Salida:
fuente
C, 95 bytes
Esto acepta un número entero y un búfer en el que devolver los dígitos. Los resultados se almacenan en
b
, terminados con valor3
(que no puede ocurrir en la salida). No tenemos que manejar la entrada de0
(ya que la pregunta especifica solo enteros positivos), por lo que no hay una carcasa especial para evitar la salida vacía.Código ampliado
Operamos por sustracción sucesiva, comenzando con el dígito más significativo. La única complicación es que usamos la variable
m
para evitar imprimir ceros a la izquierda. Seunsigned long long
puede hacer una extensión natural si se desea, a un costo de 10 bytes.Programa de prueba
Pase los números que se convertirán como argumentos de comando. Convierte el
int
búfer de matriz en una cadena de dígitos imprimible. El tiempo de ejecución es inferior a un milisegundo para la entrada1000000000000000000
.Resultados de la prueba
fuente
auto a=~0ull
para una ligera ventaja ...JavaScript (Node.js) , 40 bytes
Pruébalo en línea!
Esta solución no funciona en el último caso de prueba. Simplemente causa un desbordamiento de pila en él.
fuente
CoffeeScript,
9269 bytesSegún la respuesta y las actualizaciones de Qwertiy :
fuente
Japt , 31 bytes
Pruébalo en línea!
Puerto casi directo de esta solución JS . No tengo idea si hay mejor manera.
Desempaquetado y cómo funciona
fuente
Stax , 16 bytes
Ejecutar y depurarlo
No estoy seguro de cuál es exactamente la clase de complejidad formal, pero es lo suficientemente rápido como para hacer todos los casos de prueba en una décima de segundo en esta máquina.
Desempaquetado, sin golf y comentado, se ve así. En este programa, el registro x originalmente contiene la entrada.
Ejecute este
fuente