## 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, ...),
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: 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
``````

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
``````

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

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

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

-
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[0]` which is the *leftmost element of that list? – Lego Stormtroopr 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
@PeterTaylor - Yes, worm [2,1] (like [3]) is a good example to illustrate some "nontrivial" active segments in the first few steps. I'll add it to the question. – r.e.s. Jan 20 '14 at 12:58

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

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

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