Żywotność robaka

28

Warunki

Robak jest jakaś lista nieujemnych liczb całkowitych, a jej skrajna (czyli ostatni ) element jest nazywany głowy . Jeśli głowa nie jest równa 0, robak ma aktywny segment składający się z najdłuższego ciągłego bloku elementów, który obejmuje głowę i ma wszystkie swoje elementy co najmniej tak duże jak głowa . Zredukowany odcinek czynny jest aktywny segment z głowicą zmniejszana o 1. Na przykład, wirus 3 1 2 3 2zawiera aktywny fragment 2 3 2, a zredukowany odcinek czynny 2 3 1.

Zasady ewolucji

Robak ewoluuje krok po kroku w następujący sposób:

W kroku t (= 1, 2, 3, ...),
    jeśli głowa ma wartość 0: usuń głowę
    inaczej: zamień aktywny segment na t + 1 konkatenowane kopie zredukowanego aktywnego segmentu.

Fakt : Każdy robak ostatecznie ewoluuje na pustą listę , a liczba kroków, które należy wykonać, to żywotność robaka .

(Szczegóły można znaleźć w dokumencie The Worm Principle , pracy LD Beklemisheva. Użycie „listy” w celu oznaczenia skończonej sekwencji i „głowy” w celu oznaczenia jej ostatniego elementu pochodzi z tego artykułu - nie należy tego mylić z powszechnym użyciem list jako abstrakcyjnego typu danych , gdzie head zwykle oznacza pierwszy element.)

Przykłady (aktywny segment w nawiasach)

Robak: 0,1

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

Robak: 1,0

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

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

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

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

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


Na bok

Czas życia robaka jest zwykle ogromny, co pokazują poniższe dolne granice w kategoriach standardowej szybko rosnącej hierarchii funkcji 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)

Co ciekawe, robak [3] ma już żywotność znacznie przewyższającą liczbę Grahama , G:

f ω ω (2) = f ω 2 (2) = f ω2 (2) = f ω + 2 (2) = f ω + 1 (f ω + 1 (2)) >> f ω + 1 (64) > G.


Code Golf Challenge

Napisz możliwie najkrótszy podprogram funkcji o następującym działaniu:

Dane wejściowe : dowolny robak.
Dane wyjściowe : czas życia robaka.

Rozmiar kodu jest mierzony w bajtach.


Oto przykład (Python, golf do około 167 bajtów):

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 : Jeśli t (n) jest okresem życia robaka [n], wówczas tempo wzrostu t (n) jest mniej więcej takie samo jak funkcja Goodsteina . Więc jeśli można to grałem poniżej 100 bajtów, to może dobrze dać zwycięską odpowiedź na największą liczbę druku pytanie . (W przypadku tej odpowiedzi tempo wzrostu można znacznie przyspieszyć, zawsze uruchamiając licznik kroków od n - tej samej wartości co robak [n] - zamiast od 0).

res
źródło
Jestem zdezorientowany twoim kodem. Powiedziałeś, że głowa jest najbardziej wysuniętym w prawo elementem, ale w twoim przykładzie w Pythonie traktujesz głowę jako taki, w[0]który jest * skrajnym lewym elementem tej listy?
@LegoStormtroopr Jeśli możesz uznać listę za lewą i prawą. Jeśli weźmiesz pod uwagę pierwszy i ostatni, możesz zmapować od prawej do pierwszej lub ostatniej podczas czytania początkowego ciągu - co nie jest częścią pytania. Ale wejścia funkcji również nie były ściśle określone.
Bob
@LegoStormtroopr - Good catch; Poprawiłem kod, dodając wiersz, aby odwrócić robaka wejściowego, którego głowa rzeczywiście powinna znajdować się po prawej stronie (tj. Ostatni element na liście w). Dla wydajności program działa na odwróconym robaku.
res
Pierwsze prawidłową odpowiedź dla 2 1może być zbyt wiele, aby poprosić w rozsądnym czasie, ale użytecznym testem jest, że kolejność powinna rozpocząć (2 1), 2 0 2 0, 2 0 (2), 2 0 (1 1 1 1), ...
Peter Taylor
1
@ThePlasmaRailgun - Parafrazując Harveya Friedmana, liczby wyprowadzone z funkcji na poziomie ε_0 w szybko rosnącej hierarchii (np. Czas życia robaków) są całkowicie NIEZNACZNE w porównaniu do DRZEWA (3) .
res

Odpowiedzi:

15

GolfScript ( 56 54 znaków)

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

Demo online

Myślę, że kluczową sztuczką jest prawdopodobnie utrzymanie robaka w odwrotnej kolejności. Oznacza to, że znalezienie długości aktywnego segmentu jest dość kompaktowe: .0+.({<}+??(gdzie 0dodaje się go jako osłonę, aby upewnić się, że znajdziemy element mniejszy niż głowa).


Na marginesie, niektóre analizy długości życia robaka. Będę oznaczamy jako robaka age, head tail(czyli w odwrotnej kolejności od notacji Pytanie za) przy użyciu wykładników wskazać powtórzenia w głowę i ogon: na przykład 2^3jest 2 2 2.

Lemat : dla każdego aktywnego segmentu xsistnieje taka funkcja f_xs, która age, xs 0 tailprzekształca się w f_xs(age), tail.

Dowód: żaden aktywny segment nie może nigdy zawierać 0, więc wiek do czasu usunięcia wszystkiego, zanim ogon jest niezależny od ogona, a zatem jest tylko funkcją xs.

Lemma : dla każdego aktywnego segmentu xsrobak age, xsumiera w wieku f_xs(age) - 1.

Dowód: z poprzedniego lematu age, xs 0przekształca się w f_xs(age), []. Ostatnim krokiem jest usunięcie tego 0, czego wcześniej nie dotykano, ponieważ nigdy nie może ono stanowić części aktywnego segmentu.

Dzięki tym dwóm lematom możemy badać proste proste segmenty.

dla 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

tak f_{1^n} = x -> f_{1^{n-1}}^{x+1}(x+2)(z przypadkiem podstawowym f_{[]} = x -> x+1lub jeśli wolisz f_{1} = x -> 2x+3). Widzimy, że f_{1^n}(x) ~ A(n+1, x)gdzie Ajest funkcja Ackermanna – Pétera.

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

To wystarczy, aby sobie poradzić 1 2( 2 1w notacji pytania):

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

Biorąc pod uwagę dane wejściowe 2 1, oczekujemy wyników ~ 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

i naprawdę mogę zacząć rozumieć, dlaczego ta funkcja rośnie tak niesamowicie.

Peter Taylor
źródło
Bardzo fajny. Myślę, że ten program da również zwycięską odpowiedź na najkrótszy program kończący, którego rozmiar wyjściowy przekracza liczbę Grahama . (Obecny zwycięzca ma 63 bajty kodu Haskell.) Np. Przy 55 bajtach coś w rodzaju (ponieważ mam skłonność do błędów składniowych) 9{-1%0\{\)\.0={.0+.({<}+??\((\+.@<2$*\+}{(;}if.}do;}:L~oblicza czas życia robaka [9], który znacznie przekracza liczbę Grahama - i może być grać w golfa dalej.
res
9

GolfScript, 69 62 znaków

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

Ta funkcja Coczekuje robaka na stosie i zastępuje go wynikiem.

Przykłady:

> [1 1]
19

> [2]
51

> [1 1 0]
51
Howard
źródło
Fantastyczny! Z pewnością możesz to nieco zmodyfikować, aby dać zdecydowanego zwycięzcę pytania „Największy numer do wydrukowania” .
res
Nie widziałem, żebyś tam coś publikował, więc posunąłem się naprzód i opublikowałem modyfikację tego kodu, która jak dotąd uważam za zwycięską odpowiedź - zakładając, że *i ^nie są używane jako operatory arytmetyczne mnożenia i wykładniczo. Z pewnością, jeśli chcesz przesłać tam swoją (niewątpliwie lepszą) odpowiedź, chętnie usunę moją.
res
7

Ruby - 131 znaków

Wiem, że to nie może konkurować z powyższymi rozwiązaniami GolfScript i jestem całkiem pewien, że można zmniejszyć wynik lub więcej postaci, ale szczerze mówiąc, cieszę się, że mogłem rozwiązać problem nierozwiązany. Świetna łamigłówka!

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}

Moje rozwiązanie do gry w golfa, z którego wywodzi się powyższe:

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
OI
źródło
Ogólna wskazówka: wiele problemów z golfem działa na nieujemne liczby całkowite, w takim przypadku if foo==0można je przyciąć if foo<1. To może uratować cię tutaj.
Peter Taylor
Nawiasem mówiąc, fascynuje mnie to, że działa to bez sekundy reverse.
Peter Taylor
Ach nie. Działa tylko na przypadkach testowych, ponieważ mają one tylko aktywne segmenty palindromiczne.
Peter Taylor
Dzięki za wskazówkę golfową, @PeterTaylor. Również dobre złapanie brakującego drugiego biegu wstecznego. Dodałem go. Spróbuję przepisać to w inny sposób, bez późniejszego użycia wstecz. Jestem prawie pewien, że uda mi się sprowadzić elseklauzulę do jednej linii, a następnie zamienić ją if..else..endna zdanie trójkowe. Myślę, że mógłbym również użyć lambda, aby uratować kilka postaci.
OI
6

Sclipting (43 znaki)

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

To oczekuje danych wejściowych jako listy rozdzielonej spacjami. To daje poprawną odpowiedź na 1 1i 2, ale na 2 1lub 3to trwa zbyt długo, więc zrezygnowałem z czekania na jej zakończenie.

Z komentarzem:

글坼 | 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
Timwi
źródło
2
Przydałby się link do tłumacza ... Również 86 bajtów przy użyciu UTF-16?
Peter Taylor
@PeterTaylor: Dzięki, dodałem link do tłumacza do artykułu. I tak, 43 znaki BMP przekładają się na 86 bajtów w UTF-16.
Timwi
5

k (83)

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

prawdopodobnie można to jeszcze pograć w golfa, ponieważ po prostu implementuje on nawrót dość prosto.

podstawowa funkcja ewolucji {x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}, to 65 znaków, i wykorzystuje pewne sztuczki, aby przestać zwiększać wiek, w którym umiera robak. opakowanie wymusza wprowadzenie pojedynczej liczby całkowitej na listę, odwraca dane wejściowe (krótsze jest napisanie rekurencji pod względem robaka odwróconego od notacji), prosi o punkt stały, wybiera wiek jako wynik i dostosowuje wynik w celu uwzględnienia przekroczenia w ostatnim pokoleniu.

jeśli zrobię przymus i odwrócenie ręcznie, spada do 80 ( {-1+*({x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}.)/(1;x)}).

kilka przykładów:

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

Niestety, prawdopodobnie nie ma większego zastosowania w przypadku największej liczby drukowalnych liczb , z wyjątkiem bardzo teoretycznego znaczenia, ponieważ jest dość powolny, ograniczony do 64-bitowych liczb całkowitych i prawdopodobnie nie jest szczególnie wydajny pod względem pamięci.

w szczególności worm 2 1i worm 3po prostu rezygnować (i prawdopodobnie rzuciłbym 'wsfull(z pamięci), jeśli pozwolę im iść dalej).

Aaron Davies
źródło
Próbowałem uruchomić Twój program za pomocą tego interpretera online , ale nie wyświetla on żadnych wyników. (Przesłanie pliku tekstowego z rozszerzeniem .k ma wywoływać interpreter K.) Czy wiesz, co można zrobić, aby wysłać wyjście na standardowe wyjście?
res
Wygląda na to, że działa kona, klon k3 typu open source. Mój kod jest napisany w k4 i jest mało prawdopodobne, aby był kompatybilny z k3. Możesz pobrać ograniczoną czasowo bezpłatną kopię q / k4 na stronie kx.com/software-download.php ; gdy już to zrobisz, uruchom REPL, wpisz ` to switch from q` do ki wklej mój kod. Alternatywnie możesz zapisać mój kod w pliku z .krozszerzeniem i załadować go do interpretera.
Aaron Davies
2

APL (Dyalog Unicode) , 52 bajty SBCS

Zaoszczędzono 7 bajtów dzięki @ngn i @ Adám.

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

Wypróbuj online!

Wyjaśnienie:

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=⊃⍵:n1↓⍵  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
jastrząb
źródło
Uznałem, że APL miałoby na to naprawdę czyste rozwiązanie, czy nie jest to język oparty na tablicy?
ThePlasmaRailgun
1

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}

Stosowanie:

scala> T(List(2))
res0: Int = 51
ValarDohaeris
źródło
1

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
tartin
źródło
1

C (gcc) , 396 bajtów

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

Wypróbuj online!

Wiem, że jestem wyjątkowo spóźniony na imprezę, ale pomyślałem, że spróbuję tego w C, co wymagało implementacji listy połączonej. To wcale nie jest gra w golfa oprócz zmiany wszystkich identyfikatorów na pojedyncze znaki, ale działa!

Podsumowując, jestem bardzo szczęśliwy, biorąc pod uwagę, że jest to trzeci program C / C ++, jaki kiedykolwiek napisałem.

ThePlasmaRailgun
źródło
Czy naprawdę potrzebujesz połączonej listy? Dlaczego nie przydzielić tablic? Ponieważ jest to golf golfowy, nie musisz nawet zawracać sobie głowy uwalnianiem ich, gdy skończysz. Państwo może nawet być w stanie znaleźć sposób, aby zapisać je na stosie wywołań (nie jestem pewien).
dfeuer
Ponadto nie potrzebujesz głównej funkcji. Po prostu napisz funkcję, która bierze robaka za argument i zwraca jego żywotność. Robakiem może być tablica i jej długość, a może tablica kończąca się liczbą ujemną.
dfeuer
1

Haskell , 84 bajty

(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

Wypróbuj online!

Dzięki @xnor za dwa bajty.

Wydaje mi się, że powinien istnieć dobry sposób na obliczenie wspólnego przyrostu, ale nie znalazłem jeszcze krótkiego.

dfeuer
źródło
1
Dwa małe golfa : zaznacz drugi pusty przypadek listy i nprzesuń w dół o 1.
xnor
Myślę też, że powinien istnieć sposób, aby nie pisać (n+1)!dwa razy, ale moja próba była tylko powiązana.
xnor