Simulasi Sistem Tag Siklik

14

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 produksi0 saat ini dilewati
  • jika itu produksi1 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 0dan 1, Truedan False, Tdan NIL, Adan B, atau bahkan 1dan 0, atau apa pun yang Anda buat, selama Anda konsisten. Semua input dan output harus menggunakan alfabet yang sama, dan Anda harus menunjukkan untuk 0apa dan untuk apa 1.

  • 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 0menjadi kata input itu sendiri, dan generasi 1menjadi 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).

marinus
sumber
Um, apakah Anda yakin output Anda dalam contoh sudah benar? Berdasarkan contoh lain yang Anda berikan, saya pikir itu adalah gen 5 ...
FryAmTheEggman
Bisakah kita mengambil input dalam urutan yang berbeda?
Martin Ender
1
@FryAmTheEggman: Benar, maksud saya kolom 'sebelum'. Jika lebih banyak orang melakukan kesalahan ini, saya akan mengubah pertanyaan saya untuk menerimanya juga. Saya akui saya tidak begitu jelas.
marinus
@ MartinBüttner: selama Anda menentukan urutannya, itu tidak masalah.
marinus

Jawaban:

4

GolfScript (17 hingga 19 byte tergantung pada format input dan format output yang diterima)

18 byte:

~.@*<{\1,or(@*+}/`

Mengambil input dalam formulir [1 1 0 0 1] [[0 1 0] [0 0 0] [1 1 1 1]] 4dan memberikan output dalam formulir [1 0 1 0 0 0 0]. (Bisa 17 byte tanpa yang terakhir `jika output seperti 1010000itu dapat diterima).

Demo online

19 byte:

~.@*<{\0`or(1&@*+}/

Mengambil input dalam formulir "11001" ["010" "000" "1111"] 4.

Demo online

Pembedahan

~        # Evaluate input: stack: word productions gen
.@*<     # Produce a list of the right number of productions with suitable repetition
{        # For each of those productions:
  \      #   Bring the word to the top
  0`or   #   Ensure that we don't get an error if the word is empty
  (1&    #   Pop the first char from the word and evaluate it
  @*     #   Repeat the production that many times
  +      #   Concatenate 0 or 1 copies of the production to the rest of the word
}/       # Endforeach

Kredit untuk Martin Büttner 's solusi CJam untuk ide menghasilkan daftar produksi oleh pengulangan dan pemotongan.

Peter Taylor
sumber
Anda terikat dengan solusi CJam yang Anda kutip, jadi saya telah memilih jawaban itu. Jika Anda mencukur satu byte lagi, saya akan mempertimbangkan kembali :)
marinus
@marinus, apakah Anda menerima versi 17 byte yang saya rujuk dalam teks jawaban saya?
Peter Taylor,
Belum melihat itu, tetapi terlihat valid. Anda mungkin harus menandainya sedikit lebih jelas.
marinus
5

Haskell, 55 53 51

(t:w)%p|t=w++p|0<1=w
x%_=x
e w=(!!).scanl(%)w.cycle

ini menggunakan Trueas 1dan Falseas 0. contoh dijalankan:

*Main> let t=True ; f=False
*Main> e [t,f,t] [[f,f,f],[t,t,t]] 4
[False,False,False,False,False]
haskeller bangga
sumber
3

CJam, 31 30 28 27 24 18 byte

{_@*<{\_0a?(@*+}/}

Ini mendefinisikan blok (hal yang paling dekat dengan functioN), yang mengharapkan input berada di stack seperti ini

[1 1 0 0 1] [[0 1 0] [0 0 0] [1 1 1 1]] 9

Ini juga akan meninggalkan array 0s dan 1s di stack.

Uji di sini. Tempel input satu baris pertama, kode pada baris ketiga, dan tambahkan a ~untuk benar-benar mengevaluasi blok. Misalnya

[1 1 0 0 1] [[0 1 0] [0 0 0] [1 1 1 1]] 9
{_@*<{\_0a?(@*+}/}~

Jika output tidak harus memiliki bentuk yang sama dengan input

Penjelasan:

_@*<{\_0a?(@*+}/
_@               "Duplicate the generation and pull the productions to the top.";
  *<             "Repeat the productions N times and take the first N elements.";
    {         }/ "For each element in that list, run this block.";
     \           "Swap production and current word W.";
      _0a?       "W = (W != []) ? W : [0]. This is to ensure we can unshift an element.";
          (      "Unshift the first 0 or 1 from the word.";
           @     "Rotate the stack, pulling the production to the top.";
            *    "Repeat it 0 or 1 times.";
             +   "Append to the word.";

Keadaan akhir kata dibiarkan di tumpukan.

Terima kasih kepada Peter Taylor karena membuat saya mengunjungi kembali ini.

Martin Ender
sumber
1
l~{_,g{('1=@(:Pa+@@P*+}*}*\;28 dan masih ruang untuk perbaikan (khususnya (:Pbagian), tetapi waktu untuk makan siang
Pengoptimal
@Optimizer Ah, ide bagus. Terima kasih. Dan ya, :Pitu juga mengganggu saya: D
Martin Ender
l~{_,g{(si@(:Pa+@@P*+}*}*\;: 27 dan setelah melihatnya, :Psebenarnya efisien: P
Optimizer
_,gjuga bisa diganti dengan _!!byte yang sama.
Pengoptimal
@ Pengoptimal saya mungkin juga menggunakannya _{...}{}?.
Martin Ender
2

Mathematica, 84 80 77 karakter

f[_,w_,_]=w;f[p_,{x_,y___},n_/;n>0]:=f[RotateLeft@p,Flatten@{y,p~Take~x},n-1]

Contoh:

f[{{0, 1, 0}, {0, 0, 0}, {1, 1, 1, 1}}, {1, 1, 0, 0, 1}, 4]

{1, 0, 1, 0, 0, 0, 0}

alephalpha
sumber
2

Pyth 22

Membutuhkan semua 3 argumen sebagai input terpisah.

#Vvw=z+tz*@Q%NlQshz)zq

Membawa argumen seperti:

11001
["010","000","1111"]
4

Penjelasan:

                        : Implicit: z = input(); Q=eval(input())
#                       : Loop until an exception is thrown
 Vvw               )    : for N in range(eval(input()))
    =z                  : assign to z
      +tz               : the sum of the tail of z and
         *@Q%NlQ        : Q[N%len(Q)] times
                shz     : the numeric value of the first character in z
                    zq  : print z then throw exception

Python 2 - 61 67 91 105 124

c=lambda p,w,g:g*w and c(p[1:]+p[:1],w[1:]+w[0]*p[0],g-1)or w

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

>>> c([[0,1,0],[0,0,0],[1,1,1,1]],[1,1,0,0,1],4)
[1, 0, 1, 0, 0, 0, 0]
FryAmTheEggman
sumber
1
Tentunya lebih pendek menggunakan lambda dan hanya menulis g and wuntuk x? Juga, saya pikir g*wharus bekerja untuk memberikan nilai kebenaran ketika keduanya gbukan nol dan bukan wkosong.
xnor
Juga, saya tidak mengerti bagian dalam if x else w. Tidak akan xselalu benar karena kode ini hanya dijalankan if x, atau apakah saya kehilangan sesuatu?
xnor
@ xnor Tentunya, Anda sepenuhnya benar :)
FryAmTheEggman
1
Beberapa lagi bermain golf dengan and/ ortrik dan memutar pbukannya menambah n:c=lambda p,w,g:g*w and c(p[1:]+p[:1],w[1:]+w[0]*p[0],g-1)or w
xnor
@ xnor Terima kasih :) Juga, sekarang setelah Anda membuatnya menjadi fungsi 3 variabel, saya pikir saya menerjemahkannya ke Pyth ...
FryAmTheEggman
1

Javascript ES6 - 88 byte

f=(p,w,g,n)=>g?w.replace(/(.)(.*)/,(_,a,b)=>f(p,a*1?b+p[(n=n||0)%p.length]:b,g-1,n+1)):w

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:

f = (p,w,g,n) =>
    g ?
        w.replace( /(.)(.*)/, (_,a,b) =>
            f( p, a*1 ? b + p[(n=n||0)%p.length] : b, g-1, n+1 )
        )
    :
        w

Output Sampel

f(['010','000','1111'],'11001',4)
"1010000"

Sekarang saksikan bahasa-bahasa golf datang dan membantai kita berdua. : D

COTO
sumber
Saya benar-benar menghapus posting saya karena saya mendapat jawaban berbeda untuk dua contoh. Sudahkah Anda mencoba contoh kemana dia pergi dari generasi ke generasi? Tampaknya menjadi salah satu dibandingkan dengan contoh panggilan penuh yang dia berikan ...
FryAmTheEggman
Dan jangan khawatir, saya yakin Anda tidak menyalin saya: P
FryAmTheEggman
@FryAmTheEggman: Milik saya secara konsisten menghasilkan kolom "sebelum" untuk generasi bernomor. Ini konsisten dengan contoh dalam OP, dan tampaknya logis bahwa "generasi 0" hanya akan mengembalikan input tanpa memprosesnya, yang konsisten dengan interpretasi ini. Kebetulan, saya menambahkan "copy" disclaimer karena solusinya sangat mirip dalam beberapa hal. Kami menggunakan nama argumen yang sama, struktur rekursif dasar yang sama, dan kami bahkan menambahkan argumen keempat phantom yang sama n,. Pikiran yang hebat, eh? : D
COTO
Oke, saya kira jika salah satu dari kita salah, kita berdua salah! Bersatu kita berdiri.
FryAmTheEggman
@FryAmTheEggman: Anda tidak salah tentang Mr. Peppe. ;)
COTO