Lifetime of a Worm

Question

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 [3] already has a lifetime that far surpasses Graham's number, G:

f_ω^ω(2) = f_ω²(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[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: 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.)

Answer 1

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.

Answer 2

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

> [2]
51

> [1 1 0]
51

Answer 3

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[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}

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

Answer 4

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
終 | end while

Answer 5

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

Answer 6

APL (Dyalog Unicode), 52 bytes^SBCS

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

Answer 7

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

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.

Answer 8

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.

Answer 9

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

Answer 10

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

Answer 11

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!

Answer 12

Stax, 31 bytes

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

Run and debug it