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 2
zawiera 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).
w[0]
który jest * skrajnym lewym elementem tej listy?2 1
moż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)
, ...Odpowiedzi:
GolfScript (
5654 znaków)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+.({<}+??
(gdzie0
dodaje 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ład2^3
jest2 2 2
.Lemat : dla każdego aktywnego segmentu
xs
istnieje taka funkcjaf_xs
, któraage, xs 0 tail
przekształca się wf_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
xs
robakage, xs
umiera w wiekuf_xs(age) - 1
.Dowód: z poprzedniego lematu
age, xs 0
przekształca się wf_xs(age), []
. Ostatnim krokiem jest usunięcie tego0
, 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
,tak
f_{1^n} = x -> f_{1^{n-1}}^{x+1}(x+2)
(z przypadkiem podstawowymf_{[]} = x -> x+1
lub jeśli woliszf_{1} = x -> 2x+3
). Widzimy, żef_{1^n}(x) ~ A(n+1, x)
gdzieA
jest funkcja Ackermanna – Pétera.To wystarczy, aby sobie poradzić
1 2
(2 1
w notacji pytania):Biorąc pod uwagę dane wejściowe
2 1
, oczekujemy wyników ~A(A(5,4), A(5,4))
.i naprawdę mogę zacząć rozumieć, dlaczego ta funkcja rośnie tak niesamowicie.
źródło
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.GolfScript,
6962 znakówTa funkcja
C
oczekuje robaka na stosie i zastępuje go wynikiem.Przykłady:
źródło
*
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ą.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!
Moje rozwiązanie do gry w golfa, z którego wywodzi się powyższe:
źródło
if foo==0
można je przyciąćif foo<1
. To może uratować cię tutaj.reverse
.else
klauzulę do jednej linii, a następnie zamienić jąif..else..end
na zdanie trójkowe. Myślę, że mógłbym również użyć lambda, aby uratować kilka postaci.Sclipting (43 znaki)
To oczekuje danych wejściowych jako listy rozdzielonej spacjami. To daje poprawną odpowiedź na
1 1
i2
, ale na2 1
lub3
to trwa zbyt długo, więc zrezygnowałem z czekania na jej zakończenie.Z komentarzem:
źródło
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:
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 1
iworm 3
po prostu rezygnować (i prawdopodobnie rzuciłbym'wsfull
(z pamięci), jeśli pozwolę im iść dalej).źródło
` to switch from
q` dok
i wklej mój kod. Alternatywnie możesz zapisać mój kod w pliku z.k
rozszerzeniem i załadować go do interpretera.APL (Dyalog Unicode) , 52 bajty SBCS
Zaoszczędzono 7 bajtów dzięki @ngn i @ Adám.
Wypróbuj online!
Wyjaśnienie:
źródło
Scala, 198
Stosowanie:
źródło
K, 95
.
źródło
C (gcc) , 396 bajtów
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.
źródło
Haskell , 84 bajty
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.
źródło
n
przesuń w dół o 1.(n+1)!
dwa razy, ale moja próba była tylko powiązana.Perl 5
-pa
, 92 bajtówWypróbuj online!
źródło
Stax , 31 bajtów
Uruchom i debuguj
źródło