La palabra infinita de Fibonacci es una secuencia específica e infinita de dígitos binarios, que se calculan mediante la concatenación repetida de palabras binarias finitas.
Definamos que una secuencia de palabras de tipo Fibonacci (o FTW secuencia ) es cualquier secuencia de ⟨W n ⟩ que se forma como sigue.
Comience con dos matrices arbitrarias de dígitos binarios. Llamemos a estas matrices W -1 y W 0 .
Para cada n> 0 , deje W n ≔ W n-1 ∥ W n-2 , donde ∥ denota concatenación.
Una consecuencia de la definición recursiva es que W n es siempre un prefijo de W n + 1 y, por lo tanto, de todo W k tal que k> n . En un sentido, esto significa que la secuencia de ⟨W n ⟩ converge a una palabra infinito.
Formalmente, dejemos que W ∞ sea la única matriz infinita tal que W n sea un prefijo de W ∞ para todos n ≥ 0 .
Llamaremos a cualquier palabra infinita formada por el proceso anterior un FTW infinito .
Tarea
Escriba un programa o función que acepte dos palabras binarias W -1 y W 0 como entrada e imprima W ∞ , respetando las siguientes reglas adicionales:
Puede aceptar las palabras en cualquier orden; como dos matrices, una matriz de matrices, dos cadenas, una matriz de cadenas o una sola cadena con un delimitador de su elección.
Puede imprimir los dígitos de la palabra infinita sin un delimitador o con un delimitador consistente entre cada par de dígitos adyacentes.
Para todos los propósitos, suponga que su código nunca se quedará sin memoria y que sus tipos de datos no se desbordan.
En particular, esto significa que cualquier salida a STDOUT o STDERR que sea el resultado de un bloqueo se ignorará.
Si ejecuto su código en mi máquina (Intel i7-3770, 16 GiB RAM, Fedora 21) durante un minuto y canalizo su salida
wc -c
, debe imprimir al menos un millón de dígitos de W ∞ para (W -1 , W 0 ) = (1, 0) .Aplican reglas estándar de código de golf .
Ejemplo
Deje W -1 = 1 y W 0 = 0 .
Entonces W 1 = 01 , W 2 = 010 , W 3 = 01001 , W 4 = 01001010 … y W ∞ = 010010100100101001010… .
Esta es la palabra infinita de Fibonacci.
Casos de prueba
Todos los casos de prueba contienen los primeros 1,000 dígitos del FTW infinito.
Input: 1 0
Output: 0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001
Input: 0 01
Output: 0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001
Input: 11 000
Output: 0001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011
Input: 10 010
Output: 0101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010
Input: 101 110
Output: 1101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101
Respuestas:
Pyth, 8 bytes
Entrada en el formulario
"W-1", "W0"
.Prueba de finalización:
Prueba de corrección:
Aquí está la serie como generada internamente. Está impreso en concatenación por el programa.
Compare con lo siguiente, impreso en concatenación, que es simplemente la cadena agregada a la cadena anterior en cada paso:
Queremos demostrar que son equivalentes.
Claramente, son los mismos en los primeros pasos. Vamos a compararlos después de un momento:
Vemos que los pares de cadenas son alternativamente de las formas:
Donde ayb son secuencias arbitrarias en 0s y 1s. Continuemos la secuencia por un momento, para demostrar que continúa para siempre por inducción:
2 pasos después, es de la forma correcta.
2 pasos después, es de la forma correcta.
Entonces, por inducción, las cadenas siempre coinciden una vez concatenadas.
fuente
W0
, pero en lugar de imprimirW1
se imprimeW-1 || W0
, que es el orden de concatenación "equivocado". Creo que esto es equivalente, pero no he encontrado una prueba ...Haskell, 15 bytes
La función infija
%
produce una cadena infinita, que Haskell imprime para siempre porque Haskell es genial así.La idea recursiva es similar a la solución de Zgarb . Al escribir
f
para la función%
y+
para la concatenación de cadenas, implementa:La cadena de salida infinita comienza con
w
, y el resto de la misma es el resultado de las cadenas con desplazamiento de Fibonacciw
yv+w
.Esto no tiene problemas para generar un millón de caracteres en un minuto.
fuente
Haskell, 31 bytes
Esto define una función infija
#
que toma dos cadenas y devuelve una cadena infinita. Uso:Si consulto el elemento millonésimo de la secuencia definida por "1" y "0", incluso el intérprete en línea imprime el resultado en menos de un segundo:
Explicación
Básicamente, sabemos eso
w#v == v#(v++w)
y comenzamosw#v
conv
, y usamos estos hechos para definir el resultado. Como Haskell es vago, esto "mágicamente" simplemente funciona.fuente
Pip, 8 bytes
¡Hola, atado con Pyth!
Definición recursiva directa tomada de la respuesta de Haskell de xnor . Con espacios añadidos para mayor claridad:
Cada programa en la pipa es una función implícita que lleva a los argumentos de línea de comandos como sus argumentos (asignados a las variables
a
a travése
) e imprime su valor de retorno.O
es un operador que genera y luego devuelve su operando, por lo que lo primero que sucede aquí es que se muestra el segundo argumento (sin nueva línea final).Ahora, la sintaxis inspirada
(f x y)
en Lisp en Pip es una llamada de función, equivalente af(x,y)
en lenguajes tipo C. Laf
variable se refiere a la función actual, en este caso, el programa de nivel superior. Por lo tanto, el programa se llama recursivamente conb
ya.b
como los nuevos argumentos.Me sorprendió gratamente descubrir que este enfoque es bastante rápido:
En mi máquina Ubuntu, el programa tarda unos 30 segundos en alcanzar la profundidad máxima de recursión, momento en el que se ha impreso en algún lugar de más de mil millones de dígitos.
Esta solución iterativa es un poco más rápida y consume menos memoria, a costa de un byte:
fuente
CJam,
1211 bytesEsto toma las dos palabras en líneas separadas, en el orden opuesto, por ej.
da
Explicación
La idea es construir la palabra ingenuamente (recordando la palabra actual y añadiéndole la anterior) y mientras lo hacemos, imprimimos lo que acabamos de agregar (para no repetir el prefijo que ya estaba impreso) . Para evitar tener que manejar el punto de partida por separado, partimos de una palabra vacía, de modo que W 0 es lo primero que agregamos (e imprimimos).
fuente
PowerShell,
9776 bytesEditar - Umm, escribir
$e.substring($b.length)
después de que acabamos de concatenar$a
y$b
juntos es equivalente a escribir solo$a
... derp.Wow, detallado. PowerShell, por defecto, escupirá una nueva línea cada vez que envíe algo. Realmente, la única forma de evitar eso es con
write-host -n
(abreviatura de-NoNewLine
), y eso mata absolutamente la longitud aquí.En esencia, esta itera a través de la secuencia, la construcción
$e
como el "actual" W n medida que avanzamos. Sin embargo, dado que queremos construir la palabra infinita en lugar de la secuencia, aprovechamos nuestras variables anteriores para imprimir el sufijo$a
que se rellenó en nuestro bucle anterior. Luego configuramos nuestras variables para la próxima ronda y repetimos el ciclo. Tenga en cuenta que esto espera que la entrada se delimite explícitamente como cadenas, de lo contrario, el+
operador se utiliza para la aritmética en lugar de la concatenación.Ejemplo:
fuente
APL,
2418El uso de la formulación de xnor permitió eliminar algunos caracteres.
En una máquina infinita en tiempo infinito, en realidad imprimiría W ∞ tres veces, primero de forma incremental mientras se ejecuta el ciclo, y luego dos veces como resultado de la expresión completa cuando el
⍣≡
operador del punto fijo finalmente regresa.No es muy rápido pero lo suficientemente rápido. En GNU APL:
fuente
⍣≡
; Suena muy útil.Puro golpe, 58
Me quedo sin memoria antes de 1 minuto, pero tengo muchos dígitos para entonces; después de 10 segundos tengo 100 millones de dígitos:
fuente
Mathematica, 56 bytes
fuente
C, 76 (gcc)
Esta es una impresora recursiva bastante sencilla, implementada como una función anidada (una extensión GNU C no compatible con clang) para evitar tener que pasar
v
.p(n)
imprime W n-2 , donde W -1 y W 0 deben proporcionarse env[1]
yv[2]
. Inicialmente, esto llamap(4)
a imprimir W 2 . Luego realiza un bucle: llamap(3)
a imprimir W 1 , haciendo que la salida completa sea W 2 W 1 , que es W 3 . Luego llamap(4)
para imprimir W 2 , haciendo que la salida completa sea W4 , etc. El rendimiento es ligeramente mejor que mi respuesta anterior: estoy viendo 1875034112 valores en un minuto.C, 81 (sonido metálico)
Este es un enfoque completamente diferente al anterior que creo que vale la pena seguir, a pesar de que es peor.
Esto tiene todo tipo de comportamiento indefinido, principalmente por diversión. Funciona con clang 3.6.2 en Linux y con clang 3.5.2 en Cygwin para los casos de prueba en la pregunta, con o sin opciones especiales de línea de comandos. No se rompe cuando las optimizaciones están habilitadas.
No funciona con otros compiladores.
Acepto las palabras como argumentos de línea de comandos en formato de cadena.
Yo uso nueva línea como delimitador consistente.
Accedo
s
fuera de los límites. Esto seguramente debe terminar con una falla de seguridad o una infracción de acceso en algún momento.s
sucede que se coloca al final del segmento de datos, por lo que no debería bloquear otras variables y dar una salida incorrecta antes de ese segfault. Ojalá.Al realizar la prueba
{ ./program 1 0 | tr -d '\n' & sleep 60; kill $!; } | wc -c
, obtengo 1816784896 dígitos en un minuto en mi máquina cuando se compiló el programa-O3
y 1596678144 cuando se compiló con optimizaciones marcadas.Sin golf, sin UB, con explicación:
fuente
s[]
truco malvado funciona bien con clang (solo lo instalé). Estoy bastante sorprendido de que esto realmente funcione. Para todos los propósitos, suponga que su código nunca se quedará sin memoria y que sus tipos de datos no se desbordan. Desafortunadamente, eso significa que simplemente imprimir W97 no se considera válido. ¿Podrías llamarp
recursivamente? Eso eliminaría la necesidad de amain
.p
ap
sí mismo sin agregar más código, pero si encuentro la forma, volveré a editar.Javascript (53 bytes)
La entrada debe ser una cadena y no un número (
'0'
y no solo0
).fuente
Perl 5,
455549 bytes44 bytes, más 1 para
-E
lugar de-e
Usar como p. Ej.
Esto imprime aproximaciones sucesivas a W ∞ y, por lo tanto, si espera lo suficiente, imprime, en su última línea de salida, W ∞ a cualquier longitud deseada, según sea necesario. Los dígitos de la palabra se concatenan sin un delimitador.
Desde que estoy en Windows, lo probé para "al menos un millón de dígitos de W requisito de ∞ " ejecutándolo con la salida redirigida a un archivo y eliminándolo después de aproximadamente 59 segundos, luego ejecuté GnuWin32
wc -L
, que imprimió 701408733.Actualizar:
El OP aclaró en un comentario sobre esta respuesta (y probablemente debería haberme dado cuenta de todos modos) que la salida adicional que precede a W qu descalifica lo anterior. Entonces, en cambio, aquí hay una solución de 55 bytes que imprime solo W ∞ :
Se usa de la misma manera, pero con los argumentos en orden inverso , y no requiere
-E
:Sin duda, se puede jugar más al golf, pero no veo cómo hacerlo en este momento.
Actualización adicional:
Dennis recortó cinco bytes utilizando
-a
(leyendo<>
para eliminarsub
) y reasignando el parámetro pasado aprint
final delredo
bloque:Con
-ane
y leyendo desde<>
(ambas entradas en una línea, separadas por espacios, en orden inverso); 48 + 2 bytes:Y, en base a eso, afeité un byte más (igual que el anterior, pero ahora las entradas están en el orden correcto); 47 + 2 bytes:
fuente
REXX , 48
ftw.rex
exec ftw.rex 0 1
Actualmente no puedo probar el rendimiento porque utilicé un compilador en línea para escribirlo. El "para siempre" se puede reemplazar con cualquier número donde están los números impresos de ftw (número + 2).
También escribí una pequeña solución (desordenada) en Prolog. No descubrí cómo probar el rendimiento con este, pero de todos modos es probablemente atroz.
fuente
Python 2, 67 bytes
Acepta la entrada como un par de cadenas separadas por comas:
"1","0"
por ejemplo, en la pregunta.No hay intérprete en línea porque los bucles infinitos son malos.
La salida en búfer me hizo ganar muchos bytes. :(Gracias Dennis por señalar que 1 dígito por línea es válido.Tiempo en mi máquina (significativamente más débil):
fuente
Dyalog APL, 9
Este se usa
∇
para definir una función recursiva. Es una traducción directa de esta respuesta de Python 3 de xnor . Toma W 0 como derecho y W −1 como argumento izquierdo, ambos deben ser vectores de caracteres.fuente
Minkolang 0.11 , 62 bytes
Pruébalo aquí Espera entrada en el orden W 0 , W -1 con un espacio en el medio.
Explicación
La metaexplicación de lo siguiente es que, en este momento, tenemos dos números seguidos de una cadena de "0" y "1" sin separación. Si las longitudes de W 0 y W -1 son
a
yb
, respectivamente, entonces los dos números al frente de la pila son<a+b>
y<a>
, en ese orden. La palabra formada al concatenar W i + 1 y W i , es decir, W i + 1 + W i , es igual a 2 * W i + 1 - W i . Entonces, el siguiente código duplica la pila (2 * W i + 1 ), aparece en la parte superior<a>
elementos (- W i ), y luego reemplaza<a+b>
y<a>
con sus sucesores,<a+2b>
y<b>
.fuente
Pitón 3, 32
La misma idea recursiva que mi respuesta de Haskell , excepto que el prefijo se imprime porque Python no puede manejar cadenas infinitas.
Usé un truco de Sp3000 para imprimir sin espacios al colocar la cadena como
end
argumento en Python 3fuente
Perl, 32 bytes
Contando el shebang como dos, la entrada se toma de stdin, el espacio se separa como W 0 , W -1 . Salida de 1 MB veces a ~ 15 ms, la mayoría de los cuales se pueden atribuir al lanzamiento del intérprete.
Uso de muestra
fuente
Prólogo, 69 bytes
Entrada de ejemplo: p ('1', '0')
No he encontrado una manera de eliminar la escritura adicional.
Debería poder mejorar esto si descubro cómo hacerlo.
fuente