Durée de vie d'un ver

28

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 (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.)

res
la source
Je suis confus par votre code. Vous avez dit que la tête est l' élément le plus à droite , mais dans votre exemple Python, vous traitez la tête comme un w[0]élément qui est * le plus à gauche de cette liste?
@LegoStormtroopr Si vous pouvez considérer une liste comme ayant une gauche et une droite. Si vous considérez simplement un premier et un dernier, vous pouvez mapper le plus à droite au premier ou au dernier lors de la lecture de la chaîne initiale - ce qui ne fait pas partie de la question. Mais les entrées de fonction n'étaient pas non plus strictement définies.
Bob
@LegoStormtroopr - Bonne prise; J'ai corrigé le code en ajoutant une ligne pour inverser le ver d'entrée, dont la tête est en effet supposée être à droite (ie le dernier élément de la liste w). C'est pour l'efficacité que le programme fonctionne sur le ver inversé.
res
Obtenir la bonne réponse pour 2 1peut - être trop demander dans un délai raisonnable, mais un test utile est que la séquence doit commencer (2 1), 2 0 2 0, 2 0 (2), 2 0 (1 1 1 1), ...
Peter Taylor
1
@ThePlasmaRailgun - Pour paraphraser Harvey Friedman, les nombres dérivés des fonctions au niveau ε_0 dans la hiérarchie à croissance rapide (comme les durées de vie des vers) sont totalement INNOTICEABLES par rapport à TREE (3) .
res

Réponses:

15

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.

Peter Taylor
la source
Très sympa. Je pense que ce programme donnera également une réponse gagnante au programme de terminaison le plus court dont la taille de sortie dépasse le nombre de Graham . (Le gagnant actuel contient 63 octets de code Haskell.) Par exemple, à 55 octets, quelque chose comme (puisque je suis sujet aux erreurs de syntaxe) 9{-1%0\{\)\.0={.0+.({<}+??\((\+.@<2$*\+}{(;}if.}do;}:L~calcule la durée de vie du ver [9], qui dépasse de loin le nombre de Graham - et peut être golfé plus loin.
res
9

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
Howard
la source
Fantastique! Vous pouvez sûrement modifier cela un peu pour donner également un gagnant définitif pour la question "Le plus grand nombre imprimable" .
res
Je ne vous ai pas vu publier quoi que ce soit là-bas, alors j'ai continué et j'ai posté une modification de ce code comme ce que je crois être la réponse gagnante jusqu'à présent - en supposant que le *et ^ne sont pas utilisés comme opérateurs arithmétiques de multiplier et exponentiate. Certainement, si vous voulez y soumettre votre propre réponse (sans doute supérieure), je me ferai un plaisir de supprimer la mienne.
res
7

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
OI
la source
Astuce générique: de nombreux problèmes de golf fonctionnent sur des entiers non négatifs, auquel cas ils if foo==0peuvent être ajustés if foo<1. Cela peut vous faire économiser un caractère ici.
Peter Taylor
Soit dit en passant, je trouve fascinant que cela fonctionne sans une seconde reverse.
Peter Taylor
Ah non. Cela ne fonctionne que sur les cas de test car ils n'ont que des segments actifs palindromiques.
Peter Taylor
Merci pour le conseil de golf, @PeterTaylor. Aussi, bonne prise sur le deuxième revers manquant. Je l'ai ajouté. J'essaierai de réécrire cette autre façon sans utiliser inverser plus tard. Je suis sûr que je peux ramener la elseclause à une seule ligne, puis échanger le if..else..endpour une déclaration ternaire. Je pourrais aussi utiliser un lambda pour enregistrer quelques caractères, je pense.
OI
6

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
Timwi
la source
2
Un lien vers un interprète serait pratique ... Aussi, 86 octets, en utilisant UTF-16?
Peter Taylor
@PeterTaylor: Merci, a ajouté le lien vers l'interprète à l'article. Et oui, 43 caractères BMP se traduisent en 86 octets 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)}

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

Aaron Davies
la source
J'ai essayé d'exécuter votre programme avec cet interprète en ligne , mais il n'affiche aucune sortie. (La soumission d'un fichier texte avec l'extension .k est censée invoquer l'interpréteur K.) Savez-vous ce qui pourrait être fait pour envoyer la sortie à stdout?
res
Il semble que cela exécute kona, un clone open-source de k3. Mon code est écrit en k4 et il est peu probable qu'il soit compatible avec k3. Vous pouvez obtenir une copie gratuite limitée dans le temps de q / k4 sur kx.com/software-download.php ; une fois que vous avez cela, démarrez le REPL, tapez ` to switch from q` to ket collez mon code dedans . Alternativement, vous pouvez enregistrer mon code dans un fichier avec une .kextension et le charger dans l'interpréteur.
Aaron Davies
2

APL (Dyalog Unicode) , 52 octets SBCS

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

0{⍬≡⍵:⍺⋄n←⍺+10=⊃⍵:n1↓⍵⋄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=⊃⍵: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
voidhawk
la source
J'ai pensé qu'APL aurait une solution vraiment propre pour cela, n'est-ce pas un langage basé sur un tableau?
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}

Usage:

scala> T(List(2))
res0: Int = 51
Valar Dohaeris
la source
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
la source
1

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.

ThePlasmaRailgun
la source
Avez-vous vraiment besoin d'une liste chaînée? Pourquoi ne pas simplement allouer des tableaux? Puisque c'est du golf de code, vous n'avez même pas besoin de vous soucier de les libérer lorsque vous avez terminé. Vous pourriez même être en mesure de trouver un moyen de les stocker sur la pile des appels (pas sûr).
dfeuer
De plus, vous n'avez pas besoin d'une fonction principale. Il suffit d'écrire une fonction qui prend le ver comme argument et renvoie sa durée de vie. Le ver peut être un tableau et sa longueur, ou peut-être un tableau se terminant par un nombre négatif.
dfeuer
1

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.

dfeuer
la source
1
Deux petits golfs : vérifiez le cas de la liste vide en second, et nrétrogradez de 1.
xnor
Je pense aussi qu'il devrait y avoir un moyen de ne pas écrire (n+1)!deux fois, mais ma tentative n'a fait que des égales.
xnor