La rotación de una cadena se realiza dividiendo una cadena en dos partes e invirtiendo su orden, por ejemplo, "world! Hello,"es una rotación de "Hello, world!". Es posible crear programas que se pueden rotar para formar un programa diferente, pero aún válido. Considere este ejemplo en python:
print ")import sys; sys.stdout.write("
Se puede girar para formar
import sys; sys.stdout.write("print ")
Que es en sí un programa válido de Python.
Su desafío es escribir un programa que genere una rotación de sí mismo, que cuando se ejecute generará el programa original. ¡Los puntos de bonificación a cualquier entrada con una duración de ciclo superior a dos!
Este es el código de golf, la puntuación exacta será: (longitud del código) / (longitud del ciclo - 1).
EDITAR: ¡Tenemos un ganador (a menos que alguien más pueda superar un puntaje de 4)! Todavía estaría muy interesado en ver otras soluciones, ya sean contendientes o no.
fuente
Respuestas:
APL (158 caracteres, puntaje = 4)
Estoy usando Dyalog APL aquí. El número de ciclos se puede aumentar en uno agregando
0(0 seguido de un espacio) al final de la expresión y al final de la cadena (antes'''). La longitud del ciclo es(# 0's) + 1y la longitud de la expresión es150 + 4*(cycle length)). Suponiendo que seguimos agregando ceros para siempre, el puntaje esLimit[(150 + 4*n)/(n - 1), n -> Infinity] = 4dóndenestá la duración del ciclo.Aquí hay un ejemplo con la duración del ciclo = 6:
192 caracteres, puntuación = 2
Dependiendo de la implementación, un punto de falla podría ser cuando el entero prefijado a la cadena es demasiado grande. Sin embargo, en teoría, podemos agregar un ciclo agregando dos caracteres:
1a al final de la cadena (antes''') y1a al final de toda la línea.200 caracteres, puntuación = 1
Mi implementación APL no tiene enteros de precisión ilimitados de manera predeterminada, por lo que el entero se convierte en flotante cuando se vuelve demasiado grande, lo que hace que la salida sea incorrecta. Entonces este es el más meticuloso, pero teóricamente (ya sea a mano o con un intérprete APL diferente), debe tener una puntuación de 1. Simplemente agregue un
1al final de la expresión y obtendrá otro ciclo.Descripción general (con una quine más corta)
Voy a dar una visión general de la primera versión, porque creo que es probablemente la más fácil de comprender. Sin embargo, antes de abordar esa versión, vamos a considerar una quine simple en APL :
Descubrí que una de las mejores maneras de comprender algunas expresiones APL es mirar la salida en toda la cascada de operadores / funciones. Todos los operadores y funciones en APL son asociativos a la derecha y tienen la misma precedencia, así que aquí está, de derecha a izquierda:
'''1⌽22⍴11⍴''': Esto es solo un literal de cadena (una lista de caracteres).''es la forma APL de escapar de las comillas simples. Salida:'1⌽22⍴11⍴'.11⍴'''1⌽22⍴11⍴''': Aquí, rediseñamos (⍴) la cadena para que sea de longitud11. Debido a que la longitud de la cadena es inferior a 11, se repite (es decir,5⍴'abc'produciría'abcab'). Salida:'1⌽22⍴11⍴''. Así que ahora tenemos dos comillas al final: ¡estamos llegando a alguna parte!22⍴11⍴'''1⌽22⍴11⍴''': Del mismo modo, ahora rediseñamos nuestra salida anterior para que sea de longitud22. Salida:'1⌽22⍴11⍴'''1⌽22⍴11⍴''. Ya casi llegamos, solo necesitamos mover la primera cita al final.1⌽22⍴11⍴'''1⌽22⍴11⍴''': Aquí, rotamos (⌽) la lista de caracteres por1. Esto mueve el primer carácter de la cadena al final. Como otro ejemplo,2⌽'abcdef'regresa'cdefab'. Salida:1⌽22⍴11⍴'''1⌽22⍴11⍴'''.La quine giratoria
Esa quine corta es la base principal de nuestra quine giratoria. Ahora, con eso en mente, echemos un vistazo a nuestra quine:
{ ... }define una función sin nombre, que es donde haremos el trabajo. Tenga en cuenta que las funciones en APL toman un argumento derecho, denotado por⍵, y un argumento izquierdo opcional, denotado por⍺(think infix). Queremos alimentar esta función tanto con nuestra cadena de quine como con algo que nos ayude a crear un número arbitrario de ciclos. Para hacer las cosas más fáciles para nosotros (y para cualquiera que quiera agregar ciclos), hacemos que la cadena de quine sea el argumento izquierdo. El argumento correcto, entonces, es donde ponemos nuestra lista de ciclos. 2 o más elementos separados por un espacio crean una lista, por lo que en este ejemplo, tenemos una lista de 2 elementos que consiste en ay1a0.Podemos ver que la función se parece a la quine de antes. Tenemos la misma
...⌽...⍴...⍴...forma de antes. Así que eso es bueno, ¡al menos lo entendemos! Vamos a profundizar más en las elipses, a partir de todo lo que después de la última⍴:⊃,/(~^/¨⍺=0)/⍺.⍺=0devuelve una lista, en este caso, con la misma forma que⍺, donde cada elemento⍺se reemplaza por a1si es igual a0, y a de lo0contrario. Esto se realiza de forma recursiva; así que si tenemos una lista de una lista de una lista de caracteres, los caracteres individuales se probarán contra 0, y obtendrá una lista de una lista de una lista de valores binarios.⍺consiste solo en nuestra cadena, recuperamos una lista de 0. De lo contrario, nuestro argumento izquierdo tiene algunos 0 prefijados (por ejemplo,0 0 0 'quinestring'), por lo que es una lista que consta de 0 y otra lista, nuestra cadena. Entonces nuestra salida se ve así1 1 1 <sub-list of zeros>.^/¨⍺=0: Aplicamos la función derivada^/, que reduce (/) usando la función lógica AND (^), a cada¨elemento ( ) de⍺=0. Esto es para aplanar la sublista de ceros para que podamos considerar la cadena de quine como un valor binario. Considerando el ejemplo anterior, la salida sería1 1 1 0.~: Binarios NO cada uno de los valores de antes (por ejemplo, volver0 0 0 1).(~^/¨⍺=0)/⍺: Para cada elemento en⍺, lo replicamos (/) el número de veces dado por el elemento correspondiente en el argumento izquierdo. Esto elimina todos los 0, dejándonos solo con nuestra cadena de quine.⊃,/es una documentación necesaria para garantizar que recuperemos una lista de caracteres aplanada, reduciendo el resultado con la función de concatenación (,). Si la entrada ya es una lista aplanada (es decir, el argumento izquierdo de nuestra función principal es solo la cadena), obtenemos una lista de 1 elemento que contiene esa lista. En el otro caso, cuando tenemos una lista que consiste en una sublista para la cadena, recuperamos lo mismo (una lista con una sublista). Luego desempaquetamos esto (⊃), dándonos solo el primer elemento de la lista (es decir, la sublista de caracteres). Esto puede parecer innecesario, pero de lo contrario estaríamos tratando de remodelar una lista de 1 elemento.A continuación, observamos la longitud dada para la primera remodelación, entre paréntesis:
⍺,⍵: Concatenamos el argumento correcto con el primer argumento⊃,/⍺,⍵: Igual que antes: aplanar la lista.+/0=⊃,/⍺,⍵: Suma el número de ceros en la lista reduciendo (/) usando la función suma (+).2×+/0=⊃,/⍺,⍵: Multiplica ese número por dos.z←2×+/0=⊃,/⍺,⍵: Asignar (←) el resultado a una variable,z. En resumen,zahora es el doble del número de ceros encontrados en los argumentos izquierdo y derecho.77+z←2×+/0=⊃,/⍺,⍵: Luego agregamos77, para los caracteres en la cadena de quine, ignorando todo después del espacio siguiente1. Como en el ejemplo de quine inicial, agregamos 1 a la longitud de la cadena para obtener otra comilla simple.'{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 ''El argumento para la remodelación que sigue es simple y refleja la quine corta (2 veces la longitud de la primera remodelación). Nuestra salida ahora es:
Ahora para el paso final, donde calculamos cuánto girar la cadena de salida:
0(y otro espacio) se mueva al principio también, queremos rotarlo 3 caracteres adicionales hacia atrás.+/+/¨⍺=0: Sume el número de ceros en el argumento izquierdo . El primero (desde la derecha)+/¨suma el recuento de cada elemento (es decir, una sublista o solo un número entero), y el segundo+/nos da la suma de esa lista resultante.5+2×+/+/¨⍺=0: Multiplique por dos (para rotar los espacios también) y agregue 5 (el resultado que obtuvimos antes).-para manejar el caso cuando llegamos al final de nuestro ciclo:(3+z)×^/⍵: Y todos los elementos en el argumento correcto juntos para ver si hemos llegado a nuestro final (1), y multiplicar eso por3+z.¡Y hemos terminado!
fuente
⍴operador (?). ¡Creo que tendré que leerlo todo un par de veces más antes de digerirlo completamente!GolfScript, 10046/9999 ≈ 1.0047 (puntaje asintótico 1)
OK, voy a intentar superar la entrada APL de DC con esto:
El código anterior no es la quine real: sentí que publicar una línea de 10kB no sería una muy buena idea. Por el contrario, ejecutar el código anterior una vez produce el programa GolfScript 10046-char real, que, cuando se itera como se especifica en la pregunta, genera 9999 rotaciones de sí mismo y, finalmente, de nuevo.
La duración del ciclo (y el programa) se puede ajustar cambiando la constante
9999. Por brevedad y conveniencia, mostraré cómo se ve la salida iterada si la constante se reduce a9:A medida que
9999aumenta la constante , la relación entre la duración del programa y la duración del ciclo (menos uno) tiende a uno. Estoy bastante seguro de que esta solución no puede ser mejor, al menos no asintóticamente. ;-)¿Como funciona?
GolfScript es un lenguaje bastante fácil de quines escritura en, ya que, básicamente, cualquier número literal actúa como un quine: por ejemplo, el programa GolfScript
12345salidas - usted lo adivinó -12345. Además, la concatenación de múltiples quines generalmente produce una quina. Por lo tanto, podría usar un número simple11111...111como la parte repetitiva de mi quine cíclico.Sin embargo, para hacer que la quine realmente circule, necesitamos llevar y ejecutar una "carga útil" no trivial. La quine más simple de GolfScript que se me ocurre que puede hacer es la siguiente:
Entonces, mi plan era prefijar una línea como esa con una constante numérica repetitiva, y usar una carga útil que corta un dígito del número y lo mueve al final del programa. Si el programa detecta que no hay una constante numérica delante de él (en cuyo caso el valor debajo de él en la pila será una cadena vacía, suponiendo que no haya entrada), en su lugar antepondrá una constante numérica de longitud fija delante de sí mismo.
Sin embargo, hay una arruga adicional: cuando se "ajusta", la carga útil también debe suprimir la salida del número después de sí misma. Normalmente, cuando finaliza un programa GolfScript, todos los valores en la pila se imprimen automáticamente, lo que sería un problema aquí.
Sin embargo, resulta que hay una forma indocumentada (AFAIK) para evitar eso: el intérprete realmente llama a la función predefinida
putspara realizar la impresión, por lo que redefinir esa función como un no-op suprime la salida automática. Por supuesto, esto también significa que primero debemos llamarnos aputsnosotros mismos para imprimir la parte de la pila que queremos imprimir.El código final parece bastante desordenado (incluso para GolfScript), pero al menos funciona. Sospecho que puede haber algunas formas inteligentes en las que aún no he pensado para eliminar algunos caracteres de la carga útil, pero para esta versión, principalmente me enfoqué en el puntaje asintótico.
fuente
puts{}:puts, aunque podría ver un argumento por{print}:putsel hecho de que una nueva línea en la salida significaría que no está estrictamente en bicicleta.]puts{}:putses necesario para la transición de{STUFF}.~111111111a111111111{STUFF}.~, de lo contrario, el número de1s al final del programa sigue creciendo y creciendo. (Sin{}embargo, parece innecesario; aparentemente, el intérprete de GolfScript permite la asignación desde una pila vacía.)HTML, menos infinito (casi)
-2
AA-10
AAAAAAAAAAY así sucesivamente ... Si alguien dice que está haciendo trampa, podemos discutirlo, pero he encontrado un agujero en cuestión :)
Entonces, supongo que todos entienden que el código sí, no tiene bucles, por lo que el bucle más largo es
0y teniendo en cuenta la longitud del programan, la puntuación esn / (0 - 1)o-n, puedo escribir un programa que tenganun número entero positivo grande, pero es inútil, porque todos lo entienden.fuente