3 added 2160 characters in body
source | link

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.


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.

2 deleted 4 characters in body
source | link

GolfScript (5656 54 chars)

{-1%1\1%0\{\)\.0={0+.0+.({<}+??\((\+.@<2$*\+)}{(;}if;\)\if.}do;(}:L;

Online demoOnline 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+.0+.({<}+?? plus a later ) to remove(where the 0 is added as a guard to ensure that we find an element smaller than the head).

GolfScript (56 chars)

{-1%1\{.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+..({<}+?? plus a later ) to remove the 0 added as a guard to ensure that we find an element smaller than the head.

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

1
source | link

GolfScript (56 chars)

{-1%1\{.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+..({<}+?? plus a later ) to remove the 0 added as a guard to ensure that we find an element smaller than the head.