Ketentuan
Sebuah worm adalah setiap daftar bilangan bulat non-negatif, dan yang paling kanan (yaitu, terakhir ) elemen disebut kepala . Jika kepala bukan 0, cacing memiliki segmen aktif yang terdiri dari blok elemen yang paling panjang yang berdekatan yang mencakup kepala dan memiliki semua elemennya setidaknya sebesar kepala . The segmen aktif berkurang adalah segmen aktif dengan kepala dikurangi dengan 1. Sebagai contoh, worm 3 1 2 3 2
memiliki segmen aktif 2 3 2
, dan segmen aktif berkurang adalah 2 3 1
.
Aturan evolusi
Cacing berevolusi langkah demi langkah sebagai berikut:
Pada langkah t (= 1, 2, 3, ...),
jika head adalah 0: hapus head yang
lain: ganti segmen aktif dengan t + 1 salinan gabungan dari segmen aktif tereduksi.
Fakta : Cacing apa pun akhirnya berevolusi menjadi daftar kosong , dan jumlah langkah untuk melakukannya adalah masa hidup cacing itu .
(Detail dapat ditemukan dalam The Worm Principle , sebuah makalah oleh LD Beklemishev. Penggunaan "daftar" berarti urutan yang terbatas, dan "kepala" yang berarti elemen terakhirnya , diambil dari makalah ini - tidak boleh dikacaukan dengan penggunaan umum untuk daftar sebagai tipe data abstrak , di mana head biasanya berarti elemen pertama .)
Contoh (segmen aktif dalam tanda kurung)
Cacing: 0,1
step worm
0(1)
1 0 0 0
2 0 0
3 0
4 <- lifetime = 4
Cacing: 1,0
step worm
1 0
1 (1)
2 0 0 0
3 0 0
4 0
5 <- lifetime = 5
Cacing: 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
Cacing: 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
Cacing: 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 = ??
Cacing: 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 = ??
Ke samping
Umur cacing biasanya sangat besar, seperti yang ditunjukkan oleh batas bawah berikut dalam hal hierarki standar fungsi yang tumbuh cepat 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)
Hebatnya, worm [3] sudah memiliki masa hidup yang jauh melebihi jumlah Graham , G:
f ω ω (2) = f ω 2 (2) = f ω2 (2) = f ω + 2 (2) = f ω + 1 (f ω + 1 (2)) >> f ω + 1 (64) > G.
Tantangan Golf Code
Tulis subprogram fungsi sesingkat mungkin dengan perilaku berikut:
Input : Cacing apa saja.
Output : Masa hidup worm.Ukuran kode diukur dalam byte.
Berikut ini sebuah contoh (Python, golf hingga sekitar 167 byte):
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 : Jika t (n) adalah masa hidup cacing [n], maka laju pertumbuhan t (n) kira-kira sama dengan fungsi Goodstein . Jadi, jika ini bisa di-golf hingga di bawah 100 byte, itu bisa juga memberikan jawaban yang menang untuk pertanyaan Jumlah Cetak Terbesar . (Untuk jawaban itu, laju pertumbuhan bisa sangat dipercepat dengan selalu memulai penghitung langkah di n - nilai yang sama dengan worm [n] - alih-alih memulainya di 0.)
w[0]
yang merupakan elemen paling kiri dari daftar itu?2 1
mungkin terlalu banyak untuk meminta dalam waktu yang wajar, tetapi tes yang berguna adalah bahwa urutan harus mulai(2 1)
,2 0 2 0
,2 0 (2)
,2 0 (1 1 1 1)
, ...Jawaban:
GolfScript (
5654 karakter)Demo online
Saya pikir trik utama di sini adalah menjaga agar worm tetap dalam urutan terbalik. Itu berarti cukup kompak untuk menemukan panjang segmen aktif:
.0+.({<}+??
(di mana0
ditambahkan sebagai pelindung untuk memastikan bahwa kami menemukan elemen yang lebih kecil dari kepala).Sebagai tambahan, beberapa analisis umur cacing. Saya akan menunjukkan cacing sebagai
age, head tail
(yaitu dalam urutan terbalik dari notasi pertanyaan ini) menggunakan eksponen untuk menunjukkan pengulangan di kepala dan ekor: misalnya2^3
adalah2 2 2
.Lemma : untuk setiap segmen aktif
xs
, ada fungsif_xs
sedemikian rupa sehinggaage, xs 0 tail
berubah menjadif_xs(age), tail
.Bukti: tidak ada segmen aktif yang dapat mengandung a
0
, jadi usia pada saat kita menghapus semuanya sebelum ekor tidak tergantung pada ekor dan karenanya hanya berfungsi sebagaixs
.Lemma : untuk setiap segmen aktif
xs
, cacingage, xs
mati pada usiaf_xs(age) - 1
.Bukti: oleh lemma sebelumnya,
age, xs 0
berubah menjadif_xs(age), []
. Langkah terakhir adalah penghapusan itu0
, yang tidak tersentuh sebelumnya karena tidak pernah dapat membentuk bagian dari segmen aktif.Dengan kedua lemmata itu, kita dapat mempelajari beberapa segmen aktif sederhana.
Untuk
n > 0
,jadi
f_{1^n} = x -> f_{1^{n-1}}^{x+1}(x+2)
(dengan case dasarf_{[]} = x -> x+1
, atau jika Anda sukaf_{1} = x -> 2x+3
). Kita melihat bahwa dif_{1^n}(x) ~ A(n+1, x)
manaA
fungsi Ackermann – Péter.Itu cukup untuk menangani
1 2
(2 1
dalam notasi pertanyaan):Jadi diberi input,
2 1
kita mengharapkan output ~A(A(5,4), A(5,4))
.dan saya benar-benar dapat mulai memahami mengapa fungsi ini tumbuh begitu gila.
sumber
9{-1%0\{\)\.0={.0+.({<}+??\((\+.@<2$*\+}{(;}if.}do;}:L~
menghitung umur worm [9], yang jauh melebihi jumlah Graham - dan dapat menjadi bermain golf lebih lanjut.GolfScript,
6962 karakterFungsi
C
mengharapkan worm pada stack dan menggantinya dengan hasilnya.Contoh:
sumber
*
dan^
tidak digunakan sebagai operator aritmatika penggandaan dan secara eksponensial. Tentu saja, jika Anda ingin mengirimkan jawaban Anda sendiri (tanpa diragukan lagi superior) di sana, saya akan dengan senang hati menghapus jawaban saya.Ruby - 131 karakter
Saya tahu ini tidak dapat bersaing dengan solusi GolfScript di atas dan saya cukup yakin bahwa ini dapat mengurangi skor atau lebih banyak karakter, tapi jujur saya senang bisa menyelesaikan masalah yang ungolfed. Teka-teki yang bagus!
Solusi pra-golf saya yang darinya berasal di atas:
sumber
if foo==0
ini dapat dipangkasif foo<1
. Itu bisa menyelamatkanmu satu char di sini.reverse
.else
klausa ke satu baris dan kemudian menukar denganif..else..end
pernyataan ternary. Saya juga bisa menggunakan lambda untuk menyimpan beberapa karakter, saya pikir.Sclipting (43 karakter)
Ini mengharapkan input sebagai daftar yang dipisahkan oleh ruang. Ini menghasilkan jawaban yang benar untuk
1 1
dan2
, tetapi untuk2 1
atau3
terlalu lama jadi saya menyerah menunggu sampai selesai.Dengan komentar:
sumber
k (83)
worm:{-1+*({x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}.)/(1;|,/x)}
ini mungkin bisa di-pegolf lebih jauh, karena hanya mengimplementasikan perulangan dengan cukup mudah.
fungsi evolusi dasar
{x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}
,, adalah 65 karakter, dan menggunakan beberapa trik untuk berhenti menambah usia ketika worm mati. pembungkus memaksa input bilangan bulat tunggal ke daftar, membalikkan input (lebih pendek untuk menulis pengulangan dalam hal worm dibalik dari notasi Anda), meminta fixpoint, memilih usia sebagai output, dan menyesuaikan hasilnya untuk memperhitungkan overshoot dalam generasi terakhir.jika saya melakukan pemaksaan dan pembalikan secara manual, itu turun menjadi 80 (
{-1+*({x,,(,/((x+:i)#,@[y@&w;(i:~~#y)#0;-1+]),y@&~w:&\~y<*y;1_y)@~*y}.)/(1;x)}
).beberapa contoh:
sayangnya, itu mungkin tidak banyak digunakan untuk Largest Number Printable , kecuali dalam arti yang sangat teoretis, karena sangat lambat, terbatas pada bilangan bulat 64-bit, dan mungkin tidak terlalu hemat memori.
khususnya,
worm 2 1
danworm 3
hanya churn (dan mungkin akan membuang'wsfull
(kehabisan memori) jika saya membiarkan mereka terus berjalan).sumber
` to switch from
q` untukk
, dan tempel kode saya. Atau, Anda dapat menyimpan kode saya dalam file dengan.k
ekstensi dan memuatnya ke juru bahasa.APL (Dyalog Unicode) , 52 byte SBCS
Disimpan 7 byte berkat @ngn dan @ Adám.
Cobalah online!
Penjelasan:
sumber
Scala, 198
Pemakaian:
sumber
K, 95
.
sumber
C (gcc) , 396 byte
Cobalah online!
Saya tahu saya sangat terlambat ke pesta, tapi saya pikir saya akan mencoba ini di C, yang membutuhkan implementasi daftar terkait. Ini tidak benar-benar golf sama sekali selain mengubah semua pengidentifikasi menjadi karakter tunggal, tetapi berfungsi!
Semua dalam semua, saya cukup senang mengingat ini adalah program ke-3 C / C ++ yang pernah saya tulis.
sumber
Haskell , 84 byte
Cobalah online!
Berkat @xnor untuk dua byte.
Saya merasa harus ada cara yang baik untuk memperhitungkan kenaikan umum, tetapi saya belum menemukan yang singkat.
sumber
n
ke bawah dengan 1.(n+1)!
dua kali, tetapi usaha saya hanya mengikat.Perl 5
-pa
, 92 byteCobalah online!
sumber
Stax , 31 byte
Jalankan dan debug itu
sumber