Numeración de páginas de estilo xkcd

65

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 20directamente a 100, de 120a 200y de 200a 1000. Una forma de definir esta secuencia es decir que enumera todos los números ternarios que contienen como máximo uno 2y no 1despué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 Nen 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 Nestá 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>

Martin Ender
fuente
32
He tenido ese libro desde que salió y nunca noté la numeración de la página.
Alex A.
2
@AlexA. Lo tengo en mi Kindle donde no puedes hacer ninguna numeración de página interesante.
LegionMammal978
21
@ LegionMammal978: Trágico.
Alex A.
1
@ SuperJedi224 El consenso parece ser no , lo siento mucho (haría una excepción al consenso si ese fuera el único tipo de información que su lenguaje podría manejar, pero ese no parece ser el caso).
Martin Ender
44
Esto me recuerda cómo solía contar cuando tenía 3 años. Pensé: "no hay cincuenta y diez, así que después de ciento nueve deben ser doscientos". Sólo me di cuenta de mi error al ver la diferencia entre 59->60y 109->110, con el extra 0.
Cyoce

Respuestas:

12

Pyth, 17 bytes

Ljb3ye.f!-P-yZ01Q

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.

isaacg
fuente
32

CJam, 24 23 22 21 19 bytes

ri_)2b,,W%{2\#(md}/

Este 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>a W%.

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

ri    e# Read an integer N from STDIN.
2b,   e# Push the number of binary digits of N + 1, i.e, K + 2 = log(N + 1) + 1.
,W%   e# Push the range [K+1 ... 0].
{     e# For each J in the range:
  2\# e#   J -> 2**J
  (   e#     -> 2**J - 1
  md  e#   Perform modular division of the integer on the stack (initially N)
      e#   by 2**J - 1: N, 2**J - 1 -> N/(2**J - 1), N%(2**J - 1)
}/    e#

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.

Dennis
fuente
28

Python 2, 67 bytes

def f(n):x=len(bin(n+1))-3;y=2**x-1;return n and n/y*10**~-x+f(n%y)

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

def g(n,x=1):*a,b=n>x*2and g(n,x-~x)or[n];return a+[b//x,b%x][:x]

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.

Sp3000
fuente
se 2andcompila en 3? Estoy en 2 y 2and2arroja un error de sintaxis
TankorSmash
3
@TankorSmash 2and2no funcionaría porque se analizaría como 2 and2- try 2and 2, que debería funcionar si su versión de Python es lo suficientemente nueva (probado en Python 2.7.10)
Sp3000
Oh bien, tienes razón. Incluso en 2.7.3 funciona.
TankorSmash
12

CJam, 22 21 20 bytes

ri_me,3fb{0-W<1-!},=

Este 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

ri    e# Read an integer N from STDIN.
_me,  e# Push [0 ... floor(exp(N))-1].
3fb   e# Replace each integer in the range by the array of its digits in base 3.
{     e# Filter; for each array A:
  0-  e#   Remove all 0's.
  W<  e#   Remove the last element.
  1-  e#   Remove all 1's.
  !   e#   Logical NOT. Pushes 1 iff the array is empty.
},    e#   If ! pushed 1, keep the array.
=     e# Select the (N+1)th element of the filtered array.
Dennis
fuente
9

Pyth, 20 bytes

Jt^2hslhQ#p/=%QJ=/J2

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:

Jt^2hslhQ#p/=%QJ=/J2
                        Implicit: Q is the input.
      lhQ                          log(Q+1,2)
     slhQ                    floor(log(Q+1,2))
    hslhQ                    floor(log(Q+1,2))+1
  ^2hslhQ                 2^(floor(log(Q+1,2))+1)
 t^2hslhQ                 2^(floor(log(Q+1,2))+1)-1
Jt^2hslhQ               J=2^(floor(log(Q+1,2))+1)-1
         #              until an error is thrown:
            =%QJ        Q=Q%J
                =/J2    J=J/2
           /            The value Q/J, with the new values of Q and J.
          p             print that charcter, with no trailing newline.

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:

  • Elimine cada dígito de valor Jde Qcon =%QJ. Por ejemplo, si Q=10y J=7, se Qconvierte 3, lo que corresponde al binario sesgado que cambia de 110a 10. Esto no tiene efecto en la primera iteración.
  • Cambie Jal siguiente valor base binario sesgado más pequeño con =/J2. Esta es la división de pisos por 2, cambiando J=7a J=3, por ejemplo. Como esto sucede antes de que Jsalga el primer dígito, se inicializa una posición de un dígito más alta de lo necesario.
  • Encuentre el valor real de los dígitos con /QJ(efectivamente).
  • Imprima ese valor con p, en lugar de la impresión predeterminada de Pyth, para evitar la nueva línea final.

Este ciclo se repetirá hasta que se Jconvierta en cero, momento en el cual se generará un error de división por cero y el ciclo finalizará.

isaacg
fuente
8

ES6, 105 bytes

f=n=>{for(o=0;n--;c?o+=Math.pow(3,s.length-c):o++)s=t(o),c=s.search(2)+1;return t(o);},t=a=>a.toString(3)

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!

f=n=>{ //define function f with input of n (iteration)
    for(o=0; //define o (output value in decimal)
        n--; //decrement n (goes towards falsy 0) each loop until 0
        c?o+=Math.pow(3,s.length-c):o++) //if search finds a 2, increment output by 3^place (basically moves the 2 to the left and sets the place to 0), else ++
        s=t(o), //convert output to base 3      
        c=s.search(2)+1; //find the location of 2, +1, so a not-found becomes falsy 0.
    return t(o); //return the output in base 3
},

t=a=>a.toString(3);  //convert input a to base 3
Brújula
fuente
55
Por cierto, las funciones sin nombre son perfectamente aceptables, por lo que no es necesario f=.
Martin Ender
2
-16 bytes: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}
nderscore
@nderscore Bastante genial: D
Brújula
1
-7 bytes si usa ES7: reemplace Math.pow(3,s.length+c)con 3**(s.length+c).
Gustavo Rodrigues
3
@GustavoRodrigues ¡Ni siquiera he terminado de aprender ES6! @ _ @
Brújula
7

Retina, 55 bytes

^
0a
(+`12(.*a)1
20$1
0?2(.*a)1
10$1
0a1
1a
)`1a1
2a
a
<empty line>

Toma entrada en unario.

Cada línea debe ir a su propio archivo, pero puede ejecutar el código como un archivo con la -sbandera. P.ej:

> echo 11111|retina -s skew
12

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:

  • si contiene 2: ^2 -> ^12; 02 -> 12;12 -> 20
  • si no contiene 2: 0$ -> 1$;1$ -> 2$

(Puede haber como máximo uno 2en la cadena; ^y $marca el inicio y el final de la cadena en las reglas).

Más información sobre Retina.

randomra
fuente
7

Java, 154 148

n->{String s="0";for(;n-->0;)s=s.contains("2")?s.replaceAll("(^|0)2","10").replace("12","20"):s.replaceAll("1$","2").replaceAll("0$","1");return s;}

Esta 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.

import java.util.function.Function;
public class Skew {
    public static void main(String[] args){
        Function<Integer,String> skew = n->{String s="0";for(;n-->0;)s=s.contains("2")?s.replaceAll("(^|0)2","10").replace("12","20"):s.replaceAll("1$","2").replaceAll("0$","1");return s;};

        for(String s:args){
            System.out.println(skew.apply(Integer.parseInt(s)));
        }
    }
}
ankh-morpork
fuente
5

Bash + coreutils, 52

dc -e3o0[r1+prdx]dx|grep -v 2.\*[12]|sed -n $1{p\;q}

Este es un forzador de la fuerza bruta, por lo que es bastante lento para grandes cantidades.

Salida:

$ ./xkcdnum.sh 1000
111110120
$ 
Trauma digital
fuente
5

Java, 337 335 253 246 244 bytes

Un método que toma el índice como a longy devuelve el resultado como una cadena

Utiliza un longpara el índice, por lo que teóricamente puede manejar el último caso de prueba, pero realmente no lo sugeriría.

String f(long i){List<Long>l=new ArrayList<>();l.add(0L);for(;i-->0;){int j=l.indexOf(2);if(j!=-1){l.set(j,0L);if(j==0){l.add(0,1L);}else{l.set(j-1,l.get(j-1)+1);}}else{j=l.size()-1;l.set(j,l.get(j)+1);}}String s="";for(long q:l)s+=q;return s;}
SuperJedi224
fuente
44
Puede acortar esto un poco convirtiéndolo en una función en lugar de un programa completo (y tomando la entrada como argumento en lugar de un Escáner).
Geobits
2
No necesita las llaves en la if(j == 0) declaración (cuatro bytes). No necesitas declarar k; puedes usar jnuevamente (cuatro más). Puede usar la inferencia de tipo genérico (en Java 7) en su declaración de Lista ( new ArrayList<>();) (otro 4)
durron597
4

Haskell, 73 72

¡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.

i(2:b)=1:0:b
i[b]=[b+1]
i(b:2:c)=b+1:0:c
i(b:c)=b:i c
s=(iterate i[0]!!)

Esta solución es un enfoque bastante ingenuo que calcula el número binario sesgado nincrementando 0 nveces.

ankh-morpork
fuente
4

CJam, 24 bytes

Q{0\+2a/())+a\+0a*}ri*si

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:

  1. Reemplace un eventual 2 por un 0 .

  2. Si se ha reemplazado un 2 , incremente el dígito a su izquierda.

    De lo contrario, incremente el último dígito.

Cómo funciona

Q     e# Push an empty array.
{     e# Define an anonymous function:
  0\+ e#   Prepend a 0 to the array.
  2a/ e#   Split the array at 2's.
  (   e#   Shift out the first chunk of this array.
  )   e#   Pop the last digit.
  )+  e#   Increment it and append it to the array.
  a\+ e#   Prepend the chunk to the array of chunks.
  0a* e#   Join the chunks, using [0] as separator.
      e#   If there was a 2, it will get replaced with a 0. Otherewise, there's
      e#   only one chunk and joining the array dumps the chunk on the stack.
}     e#
ri*   e# Call the function int(input()) times.
si    e# Cast to string, then to integer. This eliminates leading 0's.
Dennis
fuente
4

VBA, 209 147 142 bytes

Sub p(k)
For i=1To k
a=StrReverse(q)
If Left(Replace(a,"0",""),1)=2Then:q=q-2*10^(InStr(a,2)-1)+10^InStr(a,2):Else:q=q+1
Next
msgbox q
End Sub

Mi 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.printpor msgboxcomo salida. 5 bytes guardados

JimmyJazzx
fuente
1
Puede quitar los corchetes de 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 declarar k as Long, simplemente escriba k. Será una variable del tipo Variant y el código seguirá funcionando. Con estos consejos, debería bajar a ~ 165 bytes.
CommonGuy
Algunas ideas más: puede omitir el primer y el último argumento de InStr, son opcionales. Trim()no es necesario, ya que no tienes espacios en blanco. Aplicado correctamente, llego a 147 bytes .
CommonGuy
1
Gracias por el Manu de ayuda. Una pregunta rápida, La salida debería ser la Salida estándar. No estoy seguro de qué sería eso en VBA. debug.print qsería la salida estándar? msgbox qes 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.
JimmyJazzx
Felicidades, superaste la respuesta de Java;) Yo tampoco lo sé ... Solo usa MsgBox, si alguien se queja, todavía puedes cambiarlo.
CommonGuy
4

Javascript ES6, 99 86 78 76 72 caracteres

f=n=>{for(s="1";--n;s=s.replace(/.?2|.$/,m=>[1,2,10][+m]||20));return s}

// Old version, 76 chars:
f=n=>{for(s="1";--n;s=s.replace(/02|12|2|.$/,m=>[1,2,10][+m]||20));return s}

// Old version, 86 chars:
f=n=>{for(s="1";--n;s=s.replace(/(02|12|2|.$)/,m=>[1,2,10,,,,,,,,,,20][+m]));return s}

// Old version, 99 chars:
f=n=>{for(s="1";--n;s=s.replace(/(^2|02|12|20|.$)/,m=>({0:1,1:2,2:10,12:20,20:100}[+m])));return s}

Prueba:

;[1,2,3,6,7,50,100,200,1000,10000,100000,1000000,1048576].map(f) == "1,2,10,20,100,11011,110020,1100110,111110120,1001110001012,1100001101010020,1111010000100100100,10000000000000000001"

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).

Gracias por el hecho, es la base de mi solución :)

Qwertiy
fuente
¿Cómo podría dejar llaves innecesarias en la expresión regular? o_O
Qwertiy
3

Octava, 107 101 bytes

Debería ser O (log n) si calculo esto bien ...

function r=s(n)r="";for(a=2.^(uint64(fix(log2(n+1))):-1:1)-1)x=idivide(n,a);r=[r x+48];n-=x*a;end;end

Bonito estampado:

function r=s(n)
  r="";
  for(a=2.^(uint64(fix(log2(n+1))):-1:1)-1)
    x=idivide(n,a);
    r=[r x+48];
    n-=x*a;
  end
end

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 - 1mostrar que puedo hacerlo con precisión, y el último conjunto de salidas muestra cuánto tiempo lleva calcular ese valor):

octave:83> s(uint64(1e18))
ans = 11011110000010110110101100111010011101100100000000000001102

octave:84> s(uint64(1e18)-1)
ans = 11011110000010110110101100111010011101100100000000000001101

octave:85> tic();s(uint64(1e18)-1);toc()
Elapsed time is 0.0270021 seconds.
dcsohl
fuente
3

T-SQL, 221 189 177 bytes

EDITAR: 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.

DECLARE @ BIGINT=,@T VARCHAR(MAX)='';WITH M AS(SELECT CAST(2AS BIGINT)I UNION ALL SELECT I*2FROM M WHERE I<@)SELECT @T += STR(@/(I-1),1),@%=(I-1)FROM M ORDER BY I DESC SELECT @T

Y aquí está de nuevo, pero legible:

DECLARE 
    @ BIGINT=,
    @T VARCHAR(MAX)='';

WITH M AS
(
    SELECT
        CAST(2 AS BIGINT) I

    UNION ALL

    SELECT I * 2
    FROM M
    WHERE I < @
)

SELECT 
    @T+=STR(@/(I-1),1),
    @%=(I-1)
FROM M 
ORDER BY I DESC

SELECT @T

Si solo uso ints, esto puede ser un poco más corto, con 157 bytes:

DECLARE @ INT=,@T VARCHAR(MAX)='';WITH M AS(SELECT 2I UNION ALL SELECT I*2FROM M WHERE I<@)SELECT @T+=STR(@/(I-1),1),@%=(I-1)FROM M ORDER BY I DESC SELECT @T

Y una vez más, más legible:

DECLARE 
    @ INT=,
    @T VARCHAR(MAX)='';

WITH M AS
(
    SELECT
        2I

    UNION ALL

    SELECT 
        I * 2
    FROM M
    WHERE I < @
)

SELECT 
    @T+=STR(@/(I-1),1),
    @%=(I-1)
FROM M 
ORDER BY I DESC

SELECT @T
PenutReaper
fuente
Recuerde que @es un identificador válido en sql y lo más probable es que pueda salirse con la suya y Char(8000) seguir siendo más barato que nvarchar (max). También puede convertir a en charlugar de varchar, o usar la strfunción.
Michael B
@MichaelB Oh, pensé que lo había usado @, tonto de mí. El CHAR(8000)consejo es bastante bueno, lo intentaré. Siempre me olvido de la existencia de STR()gracias por el aviso.
PenutReaper
en realidad no ayuda Sin embargo, puede reescribir la parte después del CTE en :: select @t=concat(@t,@/i)que debería ser más pequeña. Sin embargo, requiere sql2012.
Michael B
@MichaelB ah. CONCAT, Estoy en 2008. Así que no puedo probarlo sin usar un violín SQL en este momento. Buena llamada sin embargo.
PenutReaper
3

Código de máquina de Turing, 333 293 bytes

Estoy 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.

0 _ _ l 1
0 * * r 0
1 9 8 l 2 
1 8 7 l 2
1 7 6 l 2
1 6 5 l 2
1 5 4 l 2
1 4 3 l 2
1 3 2 l 2
1 2 1 l 2
1 1 0 l 2
1 0 9 l 1
1 _ _ r 8
2 _ _ l 3
2 * * l 2
3 _ 1 r 4
3 * * l 5
4 _ _ r 0
4 * * r 4
5 * * l 5
5 _ _ r 6
6 _ _ l 7
6 2 0 l 7
6 * * r 6
7 _ 1 r 4
7 0 1 r 4
7 1 2 r 4
8 _ _ * halt
8 * _ r 8

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.

SuperJedi224
fuente
2

Perl, 66 bytes

El número se ingresará a través de STDIN.

$_=1;$c=<>;s/(.*)(.?)2(.*)/$1.$2+1 .$3.0/e||$_++while(--$c);print;
Frederick
fuente
¿Podría explicar cómo funciona su solución? No veo cómo necesita (.?)en $2puesto (.*)en $1debe 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 ;.
CJ Dennis
@CJDennis Gracias por ese byte guardado. De todos modos, el.? obtendrá el dígito justo antes de los dos a menos que no haya ningún dígito allí (por ejemplo, 20) En casos como 120 o 10020, los grupos de expresiones regulares son los siguientes: () (1) 2 (0) y (10) (0) 2 (0). Luego, el primer grupo simplemente se ignora, el segundo grupo (que siempre es un dígito si es posible o está en blanco) se incrementa, y el tercer grupo (que siempre consta de ceros) se ignora y se agrega un cero. Simplemente utilicé la entrada OEIS como mi guía para esta expresión regular.
Frederick
Tengo el código de abajo a 53 bytes: $c=<>;s/(.*)2(.*)/$1+1 .$2.0/e||$_++while($c--);print. Tenía razón, (.?)nunca capturaron nada.
CJ Dennis
Se puede optimizar para $_=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.
Thraidh
2

Pyth, 19 bytes

m/=%Qtydtd^L2_SslhQ

Complejidad logarítmica. Termina fácilmente en el tiempo necesario. Salida en forma de una lista de dígitos.

Demostración .

isaacg
fuente
2

Perl, 84 70 67 bytes

$n=<>;$d*=2while($d++<$n);$_.=int($n/$d)while($n%=$d--,$d/=2);print

No es muy golfista, está mejorando pero funciona muy rápido.

La sugerencia de Dennis lo reduce a 51 (50 bytes + -p switch)

$d*=2while$d++<$_;$\.=$_/$d|0while$_%=$d--,$d/=2}{

Se debe ser llamado como perl -p skew_binary.pl num_list.txtdonde num_list.txtcontiene una sola línea con el número para codificar en él.

CJ Dennis
fuente
@frederick estamos al borde de nuestros asientos esperando 2.
Robert Grant
@RobertGrant ¡Golfó su comentario de dos cosas a una!
CJ Dennis
Dos cosas: 1. En lugar de usar $ ARGV [0], use <> como entrada. Tomará la entrada de stdin a menos que haya algún archivo como argumento. 2. Para esquemas de conteo impares como este, use expresiones regulares. En lugar de realizar operaciones matemáticas impares, puede reemplazar los dígitos de un número como si fuera una cadena. La mejor parte es que puede usar operaciones matemáticas (como incrementos) al mismo tiempo, siempre que sea una cadena que consta completamente de dígitos. Consulte la documentación de los operadores de expresiones regulares, ya que pueden ser muy útiles en muchas ocasiones.
Frederick
Lo siento, presioné enter y se guardó antes de terminar el comentario.
Frederick
@frederick no seas tan modesto. ¡Sabemos lo que pasó!
Robert Grant
1

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.

f = (n = #;
     l = 0; 
     While[n > 0,
      m = Floor[Log2[1 + n]];
      l += 10^(m - 1);
      n -= 2^m - 1
     ]; l)&

Uso:

f[1000000000000000000]

Salida:

11011110000010110110101100111010011101100100000000000001102

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:

Timing[Block[{$MaxExtraPrecision = Infinity}, f[10^8000]];]

Salida:

{1.060807, Null}
Cuenta
fuente
1

C, 95 bytes

void f(unsigned long i,int*b){for(unsigned long a=~0,m=0;a;a/=2,b+=!!m)m|=*b=i/a,i-=a**b;*b=3;}

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 valor 3(que no puede ocurrir en la salida). No tenemos que manejar la entrada de 0(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

void f(unsigned long i,int*b)
{
    for (unsigned long a=~0, m=0;  a;  a/=2, b+=(m!=0)) {
        *b = i/a;               /* rounds down */
        i -= *b * a;
        m = m | *b;             /* m != 0 after leading zeros */
    }
    *b=3;                       /* add terminator */
}

Operamos por sustracción sucesiva, comenzando con el dígito más significativo. La única complicación es que usamos la variable mpara evitar imprimir ceros a la izquierda. Se unsigned long longpuede 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 intbúfer de matriz en una cadena de dígitos imprimible. El tiempo de ejecución es inferior a un milisegundo para la entrada 1000000000000000000.

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char**argv)
{
    while (*++argv) {
        unsigned long i = strtoul(*argv, NULL, 10);
        int result[1024];
        f(i,result);

        /* convert to string */
        char s[1024];
        {char*d=s;int*p=result;while(*p!=3)*d++=*p+++'0';*d=0;}
        printf("%lu = %s\n", i, s);
    }

    return EXIT_SUCCESS;
}

Resultados de la prueba

$ ./51517 $(seq 20)
1 = 1
2 = 2
3 = 10
4 = 11
5 = 12
6 = 20
7 = 100
8 = 101
9 = 102
10 = 110
11 = 111
12 = 112
13 = 120
14 = 200
15 = 1000
16 = 1001
17 = 1002
18 = 1010
19 = 1011
20 = 1012
Toby Speight
fuente
Supongo que una versión de C ++ es similar, pero puede usarse auto a=~0ullpara una ligera ventaja ...
Toby Speight
0

CoffeeScript, 92 69 bytes

Según la respuesta y las actualizaciones de Qwertiy :

f=(n)->s='1';(s=s.replace /(.?2|.$)/,(m)->[1,2,10][+m]||20)while--n;s

# older version, 92 bytes
f=(n)->s='1';(s=s.replace /(^2|02|12|20|.$)/,(m)->{0:1,1:2,2:10,12:20,20:100}[+m])while--n;s
rink.attendant.6
fuente
2
Convertirme a otro idioma sin siquiera una simple optimización eliminando llaves innecesarias en la expresión regular no me parece genial ...
Qwertiy
@Qwertiy He proporcionado atribución a su respuesta, y con ambas respuestas no puedo producir los mismos resultados sin los corchetes en la expresión regular
rink.attendant.6
Todo el suceso se reemplaza. ¿Por qué necesitas que esté dentro del grupo? La versión JS funciona en Firefox sin corchetes.
Qwertiy
0

Japt , 31 bytes

_r/?2|.$/g_÷C ç20 ª°Zs3}}gU['0]

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

X{Xr/?2|.$/gZ{Z÷C ç20 ||++Zs3}}gU['0]

X{     Declare a function...
Xr       Accept a string, replace the regex...
/?2|.$/g   /.?2|.$/   (g is needed to match *only once*, opposite of JS)
Z{       ...with the function... (matched string will be 0,1,2,02 or 12)
Z÷C        Implicitly cast the matched string into number, divide by 12
ç20        Repeat "20" that many times (discard fractions)
||         If the above results in "", use the next one instead
++Z        Increment the value
s3         Convert to base-3 string (so 0,1,2 becomes 1,2,10)
}}
gU['0] Repeatedly apply the function on "0", U (input) times
Bubbler
fuente
0

Stax , 16 bytes

üxëàè£öΦGΩ│Je5█ò

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.

z       push []
{       start block for while loop
 |X:2N  -log2(++x)
 {^}&   increment array at index (pad with 0s if necessary)
 xc:G-X unset high bit of x; write back to x register
w       while; loop until x is falsy (0)
$       convert to string

Ejecute este

recursivo
fuente