# Lifetime of a Worm

## Terms

A worm is any list of nonnegative integers, and its rightmost (i.e., last) element is called the head. If the head is not 0, the worm has an active segment consisting of the longest contiguous block of elements that includes the head and has all of its elements at least as large as the head. The reduced active segment is the active segment with the head decremented by 1. For example, the worm 3 1 2 3 2 has active segment 2 3 2, and the reduced active segment is 2 3 1.

## Rules of evolution

A worm evolves step-by-step as follows:

In step t (= 1, 2, 3, ...),
if the head is 0: delete the head
else: replace the active segment by t+1 concatenated copies of the reduced active segment.

Fact: Any worm eventually evolves into the empty list, and the number of steps to do so is the worm's lifetime.

(Details can be found in The Worm Principle, a paper by L. D. Beklemishev. The usage of "list" to mean a finite sequence, and "head" to mean its last element, is taken from this paper -- it should not be confused with the common usage for lists as an abstract data type, where head usually means the first element.)

## Examples (active segment in parentheses)

Worm: 0,1

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


Worm: 1,0

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


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


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


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


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


## Aside

Worm lifetimes are typically enormous, as shown by the following lower bounds in terms of the standard fast-growing hierarchy of functions 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)


Remarkably, worm  already has a lifetime that far surpasses Graham's number, G:

fωω(2) = fω2(2) = fω2(2) = fω+2(2) = fω+1(fω+1(2)) >> fω+1(64) > G.

## Code Golf Challenge

Write the shortest possible function subprogram with the following behavior:

Input: Any worm.
Output: The lifetime of the worm.

Code size is measured in bytes.

Here's an example (Python, golfs to about 167 bytes):

from itertools import *
def T(w):
w=w[::-1]
t=0
while w:
t+=1
if w:a=list(takewhile(lambda e:e>=w,w));a-=1;w=a*(t+1)+w[len(a):]
else:w=w[1:]
return t


NB: If t(n) is the lifetime of the worm [n], then the rate of growth of t(n) is roughly that of the Goodstein function. So if this can be golfed to below 100 bytes, it could well give a winning answer to the Largest Number Printable question. (For that answer, the growth-rate could be vastly accelerated by always starting the step-counter at n -- the same value as the worm [n] -- instead of starting it at 0.)

• I am confused by your code. You said the head is the rightmost element, but in your Python example, you treat the head as a w which is the *leftmost element of that list? – user8777 Jan 20 '14 at 0:22
• @LegoStormtroopr If you can consider a list as having a left and right. If you just consider a first and last, you could map the rightmost to first or last when reading the initial string - which isn't part of the question. But the function inputs weren't strictly defined either. – Bob Jan 20 '14 at 3:26
• @LegoStormtroopr - Good catch; I corrected the code by adding a line to reverse the input worm, whose head is indeed supposed to be on the right (i.e. the last element in the list w). It's for efficiency that the program operates on the reversed worm. – r.e.s. Jan 20 '14 at 4:55
• Getting the correct answer for 2 1 might be too much to ask in a reasonable time, but a useful test is that the sequence should start (2 1), 2 0 2 0, 2 0 (2), 2 0 (1 1 1 1), ... – Peter Taylor Jan 20 '14 at 12:03
• @ThePlasmaRailgun - To paraphrase Harvey Friedman, numbers derived from functions at level ε_0 in the fast-growing hierarchy (such as worm-lifetimes) are completely UNNOTICEABLE in comparison to TREE(3). – r.e.s. Mar 13 '19 at 18:17

## GolfScript (56 54 chars)

{-1%0\{\)\.0={.0+.({<}+??$$(\+.@<2*\+}{(;}if.}do;}:L;  Online demo I think that the key trick here is probably keeping the worm in reverse order. That means that it's pretty compact to find the length of the active segment: .0+.({<}+?? (where the 0 is added as a guard to ensure that we find an element smaller than the head). As an aside, some analysis of the worm lifespan. I'll denote the worm as age, head tail (i.e. in reverse order from the question's notation) using exponents to indicate repetition in the head and tail: e.g. 2^3 is 2 2 2. Lemma: for any active segment xs, there is a function f_xs such that age, xs 0 tail transforms into f_xs(age), tail. Proof: no active segment can ever contain a 0, so the age by the time we delete everything before the tail is independent of the tail and is hence a function only of xs. Lemma: for any active segment xs, the worm age, xs dies at age f_xs(age) - 1. Proof: by the previous lemma, age, xs 0 transforms into f_xs(age), []. The final step is deletion of that 0, which is not touched previously because it can never form part of an active segment. With those two lemmata, we can study some simple active segments. For 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  so f_{1^n} = x -> f_{1^{n-1}}^{x+1}(x+2) (with base case f_{[]} = x -> x+1, or if you prefer f_{1} = x -> 2x+3). We see that f_{1^n}(x) ~ A(n+1, x) where A is the Ackermann–Péter function. age, 2 0 xs -> age+1, 1^{age+1} 0 xs -> f_{1^{age+1}}(age+1)  That's enough to get a handle on 1 2 (2 1 in the notation of the 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, []  So given input 2 1 we expect output ~ 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  and I can really start to comprehend why this function grows so insanely. • Very cool. I think this program will also give a winning answer to the Shortest terminating program whose output size exceeds Graham's number. (The current winner there is 63 bytes of Haskell code.) E.g., at 55 bytes, something like (since I'm prone to syntax errors) 9{-1%0\{$$\.0={.0+.({<}+??\((\+.@<2$*\+}{(;}if.}do;}:L~ computes the lifetime of worm , which far exceeds Graham's number -- and can be golfed further. – r.e.s. Jan 23 '14 at 12:42 ### GolfScript, 69 62 characters {0:?~%{(.{[(]{:^0=2$0+0=<}{\(@\+}/}{,:^}if;^?):?)*\+.}do;?}:C;


The function C expects the worm on the stack and replaces it by the result.

Examples:

> [1 1]
19

> 
51

> [1 1 0]
51

• Fantastic! Surely you can modify this a bit to also give a definite winner for the "Largest Number Printable" question. – r.e.s. Jan 19 '14 at 19:25
• I didn't see you post anything over there, so I went ahead and posted a modification of this code as what I believe to be the winning answer there so far -- assuming that the * and ^ are not being used as the arithmetic operators of multiply and exponentiate. Certainly, if you want to submit your own (doubtlessly superior) answer there, I will happily remove mine. – r.e.s. Jan 19 '14 at 21:21

### Ruby — 131 characters

I know this can't compete with the GolfScript solutions above and I'm fairly sure that this can be reduced a score or more characters, but honestly I'm happy to have been able to solve the problem ungolfed. Great puzzle!

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


My pre-golfed solution from which the above is derived:

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 -= 1
worm.shift(head.size)
worm = head * (step + 1) + worm
end
end
step
end

• Generic tip: many golf problems work on non-negative integers, in which case if foo==0 can be trimmed to if foo<1. That can save you one char here. – Peter Taylor Jan 20 '14 at 8:40
• Incidentally, I find it fascinating that this works without a second reverse. – Peter Taylor Jan 20 '14 at 8:41
• Ah, it doesn't. It just works on the test cases because they only have palindromic active segments. – Peter Taylor Jan 20 '14 at 11:54
• Thanks for the golf tip, @PeterTaylor. Also, good catch on the missing second reverse. I've added it in. I'll try to rewrite this another way without using reverse later. I'm pretty sure I can get the else clause down to one line and then swap the if..else..end for a ternary statement. I could also use a lambda to save a few characters, I think. – O-I Jan 20 '14 at 16:54

# Sclipting (43 characters)

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


This expects the input as a space-separated list. This outputs the correct answer for 1 1 and 2, but for 2 1 or 3 it takes too long so I gave up waiting for it to finish.

With commentary:

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


• A link to an interpreter would be handy... Also, 86 bytes, using UTF-16? – Peter Taylor Jan 20 '14 at 18:48
• @PeterTaylor: Thanks, added the link to the interpreter to the article. And yes, 43 BMP characters do translate to 86 bytes in UTF-16. – Timwi Jan 23 '14 at 11:59

# k (83)

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

this can probably be golfed further, as it just implements the recurrence fairly straightforwardly.

the basic evolution function, {x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}, is 65 chars, and uses some tricks to stop incrementing the age when the worm dies. the wrapper coerces an input of a single integer to a list, reverses the input (it's shorter to write the recurrence in terms of a worm reversed from your notation), asks for the fixpoint, selects the age as the output, and adjusts the result to account for the overshoot in the last generation.

if i do the coercion and reversal manually, it drops to 80 ({-1+*({x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}.)/(1;x)}).

some examples:

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


unfortunately, it's probably not much use for Largest Number Printable, except in a very theoretical sense, as it's quite slow, limited to 64-bit integers, and probably not particularly memory-efficient.

in particular, worm 2 1 and worm 3 just churn (and would probably throw 'wsfull (out of memory) if i let them keep going).

• I've tried to run your program with this online interpreter, but it doesn't show any output. (Submitting a text file with extension .k is supposed to invoke the K interpreter.) Do you know what might be done to send the output to stdout? – r.e.s. Jan 27 '14 at 17:27
• It looks like that's running kona, an open-source clone of k3. My code is written in k4, and is unlikely to be compatible with k3. You can get a time-limited free copy of q/k4 at kx.com/software-download.php; once you have that, start the REPL, type  to switch from q to k, and paste my code in. Alternatively, you can save my code in a file with a .k extension and load it into the interpreter. – Aaron Davies Jan 27 '14 at 21:51

# APL (Dyalog Unicode), 52 bytesSBCS

Saved 7 bytes thanks to @ngn and @Adám.

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


Try it online!

Explanation:

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

• I figured APL would have a really clean solution for this, isn't it an array-based language? – ThePlasmaRailgun Mar 13 '19 at 6:16

# 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 bytes

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


Try it online!

I know I'm EXTREMELY late to the party, but I thought I'd try my hand at this in C, which required a linked-list implementation. It's not really golfed at all besides changing all the identifiers to single characters, but it functions!

All in all, I'm pretty happy considering this is the 3rd C/C++ program I've ever wrote.

• Do you really need a linked list? Why not just allocate arrays? Since this is code golf, you don't even need to bother freeing them when you're done. You might even be able to find a way to store them on the call stack (not sure). – dfeuer Mar 16 '19 at 3:38
• Also, you don't need a main function. Just write a function that takes the worm as an argument and returns its lifespan. The worm can be an array and its length, or maybe an array ending in a negative number. – dfeuer Mar 16 '19 at 3:43

# 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


Try it online!

Thanks to @xnor for two bytes.

I feel like there should be a good way to factor out the common increment, but I haven't found a short one yet.

• Two small golfs: check the empty list case second, and shift n down by 1. – xnor Mar 16 '19 at 16:47
• I also think there should be a way to not write (n+1)! twice, but my attempt only tied. – xnor Mar 16 '19 at 16:52

# Perl 5-pa, 92 bytes

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


Try it online!

# Stax, 31 bytes

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

Run and debug it