Condiciones
Un gusano es cualquier lista de enteros no negativos, y su elemento más a la derecha (es decir, último ) se llama cabeza . Si la cabeza no es 0, el gusano tiene un segmento activo que consiste en el bloque contiguo más largo de elementos que incluye la cabeza y tiene todos sus elementos al menos tan grandes como la cabeza . El segmento activo reducido es el segmento activo con la cabeza disminuida en 1. Por ejemplo, el gusano 3 1 2 3 2
tiene segmento activo 2 3 2
, y el segmento activo reducido es 2 3 1
.
Reglas de evolución.
Un gusano evoluciona paso a paso de la siguiente manera:
En el paso t (= 1, 2, 3, ...),
si el encabezado es 0: elimine el encabezado
más: reemplace el segmento activo por t + 1 copias concatenadas del segmento activo reducido.
Hecho : Cualquier gusano eventualmente evoluciona a una lista vacía , y el número de pasos para hacerlo es la vida del gusano .
(Los detalles se pueden encontrar en The Worm Principle , un documento de LD Beklemishev. El uso de "lista" para referirse a una secuencia finita, y "cabeza" para referirse a su último elemento, se toma de este documento; no debe confundirse con el uso común de las listas como un tipo de datos abstracto , donde head generalmente significa el primer elemento).
Ejemplos (segmento activo entre paréntesis)
Gusano: 0,1
step worm
0(1)
1 0 0 0
2 0 0
3 0
4 <- lifetime = 4
Gusano: 1,0
step worm
1 0
1 (1)
2 0 0 0
3 0 0
4 0
5 <- lifetime = 5
Gusano: 1,1
step worm
(1 1)
1 1 0 1 0
2 1 0(1)
3 1 0 0 0 0 0
4 1 0 0 0 0
5 1 0 0 0
...
8 (1)
9 0 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0
...
18 0
19 <- lifetime = 19
Gusano: 2
step worm
(2)
1 (1 1)
2 1 0 1 0 1 0
3 1 0 1 0(1)
4 1 0 1 0 0 0 0 0 0
5 1 0 1 0 0 0 0 0
6 1 0 1 0 0 0 0
...
10 1 0(1)
11 1 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0
...
24 (1)
25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
...
50 0
51 <- lifetime = 51
Gusano: 2,1
(2 1)
1 2 0 2 0
2 2 0(2)
3 2 0(1 1 1 1)
4 2 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0
5 2 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0(1 1 1)
6 2 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0
7 2 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0(1 1)
8 2 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0{1 0}^9
...
?? <- lifetime = ??
Gusano: 3
step worm
(3)
1 (2 2)
2 (2 1 2 1 2 1)
3 2 1 2 1 2 0 2 1 2 1 2 0 2 1 2 1 2 0 2 1 2 1 2 0
4 2 1 2 1 2 0 2 1 2 1 2 0 2 1 2 1 2 0 2 1 2 1(2)
5 2 1 2 1 2 0 2 1 2 1 2 0 2 1 2 1 2 0(2 1 2 1 1 1 1 1 1 1)
6 2 1 2 1 2 0 2 1 2 1 2 0 2 1 2 1 2 0{2 1 2 1 1 1 1 1 1 0}^7
7 2 1 2 1 2 0 2 1 2 1 2 0 2 1 2 1 2 0{2 1 2 1 1 1 1 1 1 0}^6 (2 1 2 1 1 1 1 1 1)
... ...
?? <- lifetime = ??
Aparte
La vida útil de los gusanos suele ser enorme, como lo demuestran los siguientes límites inferiores en términos de la jerarquía estándar de funciones de rápido crecimiento f α :
worm lower bound on lifetime
---------------- ------------------------------------------
11..10 (k 1s) f_k(2)
2 f_ω(2)
211..1 (k 1s) f_(ω+k)(2)
2121..212 (k 2s) f_(ωk)(2)
22..2 (k 2s) f_(ω^k)(2)
3 f_(ω^ω)(2)
...
n f_(ω^ω^..^ω)(2) (n-1 ωs) > f_(ε_0) (n-1)
Sorprendentemente, el gusano [3] ya tiene una vida que supera con creces el número de Graham , G:
f ω ω (2) = f ω 2 (2) = f ω2 (2) = f ω + 2 (2) = f ω + 1 (f ω + 1 (2)) >> f ω + 1 (64) > G.
Code Golf Challenge
Escriba el subprograma de funciones más corto posible con el siguiente comportamiento:
Entrada : cualquier gusano.
Salida : la vida útil del gusano.El tamaño del código se mide en bytes.
Aquí hay un ejemplo (Python, golf a unos 167 bytes):
from itertools import *
def T(w):
w=w[::-1]
t=0
while w:
t+=1
if w[0]:a=list(takewhile(lambda e:e>=w[0],w));a[0]-=1;w=a*(t+1)+w[len(a):]
else:w=w[1:]
return t
NB : Si t (n) es la vida útil del gusano [n], entonces la tasa de crecimiento de t (n) es aproximadamente la de la función Goodstein . Entonces, si esto se puede jugar por debajo de los 100 bytes, bien podría dar una respuesta ganadora a la pregunta imprimible del número más grande . (Para esa respuesta, la tasa de crecimiento podría acelerarse enormemente al iniciar siempre el contador de pasos en n, el mismo valor que el gusano [n], en lugar de comenzarlo en 0.)
w[0]
el elemento más a la izquierda de esa lista?2 1
que podría ser demasiado pedir en un tiempo razonable, pero una prueba útil es que la secuencia debe comenzar(2 1)
,2 0 2 0
,2 0 (2)
,2 0 (1 1 1 1)
, ...Respuestas:
GolfScript (
5654 caracteres)Demostración en línea
Creo que el truco clave aquí es probablemente mantener el gusano en orden inverso. Eso significa que es bastante compacto encontrar la longitud del segmento activo:
.0+.({<}+??
(donde0
se agrega como protección para garantizar que encontremos un elemento más pequeño que la cabeza).Como comentario aparte, algunos análisis de la vida útil del gusano. Denotaré el gusano como
age, head tail
(es decir, en orden inverso a la notación de la pregunta) usando exponentes para indicar la repetición en la cabeza y la cola: por ejemplo,2^3
es2 2 2
.Lema : para cualquier segmento activo
xs
, existe una funciónf_xs
que seage, xs 0 tail
transforma enf_xs(age), tail
.Prueba: ningún segmento activo puede contener a
0
, por lo que la edad en el momento en que borramos todo antes de que la cola sea independiente de la cola y, por lo tanto, es solo una función dexs
.Lema : para cualquier segmento activo
xs
, el gusanoage, xs
muere a la edadf_xs(age) - 1
.Prueba: por el lema anterior, se
age, xs 0
transforma enf_xs(age), []
. El paso final es la eliminación de eso0
, que no se tocó anteriormente porque nunca puede formar parte de un segmento activo.Con esos dos lemmata, podemos estudiar algunos segmentos activos simples.
para
n > 0
,entonces
f_{1^n} = x -> f_{1^{n-1}}^{x+1}(x+2)
(con basef_{[]} = x -> x+1
, o si lo prefieref_{1} = x -> 2x+3
). Vemos quef_{1^n}(x) ~ A(n+1, x)
dóndeA
está la función Ackermann – Péter.Eso es suficiente para manejarlo
1 2
(2 1
en la notación de la pregunta):Entonces, dada la entrada
2 1
, esperamos salida ~A(A(5,4), A(5,4))
.y realmente puedo comenzar a comprender por qué esta función crece tan locamente.
fuente
9{-1%0\{\)\.0={.0+.({<}+??\((\+.@<2$*\+}{(;}if.}do;}:L~
calcula la vida útil del gusano [9], que supera con creces el número de Graham, y puede ser Golf más lejos.GolfScript,
6962 caracteresLa función
C
espera el gusano en la pila y lo reemplaza por el resultado.Ejemplos:
fuente
*
y^
no se están utilizando como operadores aritméticos de multiplicación. y exponenciar. Ciertamente, si desea enviar su propia respuesta (sin duda superior) allí, con mucho gusto eliminaré la mía.Ruby - 131 caracteres
Sé que esto no puede competir con las soluciones de GolfScript anteriores y estoy bastante seguro de que se puede reducir una puntuación o más caracteres, pero sinceramente, estoy feliz de haber podido resolver el problema sin problemas. Gran rompecabezas!
Mi solución previa al golf de la que se deriva lo anterior:
fuente
if foo==0
se pueden recortarif foo<1
. Eso puede ahorrarte un char aquí.reverse
.else
reducir la cláusula a una línea y luego cambiarlaif..else..end
por una declaración ternaria. También podría usar una lambda para salvar algunos caracteres, creo.Sclipting (43 caracteres)
Esto espera la entrada como una lista separada por espacios. Esto genera la respuesta correcta para
1 1
y2
, pero para2 1
o3
tarda demasiado, así que dejé de esperar a que termine.Con comentario:
fuente
k (83)
worm:{-1+*({x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}.)/(1;|,/x)}
esto probablemente se pueda jugar más, ya que solo implementa la recurrencia de manera bastante directa.
La función de evolución básica
{x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}
, es de 65 caracteres, y utiliza algunos trucos para dejar de aumentar la edad cuando el gusano muere. el contenedor coacciona una entrada de un entero entero a una lista, invierte la entrada (es más corto escribir la recurrencia en términos de un gusano invertido desde su notación), solicita el punto fijo, selecciona la edad como salida y ajusta el resultado para dar cuenta del exceso en la última generación.Si hago la coerción y la inversión manualmente, se reduce a 80 (
{-1+*({x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}.)/(1;x)}
).algunos ejemplos:
desafortunadamente, probablemente no sea de mucha utilidad para la impresión de número más grande , excepto en un sentido muy teórico, ya que es bastante lento, está limitado a enteros de 64 bits y probablemente no sea especialmente eficiente en memoria.
en particular,
worm 2 1
yworm 3
simplemente abandonar (y probablemente tiraría'wsfull
(sin memoria) si dejo que sigan).fuente
` to switch from
q`k
y pegue mi código. Alternativamente, puede guardar mi código en un archivo con una.k
extensión y cargarlo en el intérprete.APL (Dyalog Unicode) , 52 bytes SBCS
Guardado 7 bytes gracias a @ngn y @ Adám.
Pruébalo en línea!
Explicación:
fuente
Scala, 198
Uso:
fuente
K, 95
.
fuente
C (gcc) , 396 bytes
Pruébalo en línea!
Sé que estoy EXTREMADAMENTE tarde a la fiesta, pero pensé en intentarlo en C, que requería una implementación de lista enlazada. Realmente no se juega al golf además de cambiar todos los identificadores a caracteres individuales, ¡pero funciona!
En general, estoy bastante contento teniendo en cuenta que este es el tercer programa C / C ++ que he escrito.
fuente
Haskell , 84 bytes
Pruébalo en línea!
Gracias a @xnor por dos bytes.
Siento que debería haber una buena manera de factorizar el incremento común, pero aún no he encontrado uno corto.
fuente
n
baje por 1.(n+1)!
dos veces, pero mi intento solo empató.Perl 5
-pa
, 92 bytesPruébalo en línea!
fuente
Stax , 31 bytes
Ejecutar y depurarlo
fuente