Nutzungsbedingungen

Ein Wurm ist eine Liste von nichtnegativen ganzen Zahlen und sein rechtes (dh letztes ) Element heißt head . Wenn der Kopf nicht 0 ist, hat der Wurm ein aktives Segment, das aus dem längsten zusammenhängenden Elementblock besteht, der den Kopf enthält, und dessen Elemente mindestens so groß sind wie der Kopf . Das reduzierte aktive Segment ist das aktive Segment, dessen Kopf um 1 dekrementiert wurde. Beispielsweise hat der Wurm 3 1 2 3 2ein aktives Segment 2 3 2und das reduzierte aktive Segment ist 2 3 1.

Regeln der Evolution

Ein Wurm entwickelt sich Schritt für Schritt wie folgt:

In Schritt t (= 1, 2, 3, ...),
    wenn der Kopf 0 ist: lösche den Kopf
    sonst: ersetze das aktive Segment durch t + 1 verkettete Kopien des reduzierten aktiven Segments.

Fakt : Jeder Wurm entwickelt sich irgendwann zu einer leeren Liste , und die Anzahl der dazu erforderlichen Schritte ist die Lebensdauer des Wurms .

(Details finden Sie in The Worm Principle , einem Artikel von LD Beklemishev. Die Verwendung von "list" als endliche Sequenz und "head" als letztes Element ist diesem Artikel entnommen - nicht zu verwechseln mit der gebräuchlichen Verwendung für Listen als abstrakten Datentyp , wobei head normalerweise das erste Element bedeutet.)

Beispiele (aktives Segment in Klammern)

Wurm: 0,1

step    worm
         0(1)
1        0 0 0
2        0 0 
3        0
4           <- lifetime = 4

Wurm: 1,0

step    worm
         1 0
1       (1)
2        0 0 0
3        0 0 
4        0
5           <- lifetime = 5

Wurm: 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

Wurm: 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

Wurm: 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 = ??      

Wurm: 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 = ??

Beiseite

Worm Lebensdauern liegen typischerweise enorm, wie durch die folgenden unteren Grenzen in Bezug auf die Standard gezeigt schnell wachsenden Hierarchie von Funktionen 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)

Bemerkenswerterweise hat Wurm [3] bereits eine Lebenszeit, die Grahams Zahl bei weitem übertrifft :

f _{ω ^ω} (2) = f _{ω ²} (2) = f _ω2 (2) = f _{ω + 2} (2) = f _{ω + 1} (f _{ω + 1} (2)) >> f _{ω + 1} (64) > G.

Code Golf Challenge

Schreiben Sie das kürzestmögliche Funktionsunterprogramm mit folgendem Verhalten:

Eingabe : Beliebiger Wurm.
Ausgabe : Die Lebensdauer des Wurms.

Die Codegröße wird in Bytes gemessen.

Hier ist ein Beispiel (Python, Golf auf ca. 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

Anmerkung : Wenn t (n) die Lebensdauer des Wurms [n] ist, entspricht die Wachstumsrate von t (n) in etwa der der Goodstein-Funktion . Also , wenn diese auf unter 100 Bytes golfed werden, könnte es auch eine Gewinn Antwort auf die gibt größte Zahl Druck Frage . (Für diese Antwort könnte die Wachstumsrate erheblich beschleunigt werden, indem der Schrittzähler immer bei n gestartet wird - dem gleichen Wert wie der Wurm [n] - anstatt bei 0.)

GolfScript ( 56 54 Zeichen)

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

Online-Demo

Ich denke, dass der Schlüsseltrick hier wahrscheinlich darin besteht, den Wurm in umgekehrter Reihenfolge zu halten. Das bedeutet, dass es ziemlich kompakt ist, die Länge des aktiven Segments zu finden: .0+.({<}+??(wobei das 0als Schutz hinzugefügt wird, um sicherzustellen, dass wir ein Element finden, das kleiner als der Kopf ist).

Nebenbei eine Analyse der Wurmlebensdauer. Ich bezeichne den Wurm als age, head tail(dh in umgekehrter Reihenfolge von der Notation der Frage) mit Exponenten, um Wiederholungen in Kopf und Schwanz anzuzeigen: zB 2^3ist 2 2 2.

Lemma : Für jedes aktive Segment xsgibt es eine f_xssolche Funktion , age, xs 0 taildie sich in verwandelt f_xs(age), tail.

Beweis: Kein aktives Segment kann jemals ein enthalten 0, so dass das Alter bis zu dem Zeitpunkt, an dem wir alles löschen, bevor der Schwanz unabhängig vom Schwanz ist und daher nur eine Funktion von istxs .

Lemma : Für jedes aktive Segment stirbt xsder Wurm age, xsim Alter f_xs(age) - 1.

Beweis: age, xs 0verwandelt sich nach dem vorhergehenden Lemma in f_xs(age), []. Der letzte Schritt ist das Löschen davon0 , das vorher nicht berührt wurde, weil es niemals Teil eines aktiven Segments sein kann.

Mit diesen beiden Lemmata können wir einige einfache aktive Segmente untersuchen.

Für 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

also f_{1^n} = x -> f_{1^{n-1}}^{x+1}(x+2)(mit basis fall f_{[]} = x -> x+1, oder wenn sie es vorziehen f_{1} = x -> 2x+3). Wir sehen, f_{1^n}(x) ~ A(n+1, x)wo Aist die Ackermann-Péter-Funktion.

age, 2 0 xs -> age+1, 1^{age+1} 0 xs
            -> f_{1^{age+1}}(age+1)

Das ist genug, um einen Überblick zu bekommen 1 2( 2 1in der Notation der Frage):

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

Wenn 2 1wir also Input haben, erwarten wir 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

und ich kann wirklich verstehen, warum diese Funktion so wahnsinnig wächst.

GolfScript, 69 62 Zeichen

{0:?~%{(.{[(]{:^0=2$0+0=<}{\(@\+}/}{,:^}if;^?):?)*\+.}do;?}:C;

Die Funktion Cerwartet den Wurm auf dem Stapel und ersetzt ihn durch das Ergebnis.

Beispiele:

> [1 1]
19

> [2]
51

> [1 1 0]
51

Ruby - 131 Zeichen

Ich weiß, dass dies nicht mit den oben genannten GolfScript-Lösungen mithalten kann, und ich bin mir ziemlich sicher, dass hierdurch eine Punktzahl oder mehr Zeichen reduziert werden können, aber ehrlich gesagt bin ich froh, dass ich das Problem ungolfed lösen konnte. Tolles 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}

Meine Pre-Golf-Lösung, von der das oben Genannte abgeleitet ist:

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

Sclipting (43 Zeichen)

글坼가⑴감套擘終長①加⒈丟倘⓶增⓶가采⓶擘❷小終⓷丟❶長貶❷가掊貶插①增復合감不가終終

Dies erwartet die Eingabe als durch Leerzeichen getrennte Liste. Dies gibt die richtige Antwort für 1 1und 2, aber für 2 1oder aus3 es dauert zu lange, so dass ich es aufgegeben habe, darauf zu warten, dass es fertig ist.

Mit Kommentar:

글坼 | 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

k (83)

worm:{-1+*({x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}.)/(1;|,/x)}

Dies kann wahrscheinlich weiter ausgenutzt werden, da es nur die Wiederholung ziemlich einfach umsetzt.

Die grundlegende Evolutionsfunktion {x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}ist 65 Zeichen und verwendet einige Tricks, um die Erhöhung des Alters zu stoppen, wenn der Wurm stirbt. Der Wrapper zwingt eine Eingabe einer einzelnen Ganzzahl in eine Liste, kehrt die Eingabe um (es ist kürzer, die Wiederholung in Bezug auf einen Wurm zu schreiben, der von Ihrer Notation umgekehrt ist), fragt nach dem Fixpunkt, wählt das Alter als Ausgabe aus und passt das Ergebnis an um das Überschwingen in der letzten Generation zu erklären.

Wenn ich den Zwang und die Umkehrung manuell mache, fällt er auf 80 ( {-1+*({x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}.)/(1;x)}).

einige Beispiele:

  worm 1 1 0
51
  worm 2
51
  worm 1 1
19

Leider ist es für Largest Number Printable nur sehr theoretisch sinnvoll, da es recht langsam, auf 64-Bit-Ganzzahlen beschränkt und wahrscheinlich nicht besonders speichereffizient ist.

insbesondere worm 2 1und worm 3nur abwandern (und würde wahrscheinlich 'wsfull(aus dem Gedächtnis) werfen , wenn ich sie weitermachen lasse).

APL (Dyalog Unicode) , 52 Byte ^SBCS

7 Bytes dank @ngn und @ Adám gespeichert.

0{⍬≡⍵:⍺⋄n←⍺+1⋄0=⊃⍵:n∇1↓⍵⋄n∇∊(⊂1n/-∘1@1¨)@1⊆∘⍵⍳⍨⌊\⍵}⌽

Probieren Sie es online!

Erläuterung:

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

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}

Verwendung:

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

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

Probieren Sie es online!

Ich weiß, dass ich EXTREM spät zur Party komme, aber ich dachte, ich würde mich in C daran versuchen, was eine Implementierung einer verknüpften Liste erforderte. Abgesehen davon, dass alle Bezeichner in einzelne Zeichen geändert wurden, ist es kein wirkliches Golfspiel, aber es funktioniert!

Alles in allem bin ich ziemlich glücklich, wenn man bedenkt, dass dies das dritte C / C ++ - Programm ist, das ich jemals geschrieben habe.

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

Probieren Sie es online!

Danke an @xnor für zwei Bytes.

Ich bin der Meinung, dass es einen guten Weg geben sollte, das gemeinsame Inkrement herauszufiltern, aber ich habe noch keinen kurzen gefunden.

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

Probieren Sie es online!

Stax , 31 Bytes

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

Führen Sie es aus und debuggen Sie es