Lifetime of a Worm

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.

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

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