Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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

share|improve this question
    
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 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 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 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 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 at 12:58
show 5 more comments

7 Answers

up vote 7 down vote accepted

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.

share|improve this answer
    
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 at 12:42
add comment

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
share|improve this answer
    
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 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 at 21:21
add comment

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
share|improve this answer
    
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 at 8:40
    
Incidentally, I find it fascinating that this works without a second reverse. –  Peter Taylor Jan 20 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 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 at 16:54
add comment

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

share|improve this answer
    
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 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 at 21:51
add comment

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
share|improve this answer
    
A link to an interpreter would be handy... Also, 86 bytes, using UTF-16? –  Peter Taylor Jan 20 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 at 11:59
add comment

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
share|improve this answer
add comment

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
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.