La vida de un gusano

28

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

res
fuente
Estoy confundido por tu código. Dijiste que la cabeza es el elemento más a la derecha , pero en tu ejemplo de Python, ¿tratas a la cabeza como w[0]el elemento más a la izquierda de esa lista?
@LegoStormtroopr Si puede considerar que una lista tiene izquierda y derecha. Si solo considera el primero y el último, puede asignar el más a la derecha al primero o al último al leer la cadena inicial, que no es parte de la pregunta. Pero las entradas de función tampoco estaban estrictamente definidas.
Bob
@LegoStormtroopr - Buena captura; Corregí el código agregando una línea para invertir el gusano de entrada, cuya cabeza se supone que está a la derecha (es decir, el último elemento de la lista w). Es por eficiencia que el programa opera en el gusano invertido.
res
Conseguir la correcta respuesta de 2 1que 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), ...
Peter Taylor
1
@ThePlasmaRailgun: para parafrasear a Harvey Friedman, los números derivados de funciones en el nivel ε_0 en la jerarquía de rápido crecimiento (como la vida de gusanos) son completamente INNOTIZABLES en comparación con TREE (3) .
Res

Respuestas:

15

GolfScript ( 56 54 caracteres)

{-1%0\{\)\.0={.0+.({<}+??\((\+.@<2$*\+}{(;}if.}do;}:L;

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+.({<}+??(donde 0se 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^3es 2 2 2.

Lema : para cualquier segmento activo xs, existe una función f_xsque se age, xs 0 tailtransforma en f_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 de xs.

Lema : para cualquier segmento activo xs, el gusano age, xsmuere a la edad f_xs(age) - 1.

Prueba: por el lema anterior, se age, xs 0transforma en f_xs(age), []. El paso final es la eliminación de eso 0, 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,

age, 1^n 0 xs -> age+1, (0 1^{n-1})^{age+1} 0 xs
              == age+1, 0 (1^{n-1} 0)^{age+1} xs
              -> age+2, (1^{n-1} 0)^{age+1} xs
              -> f_{1^{n-1}}^{age+1}(age+2), xs

entonces f_{1^n} = x -> f_{1^{n-1}}^{x+1}(x+2)(con base f_{[]} = x -> x+1, o si lo prefiere f_{1} = x -> 2x+3). Vemos que f_{1^n}(x) ~ A(n+1, x)dónde Aestá la función Ackermann – Péter.

age, 2 0 xs -> age+1, 1^{age+1} 0 xs
            -> f_{1^{age+1}}(age+1)

Eso es suficiente para manejarlo 1 2( 2 1en la notación de la pregunta):

1, 1 2 -> 2, 0 2 0 2
       -> 3, 2 0 2
       -> f_{1^4}(4), 2
       -> f_{1^{f_{1^4}(4)+1}}(f_{1^4}(4)+1) - 1, []

Entonces, dada la entrada 2 1, esperamos salida ~ A(A(5,4), A(5,4)).

1, 3 -> 2, 2 2
     -> 3, 1 2 1 2 1 2
     -> 4, 0 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 2
     -> f_{21212}^4(5) - 1

age, 2 1 2 1 2 -> age+1, (1 1 2 1 2)^{age+1}
               -> age+2, 0 1 2 1 2 (1 1 2 1 2)^age
               -> age+3, 1 2 1 2 (1 1 2 1 2)^age

y realmente puedo comenzar a comprender por qué esta función crece tan locamente.

Peter Taylor
fuente
Muy genial. Creo que este programa también dará una respuesta ganadora al programa de terminación más corto cuyo tamaño de salida excede el número de Graham . (El ganador actual tiene 63 bytes de código Haskell). Por ejemplo, a 55 bytes, algo como (dado que soy propenso a errores de sintaxis) 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.
res
9

GolfScript, 69 62 caracteres

{0:?~%{(.{[(]{:^0=2$0+0=<}{\(@\+}/}{,:^}if;^?):?)*\+.}do;?}:C;

La función Cespera el gusano en la pila y lo reemplaza por el resultado.

Ejemplos:

> [1 1]
19

> [2]
51

> [1 1 0]
51
Howard
fuente
¡Fantástico! Seguramente puede modificar esto un poco para dar un ganador definitivo para la pregunta "Imprimible con el número más grande" .
Res
No te vi publicar nada allí, así que seguí adelante y publiqué una modificación de este código como lo que creo que es la respuesta ganadora hasta el momento, suponiendo que *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.
Res
7

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!

f=->w{t=0;w.reverse!;until w==[];t+=1;if w[0]<1;w.shift;else;h=w.take_while{|x|x>=w[0]};h[0]-=1;w.shift h.size;w=h*t+h+w;end;end;t}

Mi solución previa al golf de la que se deriva lo anterior:

def life_time(worm)
  step = 0
  worm.reverse!
  until worm.empty?
    step += 1
    if worm.first == 0
      worm.shift
    else
      head = worm.take_while{ |x| x >= worm.first }
      head[0] -= 1
      worm.shift(head.size)
      worm = head * (step + 1) + worm
    end
  end
  step
end
OI
fuente
Consejo genérico: muchos problemas de golf funcionan en enteros no negativos, en cuyo caso if foo==0se pueden recortar if foo<1. Eso puede ahorrarte un char aquí.
Peter Taylor
Por cierto, me parece fascinante que esto funcione sin un segundo reverse.
Peter Taylor
Ah, no lo hace. Simplemente funciona en los casos de prueba porque solo tienen segmentos activos palindrómicos.
Peter Taylor
Gracias por el consejo de golf, @PeterTaylor. Además, buena captura en el segundo reverso faltante. Lo he agregado. Intentaré reescribir esto de otra manera sin usar el reverso más adelante. Estoy bastante seguro de que puedo elsereducir la cláusula a una línea y luego cambiarla if..else..endpor una declaración ternaria. También podría usar una lambda para salvar algunos caracteres, creo.
OI
6

Sclipting (43 caracteres)

글坼가⑴감套擘終長①加⒈丟倘⓶增⓶가采⓶擘❷小終⓷丟❶長貶❷가掊貶插①增復合감不가終終

Esto espera la entrada como una lista separada por espacios. Esto genera la respuesta correcta para 1 1y 2, pero para 2 1o 3tarda demasiado, así que dejé de esperar a que termine.

Con comentario:

글坼 | split at spaces
가⑴ | iteration count = 0

감套 | while:
  擘終長①加⒈丟 | remove zeros from end and add to iteration count
  倘 | if the list is not empty:
    ⓶增⓶ | increment iteration count
    가采⓶擘❷小終⓷丟 | separate out active segment
    ❶長貶❷가掊貶插 | compute reduced active segment
    ①增復合 | repeat reduced active segment and concat
    감 | continue while loop
  不 | else
    가 | stop while loop
  終 | end if
終 | end while
Timwi
fuente
2
Un enlace a un intérprete sería útil ... ¿También, 86 bytes, usando UTF-16?
Peter Taylor
@PeterTaylor: Gracias, agregó el enlace al intérprete al artículo. Y sí, 43 caracteres BMP se traducen a 86 bytes en UTF-16.
Timwi
5

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:

  worm 1 1 0
51
  worm 2
51
  worm 1 1
19

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 1y worm 3simplemente abandonar (y probablemente tiraría 'wsfull(sin memoria) si dejo que sigan).

Aaron Davies
fuente
Intenté ejecutar su programa con este intérprete en línea , pero no muestra ningún resultado. (Se supone que enviar un archivo de texto con la extensión .k invoca al intérprete K). ¿Sabe qué se puede hacer para enviar la salida a stdout?
Res
Parece que está ejecutando kona, un clon de código abierto de k3. Mi código está escrito en k4 y es poco probable que sea compatible con k3. Puede obtener una copia gratuita de q / k4 por tiempo limitado en kx.com/software-download.php ; una vez que tenga eso, inicie REPL, escriba ` to switch from q` ky pegue mi código. Alternativamente, puede guardar mi código en un archivo con una .kextensión y cargarlo en el intérprete.
Aaron Davies
2

APL (Dyalog Unicode) , 52 bytes SBCS

Guardado 7 bytes gracias a @ngn y @ Adám.

0{⍬≡⍵:⍺⋄n←⍺+10=⊃⍵:n1↓⍵⋄n∇∊(⊂1n/-∘1@1¨)@1⊆∘⍵⍳⍨⌊\⍵}⌽

Pruébalo en línea!

Explicación:

0{...}⌽     A monadic function train. We define a recursive function with two
            arguments: zero (our counter), and the reverse of our input
⍬≡⍵:⍺       Our base case - if our input is an empty list, return our counter
n←⍺+1       Define 'n' as our counter plus 1
0=⊃⍵:n1↓⍵  If the first element of the input is zero, recurse with the tail
            of our input and n
\⍵         Minimum-expand: creates a new list from our input where each element
            is the incremental minimum     
⍳⍨          Applies above to both sides of the index-of function. Index-of returns
            the index of the first occurence of each element in the left-side list.
            At this point, a (reversed) input list of [3 4 5 2 3 4] would result
            in [1 1 1 4 4 4]
⊆∘⍵         Partition, composed with our input. Partition creates sublists of the
            right input whenever the integer list in the left input increases.
            This means we now have a list of sub-lists, with the first element
            being the worm's active segment.
(...)@1    ⍝ Take the active segment and apply the following function train...
-∘1@1¨     ⍝ Subtract 1 from the first element of the active segment
1n/        ⍝ Replicate the resultant list above n+1 times
⊂          ⍝ Enclose the above, so as to keep the original shape of our sub-array
∊          ⍝ Enlist everything above together - this recursively concatenates our
           ⍝ new active segment with the remainder of the list
n∇         ⍝ Recurse with the above and n
halcón vacío
fuente
Pensé que APL tendría una solución realmente limpia para esto, ¿no es un lenguaje basado en matrices?
ThePlasmaRailgun
1

Scala, 198

type A=List[Int]
def T(w:A)={def s(i:Int,l:A):Stream[A]=l match{case f::r=>l#::s(i+1,if(f<1)r
else{val(h,t)=l.span(_>=l(0));List.fill(i)(h(0)-1::h.tail).flatten++t})
case _=>Stream()};s(2,w).length}

Uso:

scala> T(List(2))
res0: Int = 51
ValarDohaeris
fuente
1

K, 95

{i::0;#{~x~,0}{((x@!b),,[;r]/[i+:1;r:{@[x;-1+#x;-1+]}@_(b:0^1+*|&h>x)_x];-1_x)@0=h:*|x:(),x}\x}

.

k)worm:{i::0;#{~x~,0}{((x@!b),,[;r]/[i+:1;r:{@[x;-1+#x;-1+]}@_(b:0^1+*|&h>x)_x];-1_x)@0=h:*|x:(),x}\x}
k)worm 2
51
k)worm 1 1
19
q)worm 1 1 0 0 0 0
635
tmartin
fuente
1

C (gcc) , 396 bytes

#define K malloc(8)
typedef*n;E(n e,n o){n s=K,t=s;for(*s=*o;o=o[1];*t=*o)t=t[1]=K;t[1]=e;e=s;}main(c,f,l,j,a)n*f;{n w=K,x=w;for(;l=--c;x=x[1]=K)*x=atoi(f[c]);for(;w&&++l;)if(*w){n v=K,z=v,u=w,t=K;for(a=*v=*w;(u=u[1])&&*u>=*w;*z=*u)z=z[1]=K;for(x=v[1],v=K,*v=a-1,1[u=v]=x;u;u=u[1])w=w[1];for(j=~l;j++;)u=t=E(t,v);for(;(u=u[1])&&(x=u[1])&&x[1];);u[1]=0;w=w?E(w,t):t;}else w=w[1];printf("%d",--l);}

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.

ThePlasmaRailgun
fuente
¿Realmente necesitas una lista vinculada? ¿Por qué no solo asignar matrices? Como se trata de un código de golf, ni siquiera necesita molestarse en liberarlos cuando haya terminado. Usted puede incluso ser capaz de encontrar una manera de almacenarlos en la pila de llamadas (no estoy seguro).
dfeuer
Además, no necesita una función principal. Simplemente escriba una función que tome el gusano como argumento y devuelva su vida útil. El gusano puede ser una matriz y su longitud, o quizás una matriz que termina en un número negativo.
dfeuer
1

Haskell , 84 bytes

(0!).reverse
n!(x:y)|x<1=(n+1)!y|(a,b)<-span(>=x)y=(n+1)!(([-1..n]*>x-1:a)++b)
n!_=n

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.

dfeuer
fuente
1
Dos pequeños campos de golf : revise el caso de la lista vacía en segundo lugar y nbaje por 1.
xnor
También creo que debería haber una manera de no escribir (n+1)!dos veces, pero mi intento solo empató.
xnor