pengantar

Dalam tantangan ini, kami akan mensimulasikan otomat seluler probabilistik tertentu menggunakan nomor pseudorandom yang sangat buruk. Otomat seluler didefinisikan pada string biner dengan aturan lokal berikut. Misalkan tetangga kiri sel dan sel itu sendiri memiliki status adan b.

• Jika min(a,b) == 0, maka keadaan baru badalah max(a,b).
• Jika min(a,b) == 1, maka keadaan baru bdipilih secara acak {0,1}.

Gambar berikut menunjukkan satu kemungkinan evolusi 10 langkah dari satu 1.

1
11
101
1111
11001
101011
1111111
10001001
110011011
1010111101

Perhatikan bagaimana dua 1s yang berdekatan terkadang berevolusi menjadi 1, dan terkadang ke 0, dan bit-bit perbatasan selalu 1s. Tugas Anda adalah menghasilkan evolusi otomat seluler dari bentuk ini.

Input

Input Anda adalah bilangan bulat positif n, menunjukkan jumlah baris yang akan ditampilkan, dan daftar bit Lyang tidak kosong , yang kami gunakan sebagai sumber keacakan.

Keluaran

Output Anda adalah daftar daftar atau array 2D bit, menggambarkan evolusi tunggal 1untuk nlangkah waktu, seperti pada gambar di atas. Anda dapat mengisi output dengan 0s untuk mendapatkan baris dengan panjang yang sama, jika diinginkan, tetapi tidak boleh ada leading 0.

Pilihan acak dalam otomat seluler harus diambil dari daftar L, melompat kembali ke awal ketika habis. Secara lebih eksplisit, jika output dilintasi satu baris pada waktu membentuk atas ke bawah, kiri ke kanan, maka pilihan acak berturut-turut akan membentuk daftar Ldiulang sebanyak yang diperlukan.

Contoh

Misalkan inputnya adalah n = 7dan L = [0,1,0]. Kemudian otomat seluler berkembang sebagai berikut selama 7 langkah, di mana kami telah menempatkan vhak di atas setiap pilihan acak:

[1]

[1,1]
   v
[1,0,1]

[1,1,1,1]
   v v v
[1,1,0,0,1]
   v
[1,1,1,0,1,1]
   v v   v
[1,0,0,1,1,1,1]

Jika kita membaca semua bit yang ditandai dengan v, kita dapatkan 01001001, yang Ldiulang 2,66 kali. Bit acak berikutnya adalah 0.

Aturan dan Penilaian

Anda dapat menulis program atau fungsi lengkap. Hitungan byte terendah menang, dan celah standar tidak diizinkan. Format input dan output yang tepat tidak penting (sesuai alasan).

Uji Kasus

Versi deterministik, setiap bit acak adalah 0:

Inputs: 10 [0]
Output:
1
11
101
1111
10001
110011
1010101
11111111
100000001
1100000011

Setiap bit acak adalah 1:

Inputs: 6 [1,1]
Output:
1
11
111
1111
11111
111111

Versi pseudorandom:

Inputs: 10 [0,0,1]
Output:
1
11
101
1111
10101
111111
1010011
11110101
101011111
1111101001

Inputs: 10 [1,0,0,1]
Output:
1
11
111
1001
11011
111111
1001101
11010111
111111101
1011001111

Inputs: 15 [1,1,1,0,0,0]
Output:
1
11
111
1111
10001
110011
1110111
11011001
111111011
1100011111
11100100011
111101100101
1001111101111
11011000111111
101101001011101

Pyth, 33 byte

jjLk.u++1m?hSde=.<Q1sd.:N2 1tvz]1

Cobalah online: Demonstrasi atau Test Suite

Penjelasan:

jjLk.u++1m?hSde=.<Q1sd.:N2 1tvz]1  implicit: Q = input list
    .u                      tvz]1  reduce N=[1] input-1 times by applying
                      .:N2           all substrings of length 2
         m                           map each d of ^ to:
          ?hSd                         if min(d) = 0 then:
               =.<Q1                     rotate Q by one
              e                          and use the last element
                    sd                 else use sum(d) (=max(d))
      ++1                  1         add a 1 at the front and the back
                                   .u gives all intermediate results
 jLk                               join these lists to strings
j                                  print each string on a line

Retina , 139 byte

^.
1

 00:0 01:1 10:1 11:
(m`^(..)((\S*)(?<=0) .*)
$1$3#$1!$2
+m`(?<=^(?<-2>.)*(..).*?#(.)*.)\d!(.)(.*\1:)(.)(\d*)
$5$3!$4$6$5
)`!0
0
 .+
<empty>

Di mana <empty>menunjukkan bahwa ada garis kosong tertinggal. Setiap baris masuk dalam file terpisah dan #harus diganti dengan baris baris (0x0A).

Mengharapkan masukan untuk menjadi ndi unary (terbuat dari nol, seperti di Unary ), diikuti dengan spasi, diikuti oleh "pseudo-acak" string, misalnya 10, [1, 0, 0, 1]akan dibaca sebagai

0000000000 1001

Output seperti dalam tantangan, tetapi diisi dengan nol, misalnya

1000000000
1100000000
1110000000
1001000000
1101100000
1111110000
1001101000
1101011100
1111111010
1011001111

Ini jauh lebih sulit daripada yang saya harapkan ...

Python, 142 135 132 131 byte

133 132 131 byte versi

f=input;n=f();L=f()*n*n;r=[1];i=1
while i<=n:print r;r=[L.pop(0)if r[x-1]&r[x]else r[x-1]+r[x]for x in range(1,i)];r=[1]+r+[1];i+=1

digantikan r[x-1]+r[x]>1oleh r[x-1]&r[x]adalah operator bitwise & menghasilkan nilai minimum dalam(r[x-1],r[x])

Terima kasih @ThomasKwa untuk menyarankan n*nalih-alih n**2yang menghemat 1 byte!

Terima kasih @ Shebang untuk -1 byte

Versi 135 byte

f=input;n=f();L=f()*n**2;r=[1];i=1
while i<=n:print r;r=[L.pop(0)if r[x-1]+r[x]>1 else r[x-1]+r[x]for x in range(1,i)];r=[1]+r+[1];i+=1

Berkat @Cole untuk -7 byte:

min(r[x-1],r[x])->r[x-1]+r[x]>1

max(r[x-1],r[x])->r[x-1]+r[x]

Versi 142 byte

f=input;n=f();L=f()*n**2;r=[1];i=1
while i<=n:print r;r=[L.pop(0)if min(r[x-1],r[x])else max(r[x-1],r[x])for x in range(1,i)];r=[1]+r+[1];i+=1

Bahkan tidak dekat dengan jawaban @ Jakube tapi saya punya banyak kode menyenangkan dan golf yang satu ini

Mengharapkan dua input: input pertama adalah jumlah baris dan input kedua adalah daftar sumber pseudorandomness . Ini mencetak pada konsol satu demi satu baris, masing-masing pada baris baru.

Sebagai contoh:

10 # This is input
[0] # This is input
[1] <- First output row
[1, 1]
[1, 0, 1]
[1, 1, 1, 1]
[1, 0, 0, 0, 1]
[1, 1, 0, 0, 1, 1]
[1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 1, 0, 0, 0, 0, 0, 0, 1, 1]

Sekarang untuk penjelasan singkat tentang cara kerjanya:

f=input;n=f();L=f()*n*n;r=[1];i=1 First we define the input() function as f 
                                   for saving bytes as we have to call it twice.
                                   Then L is defined as a list made of the 
                                   pseudorandom numbers in their order *many* times 
                                   (were *many* is an upperbound of the canges that 
                                   could be done); r as the first row and i as the row 
                                   counter.

while i<=n:print r                 A while loop that exits when the nth row has been 
                                   calculated and the printing of the actual row.

r=[L.pop(0)if r[x-1]&r[x] else r[x-1]+r[x] for x in range(1,i)];r=[1]+r+[1];i+=1
     ^           ^                 ^                         ^
     |           |                 |Same as max(r[x-1],r[x]) | from 2nd to last element
     |           | Same as min(r[x-1],r[x]) (0->False;1->True)                
     | get random bit from pseudorandom list    

Kuncinya di sini adalah bahwa kita tahu bahwa daftar bit akan selalu dimulai dan diakhiri dengan 1karena elemen pertama dan terakhir tidak pernah dimodifikasi karena spesifikasi. dari pertanyaan. Itulah alasan pernyataan itu [1]+r+[1].

Tetapi jika rdiinisialisasi sebagai [1], tidak ada perubahan pada baris pertama dan kemudian kita tambahkan [1]+r+[1]kenapa baris kedua tidak [1,1,1]?

Hal ini disebabkan oleh fakta bahwa pada iterasi pertama i=1begitu range(1,i)mengembalikan daftar kosong dan, sebagai akibat dari forpemahaman daftar tidak memiliki apa-apa untuk beralih rmenjadi daftar kosong begitu [1]+r+[1]=[1,1]. Ini hanya terjadi pada iterasi pertama yang ideal bagi kami!

PS: Jangan ragu untuk membuat saran tentang cara golf lebih banyak.

MATLAB, 146 143 138

(Juga berfungsi pada Oktaf online, tetapi Anda harus masuk untuk menyimpan fungsi dalam file).

function o=c(n,L);o=zeros(n);o(:,1)=1;for i=2:n;for j=2:i;a=o(i-1,j-1);b=o(i-1,j);c=a|b;d=a&b;c(d)=L(d);L=circshift(L,-d);o(i,j)=c;end;end

Fungsi mengambil input ndan L, dan mengembalikan array oyang berisi output.

Untuk nilai input, nadalah skalar, dan Lmerupakan vektor kolom, yang dapat ditentukan dalam format [;;;]. Tidak cukup dengan apa yang Anda perlihatkan, tetapi Anda mengatakan itu fleksibel karena alasan dan sepertinya demikian.

Output diformat sebagai n x narray yang berisi 0 dan 1.

Dan sebuah penjelasan:

function o=c(n,L)
%Create the initial array - an n x n square with the first column made of 1's
o=zeros(n);o(:,1)=1;
%For each row (starting with the second, as the first is done already)
for i=2:n;
    %For each column in that row, again starting with the second as the first is done
    for j=2:i;
        %Extract the current and previous elements in the row above
        a=o(i-1,j-1); %(previous)
        b=o(i-1,j);   %(current)
        %Assume that min()==0, so set c to max();
        c=a|b;
        %Now check if min()==1
        d=a&b;
        %If so, set c to L(1)
        c(d)=L(d);
        %Rotate L around only if min()==1
        L=circshift(L,-d);
        %And store c back to the output matrix
        o(i,j)=c;
    end;
end

Pembaruan: Saya telah berhasil mengoptimalkan pernyataan if-else untuk menghemat beberapa byte. Format input sekali lagi diubah kembali ke vektor kolom.

Haskell, 153 149 byte

j[_]o l=(l,o)
j(a:u@(b:c))o q@(l:m)|a*b==0=j u(o++[a+b])q|1<2=j u(o++[l])m
k(r,a)=fmap((1:).(++[1]))$j a[]r
n%l=map snd$take n$iterate k(cycle l,[1])

%mengembalikan daftar daftar bit. Contoh penggunaan:

> 10 % [1,0,0,1] 
[[1],[1,1],[1,1,1],[1,0,0,1],[1,1,0,1,1],[1,1,1,1,1,1],[1,0,0,1,1,0,1],[1,1,0,1,0,1,1,1],[1,1,1,1,1,1,1,0,1],[1,0,1,1,0,0,1,1,1,1]]

Oh sayang! Membawa daftar acak di Lsekitar adalah rasa sakit murni. Mari kita lihat apakah ini bisa lebih pendek.

C #, 152 byte

Tidak ada yang istimewa di sini. Fungsi mengembalikan array 2D di mana peringkat pertama adalah baris dan yang kedua adalah kolom.

Diindentifikasi dan baris baru untuk kejelasan:

int[,]F(int n,int[]l){
    var o=new int[n,n];
    for(int y=0,x,i=0,m;y<n;y++)
        for(o[y,x=0]=1;x++<y;)
            o[y,x]=(m=o[y-1,x-1]+o[y-1,x])<2?m:l[i++%l.Length];
    return o;
}

TI-BASIC, 106 94 87 86 87 byte

Prompt N,B
"∟B(1+remainder(𝑛,dim(∟B→u
{1
For(I,1,N
Disp Ans
augment({0},Ans)+augment(Ans,{0
Ans and Ans≠2+seq(u(𝑛-(Ans(X)<2)+2dim(∟B)),X,1,dim(Ans
End

TI-BASIC tidak memiliki operator tambahan, bukan? Yah, itu semacam itu. Variabel persamaan u, biasanya digunakan dengan urutan, memiliki fitur yang tidak jelas: ketika udipanggil dengan argumen, variabel 𝑛diatur ke yang lebih besar dari argumen itu. Peningkatan bersyarat tergantung pada ini. (Saya sudah menunggu untuk menggunakannya dalam waktu yang lama.)

Agar pengindeksan daftar berfungsi dengan baik, 𝑛harus berupa nilai default 0, dan 𝑛Minharus merupakan default 1, jadi hapus RAM kalkulator Anda atau tetapkan nilai-nilai itu secara manual sebelum menjalankan ini.

augment({0},Ans)+augment(Ans,{0menghitung daftar jumlah dua elemen yang berdekatan, sehingga akan mengembalikan daftar 0s, 1s, dan 2s. Maka keajaiban ada di baris ini:

Ans and Ans≠2+seq(u(𝑛-(Ans(X)≠2)+dim(∟B)),X,1,dim(Ans

Ans and                 ;set 0s to 0
Ans≠                    ;set to 0 all sums that equal...
2+
  seq(...,X,1,dim(Ans   ;execute for each element of the list
      u(                ;return this element in list of bits (looping)        
        𝑛               ;current location in the list
        -(Ans(X)≠2)+    ;subtract 1 if the element isn't 2
        2dim(∟B)        ;Add twice the dimension of the list
                           ;(because n<nMin on the first iteration, it's out of the domain
                           ;this prevents an error)
       )                      ;set n to one greater than that value
                              ;i.e. increment if element≠2
                        ;Will equal Ans(X) iff Ans(X)=2 and the bit read false

Hasil dari baris ini adalah bahwa elemen daftar adalah 0 jika mereka adalah 0 atau jika mereka adalah 2 dan bit yang dibaca adalah 0.

Result of above line
n \ u |  0  |  1
0        0     0

Kasus cobaan:

N=?7
B=?{0,1,0
             {1}
           {1 1}
         {1 0 1}
       {1 1 1 1}
     {1 1 0 0 1}
   {1 1 1 0 1 1}
 {1 0 0 1 1 1 1}
            Done