termes

Un ver est une liste d'entiers non négatifs, et son élément le plus à droite (c'est-à-dire le dernier ) est appelé la tête . Si la tête n'est pas égale à 0, le ver a un segment actif constitué du bloc d'éléments contigu le plus long qui comprend la tête et a tous ses éléments au moins aussi grands que la tête . Le segment actif réduit est le segment actif avec la tête décrémentée de 1. Par exemple, le ver 3 1 2 3 2a un segment actif 2 3 2et le segment actif réduit l'est 2 3 1.

Règles d'évolution

Un ver évolue pas à pas comme suit:

A l'étape t (= 1, 2, 3, ...),
    si la tête est 0: supprimez la tête
    sinon: remplacez le segment actif par t + 1 copies concaténées du segment actif réduit.

Réalité : tout ver finit par évoluer vers la liste vide , et le nombre d'étapes pour le faire est la durée de vie du ver .

(Voir les détails se trouvent dans le ver Principe ., Un papier par LD Beklemishev L'utilisation de « liste » pour signifier une séquence finie, et « tête » pour signifier son dernier élément, est tiré de ce papier - il ne faut pas confondre avec l'utilisation courante des listes comme type de données abstrait , où head signifie généralement le premier élément.)

Exemples (segment actif entre parenthèses)

Ver: 0,1

step    worm
         0(1)
1        0 0 0
2        0 0 
3        0
4           <- lifetime = 4

Ver: 1,0

step    worm
         1 0
1       (1)
2        0 0 0
3        0 0 
4        0
5           <- lifetime = 5

Ver: 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

Ver: 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

Ver: 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 = ??      

Ver: 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 = ??

De côté

Les durées de vie des vers sont généralement énormes, comme le montrent les limites inférieures suivantes en termes de hiérarchie standard à croissance rapide des fonctions 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)

Remarquablement, le ver [3] a déjà une durée de vie qui dépasse de loin le nombre de Graham , G:

f _{ω ^ω} (2) = f _{ω ²} (2) = f _ω2 (2) = f _{ω + 2} (2) = f _{ω + 1} (f _{ω + 1} (2)) >> f _{ω + 1} (64) > G.

Code Golf Challenge

Écrivez le sous-programme de fonction le plus court possible avec le comportement suivant:

Entrée : tout ver.
Sortie : la durée de vie du ver.

La taille du code est mesurée en octets.

Voici un exemple (Python, golfs à environ 167 octets):

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) est la durée de vie du ver [n], alors le taux de croissance de t (n) est à peu près celui de la fonction de Goodstein . Donc, si cela peut être joué à moins de 100 octets, cela pourrait bien donner une réponse gagnante à la question imprimable du plus grand nombre . (Pour cette réponse, le taux de croissance pourrait être considérablement accéléré en démarrant toujours le compteur de pas à n - la même valeur que le ver [n] - au lieu de le démarrer à 0.)

GolfScript ( 56 54 caractères)

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

Démo en ligne

Je pense que l'astuce clé ici est probablement de maintenir le ver dans l'ordre inverse. Cela signifie qu'il est assez compact de trouver la longueur du segment actif: .0+.({<}+??(où le 0est ajouté comme garde pour s'assurer que nous trouvons un élément plus petit que la tête).

En passant, une analyse de la durée de vie du ver. Je vais désigner le ver comme age, head tail(c'est-à-dire dans l'ordre inverse de la notation de la question) en utilisant des exposants pour indiquer la répétition dans la tête et la queue: par exemple 2^3est 2 2 2.

Lemme : pour tout segment actif xs, il existe une fonction f_xsqui se age, xs 0 tailtransforme en f_xs(age), tail.

Preuve: aucun segment actif ne peut jamais contenir un 0, donc l'âge au moment où nous supprimons tout avant que la queue ne soit indépendante de la queue et ne soit donc qu'une fonction de xs.

Lemme : pour tout segment actif xs, le ver age, xsmeurt à l'âge f_xs(age) - 1.

Preuve: par le lemme précédent, se age, xs 0transforme en f_xs(age), []. La dernière étape est la suppression de ce 0qui n'a pas été touché précédemment car il ne peut jamais faire partie d'un segment actif.

Avec ces deux lemmes, nous pouvons étudier quelques segments actifs simples.

Pour 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

donc f_{1^n} = x -> f_{1^{n-1}}^{x+1}(x+2)(avec le cas de base f_{[]} = x -> x+1, ou si vous préférez f_{1} = x -> 2x+3). On voit que f_{1^n}(x) ~ A(n+1, x)là où Aest la fonction Ackermann-Péter.

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

Cela suffit pour comprendre 1 2( 2 1dans la notation de la question):

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, []

Donc, étant donné l'entrée, 2 1nous attendons la sortie ~ 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

et je peux vraiment commencer à comprendre pourquoi cette fonction se développe si follement.

GolfScript, 69 62 caractères

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

La fonction Cattend le ver sur la pile et le remplace par le résultat.

Exemples:

> [1 1]
19

> [2]
51

> [1 1 0]
51

Ruby - 131 caractères

Je sais que cela ne peut pas rivaliser avec les solutions GolfScript ci-dessus et je suis assez sûr que cela peut être réduit d'un score ou de plusieurs caractères, mais honnêtement, je suis heureux d'avoir pu résoudre le problème sans golf. Grand puzzle!

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}

Ma solution pré-golfée à partir de laquelle ce qui précède est dérivé:

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

Sclipting (43 caractères)

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

Cela attend l'entrée en tant que liste séparée par des espaces. Cela génère la bonne réponse pour 1 1et 2, mais pour 2 1ou 3cela prend trop de temps, j'ai donc abandonné l'attente de la fin.

Avec commentaire:

글坼 | 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

k (83)

worm:{-1+*({x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}.)/(1;|,/x)}

cela peut probablement être approfondi, car il implémente simplement la récurrence assez simplement.

la fonction d'évolution de base {x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}, est de 65 caractères, et utilise quelques astuces pour arrêter l'augmentation de l'âge à la mort du ver. l'encapsuleur contraint une entrée d'un seul entier à une liste, inverse l'entrée (il est plus court d'écrire la récurrence en termes de ver inversé de votre notation), demande le point fixe, sélectionne l'âge comme sortie et ajuste le résultat pour tenir compte du dépassement de la dernière génération.

si je fais la coercition et l'inversion manuellement, cela tombe à 80 ( {-1+*({x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}.)/(1;x)}).

quelques exemples:

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

malheureusement, il n'est probablement pas très utile pour le plus grand nombre imprimable , sauf dans un sens très théorique, car il est assez lent, limité à des entiers 64 bits, et probablement pas particulièrement efficace en mémoire.

en particulier, worm 2 1et worm 3juste baratiner (et jetterait probablement 'wsfull(de mémoire) si je les laissais continuer).

APL (Dyalog Unicode) , 52 octets ^SBCS

7 octets enregistrés grâce à @ngn et @ Adám.

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

Essayez-le en ligne!

Explication:

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=⊃⍵:n∇1↓⍵ ⍝ 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

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}

Usage:

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

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

C (gcc) , 396 octets

#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);}

Essayez-le en ligne!

Je sais que je suis EXTRÊMEMENT en retard à la fête, mais j'ai pensé que je tenterais ma chance en C, ce qui nécessitait une implémentation de liste chaînée. Ce n'est pas vraiment du golf en plus de changer tous les identifiants en caractères uniques, mais ça fonctionne!

Dans l'ensemble, je suis assez content étant donné qu'il s'agit du 3e programme C / C ++ que j'ai jamais écrit.

Haskell , 84 octets

(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

Essayez-le en ligne!

Merci à @xnor pour deux octets.

Je pense qu'il devrait y avoir un bon moyen de prendre en compte l'incrément commun, mais je n'en ai pas encore trouvé un court.

Perl 5 -pa , 92 octets

while(@F){++$\;my@a;if($b=pop@F){unshift@a,pop@F while$F[-1]>=$b;push@F,(@a,--$b)x($\+1)}}}{

Essayez-le en ligne!

Stax , 31 octets

àîz7αan♣óàNµK2☻₧⌡▐`Γl½f{♂♂_KZÖÄ

Exécuter et déboguer