Sistem tag siklik adalah model komputasi Turing-complete kecil yang terdiri dari alfabet dua simbol (saya akan menggunakan {0,1}
), daftar produksi siklik terbatas hingga kosong yang terdiri dari dua simbol tersebut, dan kata tak terikat yang juga terdiri dari dua simbol itu.
Di setiap langkah:
- elemen pertama dalam kata tersebut dihapus
- jika itu produksi
0
saat ini dilewati - jika itu produksi
1
saat ini ditambahkan ke akhir kata . - produksi selanjutnya menjadi aktif. Jika ini adalah produksi terakhir, kembali ke yang pertama.
Sistem berhenti ketika kata menjadi kosong.
Contoh (dari Wikipedia):
Productions: (010, 000, 1111)
Initial word: 11001
Generation Production Word (before) Word (after)
0 010 11001 → 1001010
1 000 1001010 → 001010000
2 1111 001010000 → 01010000
3 010 01010000 → 1010000
4 000 1010000 → 010000000
5 1111 010000000 → 10000000
6 010 10000000 → 0000000010
7 000 0000000010 → 000000010
8 1111 000000010 → 00000010
9 010 00000010 → 0000010
Tugas Anda, jika Anda memilih untuk menerimanya, adalah menulis program atau fungsi yang membutuhkan:
- daftar produksi,
- kata awal, dan
- sebuah generasi,
dan mencetak atau mengembalikan kata pada generasi itu.
Sebagai contoh,
cyclic_tag(
prod=[[0,1,0],[0,0,0],[1,1,1,1]],
word=[1,1,0,0,1],
gen=4) => [1,0,1,0,0,0,0]
Detail implementasi:
Alfabet tidak masalah. Anda dapat menggunakan
0
dan1
,True
danFalse
,T
danNIL
,A
danB
, atau bahkan1
dan0
, atau apa pun yang Anda buat, selama Anda konsisten. Semua input dan output harus menggunakan alfabet yang sama, dan Anda harus menunjukkan untuk0
apa dan untuk apa1
.Panjang kata harus secara teoritis tidak terbatas. Artinya, Anda tidak boleh meng-hardcode panjang kata maksimum. Jika saya menjalankan program Anda pada komputer ideal dengan jumlah memori tak terbatas, program Anda secara teoritis harus dapat memanfaatkannya. (Anda dapat mengabaikan batas juru bahasa / kompiler Anda.)
Jika sistem yang diberikan berhenti sebelum generasi yang diberikan tercapai, Anda harus mengembalikan atau mencetak kata yang kosong.
Produksi kosong ada, dan Anda harus dapat mengatasinya. Jika Anda menulis program lengkap, I / O Anda juga harus bisa menanganinya.
Sunting : Saya awalnya bermaksud agar generasi 0
menjadi kata input itu sendiri, dan generasi 1
menjadi hasil dari langkah pertama. Yaitu, saya bermaksud agar Anda mengembalikan kolom sebelumnya . Namun , karena saya belum cukup jelas dalam menyatakan ini, saya akan menerima kedua opsi ; untuk setiap generasi Anda dapat mengembalikan nilai di kolom sebelum atau sesudah . Anda harus menyatakan bahwa Anda mengikuti kolom setelah , jika Anda melakukannya. Anda juga harus konsisten di kolom mana yang Anda pilih.
Saya akan memberikan kode terkecil seminggu dari sekarang (27/10/2014).
sumber
Jawaban:
GolfScript (17 hingga 19 byte tergantung pada format input dan format output yang diterima)
18 byte:
Mengambil input dalam formulir
[1 1 0 0 1] [[0 1 0] [0 0 0] [1 1 1 1]] 4
dan memberikan output dalam formulir[1 0 1 0 0 0 0]
. (Bisa 17 byte tanpa yang terakhir`
jika output seperti1010000
itu dapat diterima).Demo online
19 byte:
Mengambil input dalam formulir
"11001" ["010" "000" "1111"] 4
.Demo online
Pembedahan
Kredit untuk Martin Büttner 's solusi CJam untuk ide menghasilkan daftar produksi oleh pengulangan dan pemotongan.
sumber
Haskell,
555351ini menggunakan
True
as1
danFalse
as0
. contoh dijalankan:sumber
CJam,
313028272418 byteIni mendefinisikan blok (hal yang paling dekat dengan functioN), yang mengharapkan input berada di stack seperti ini
Ini juga akan meninggalkan array
0
s dan1
s di stack.Uji di sini. Tempel input satu baris pertama, kode pada baris ketiga, dan tambahkan a
~
untuk benar-benar mengevaluasi blok. MisalnyaJika output tidak harus memiliki bentuk yang sama dengan input
Penjelasan:
Keadaan akhir kata dibiarkan di tumpukan.
Terima kasih kepada Peter Taylor karena membuat saya mengunjungi kembali ini.
sumber
l~{_,g{('1=@(:Pa+@@P*+}*}*\;
28 dan masih ruang untuk perbaikan (khususnya(:P
bagian), tetapi waktu untuk makan siang:P
itu juga mengganggu saya: Dl~{_,g{(si@(:Pa+@@P*+}*}*\;
: 27 dan setelah melihatnya,:P
sebenarnya efisien: P_,g
juga bisa diganti dengan_!!
byte yang sama._{...}{}?
.Mathematica,
84 8077 karakterContoh:
sumber
Pyth 22
Membutuhkan semua 3 argumen sebagai input terpisah.
Membawa argumen seperti:
Penjelasan:
Python 2 - 61
67 91 105 124Pretty Joe-Basic answer. Diasumsikan produksi kosong
[[]]
.Terima kasih kepada @xnor, karena menunjukkan bahwa bermain golf pada jam 2 pagi adalah keputusan yang buruk.
Tambahan terima kasih kepada @xnor, kepada siapa saya tampaknya berutang 50% dari skor saya.
Sampel:
sumber
g and w
untukx
? Juga, saya pikirg*w
harus bekerja untuk memberikan nilai kebenaran ketika keduanyag
bukan nol dan bukanw
kosong.if x else w
. Tidak akanx
selalu benar karena kode ini hanya dijalankanif x
, atau apakah saya kehilangan sesuatu?and
/or
trik dan memutarp
bukannya menambahn
:c=lambda p,w,g:g*w and c(p[1:]+p[:1],w[1:]+w[0]*p[0],g-1)or w
Javascript ES6 - 88 byte
Tampak mirip dengan jawaban Fry yang baru saja muncul di browser saya. (Tidak menyalin, saya bersumpah dengan sungguh-sungguh.)
Tampaknya dia pergi rute array sementara aku pergi rute string / regex, namun.
Diperluas:
Output Sampel
Sekarang saksikan bahasa-bahasa golf datang dan membantai kita berdua. : D
sumber
n
,. Pikiran yang hebat, eh? : D