Latar Belakang

Ya, fisika bitstring adalah hal yang nyata . Idenya adalah untuk membangun teori fisika baru menggunakan hanya serangkaian bit yang berevolusi di bawah aturan probabilistik ... atau sesuatu. Meskipun membaca beberapa makalah tentang itu, saya masih cukup bingung. Namun, alam semesta bitstring membuat kode golf kecil yang menyenangkan.

Program Universe

Fisika Bitstring terjadi di alam semesta yang disebut program . Pada setiap langkah evolusi alam semesta, ada daftar Lbitstring yang terbatas dengan panjang tertentu k, dimulai dengan daftar dua elemen di [10,11]mana k = 2. Satu timestep diproses sebagai berikut (dalam pseudocode mirip-Python).

A := random element of L
B := random element of L
if A == B:
    for each C in L:
        append a random bit to C
else:
    append the bitwise XOR of A and B to L

Semua pilihan acak adalah acak seragam dan tidak tergantung satu sama lain.

Contoh

Contoh evolusi 4 langkah mungkin terlihat seperti berikut. Mulai dengan daftar awal L:

10
11

Kami memilih secara acak A := 10 dan B := 10, yang merupakan baris yang sama, yang berarti kita perlu memperluas setiap string Ldengan bit acak:

101
110

Selanjutnya, kita pilih A := 101 dan B := 110, dan karena mereka tidak sama, kami menambahkan XOR mereka ke L:

101
110
011

Kemudian, kita memilih A := 011dan B := 110, dan menambahkan XOR mereka lagi:

101
110
011
101

Akhirnya, kami memilih A := 101 (baris terakhir) dan B := 101(baris pertama), yang sama, jadi kami memperluas dengan bit acak:

1010
1100
0111
1010

Tugas

Tugas Anda adalah mengambil integer nonnegatif tsebagai input, mensimulasikan semesta program untuk ttimesteps, dan mengembalikan atau mencetak daftar yang dihasilkan L. Perhatikan bahwa t = 0hasil dalam daftar awal [10,11]. Anda dapat menampilkan Lsebagai daftar daftar bilangan bulat, daftar daftar nilai boolean atau daftar string; jika output beralih ke STDOUT, Anda juga dapat mencetak bitstrings satu per baris dalam beberapa format yang masuk akal. Urutan bitstring signifikan; khususnya, daftar awal tidak boleh [11,10],[01,11] atau semacamnya. Baik fungsi dan program penuh dapat diterima, celah standar tidak diizinkan, dan jumlah byte terendah menang.

Pyth, 27 26 byte

u?+RO2GqFKmOG2aGxVFKQ*]1U2

Cobalah online: Demonstrasi

Penjelasan:

                              implicit: Q = input number
                     *]1U2    the initial list [[1,0], [1,1]]
u                   Q         reduce, apply the following expression Q times to G = ^
          mOG2                  take two random elements of G
         K                      store in K
       qF                       check if they are equal
 ?                              if they are equal:
  +RO2G                           append randomly a 0 or 1 to each element of G
                                else:
              aG                  append to G
                xVFK              the xor of the elements in K

CJam, 42 40 38 37 byte

1 byte disimpan oleh Sp3000.

B2b2/q~{:L_]:mR_~#L@~.^a+L{2mr+}%?}*p

Penjelasan

Buat status awal sebagai nomor basis-2:

B2b e# Push the the binary representation of 11: [1 0 1 1]
2/  e# Split into chunks of 2 to get [[1 0] [1 1]]

Dan kemudian lakukan loop utama dan cukup cetak hasilnya di akhir:

q~       e# Read and eval input t.
{        e# Run this block t times.
  :L     e#   Store the current universe in L.
  _]     e#   Copy it and wrap both copies in an array.
  :mR    e#   Pick a random element from each copy.
  _~     e#   Duplicate those two elements, and unwrap them.
  #      e#   Find the second element in the first. If they are equal, it will be found at
         e#   index 0, being falsy. If they are unequal, it will not be found, giving
         e#   -1, which is truthy.

         e#   We'll now compute both possible universes for the next step and then select
         e#   the right one based on this index. First, we'll build the one where they were
         e#   not equal.

  L@~    e#   Push L, pull up the other copy of the selected elements and unwrap it.
  .^     e#   Take the bitwise XOR.
  a+     e#   Append this element to L.

  L      e#   Push L again.
  {      e#   Map this block onto the elements in L.
    2mr+ e#     Append 0 or 1 at random. 
  }%     
  ?      e#   Select the correct follow-up universe.
}*
p        e# Pretty-print the final universe.

Uji di sini.

Julia, 141 129 byte

t->(L=Any[[1,0],[1,1]];for i=1:t r=1:length(L);A=L[rand(r)];B=L[rand(r)];A==B?for j=r L[j]=[L[j],rand(0:1)]end:push!(L,A$B)end;L)

Tidak ada yang pintar. Membuat fungsi tanpa nama yang menerima integer sebagai input dan mengembalikan array array. Untuk menyebutnya, berikan nama, misf=t->... .

Penjelasan + tidak dikumpulkan:

function f(t)
    # Start with L0
    L = Any[[1,0], [1,1]]

    # Repeat for t steps
    for i = 1:t
        # Store the range of the indices of L
        r = 1:length(L)

        # Select 2 random elements
        A = L[rand(r)]
        B = L[rand(r)]

        if A == B
            # Append a random bit to each element of L
            for j = r
                L[j] = [L[j], rand(0:1)]
            end
        else
            # Append the XOR of A and B to L
            push!(L, A $ B)
        end
    end

    # Return the updated list
    L
end

Contoh:

julia> f(4)
4-element Array{Any,1}:
 [1,0,1,0]
 [1,1,1,1]
 [0,1,1,0]
 [0,1,0,0]

julia> f(3)
3-element Array{Any,1}:
 [1,0,1,1]
 [1,1,1,0]
 [0,1,0,1]

Disimpan 12 byte berkat ML!

Python 2, 141

Saya mencoba beberapa metode berbeda, tetapi yang terbaik yang bisa saya dapatkan relatif mudah. Terima kasih kepada @ Sp3000 untuk 15 karakter atau lebih (dan telah mengajari saya tentang keberadaan int.__xor__).

from random import*
L=[[1,0],[1,1]];C=choice
exec"A=C(L);B=C(L);L=[L+[map(int.__xor__,A,B)],[x+[C([1,0])]for x in L]][A==B];"*input()
print L

Python 2, 127 122

Dengan asumsi string bit python dari bentuk '0b1'dll OK:

from random import*
C=choice
L=[2,3]
exec"x=C(L)^C(L);L=L+[x]if x else[a*2+C([0,1])for a in L];"*input()
print map(bin,L)

Hanya nuansa ringan di sini adalah penggunaan fakta bahwa XOR (A, B) = 0 iff A = B.

Terima kasih kepada @ Sp300 untuk memperpendek forloop penutup

Pyth, 34

u?+RO`TGqJOGKOG+Gsm`s!dqVJKQ[`T`11

Penggunaan dikurangi untuk menerapkan setiap iterasi. Saya akan menjelaskan ketika saya selesai bermain golf.

Coba di sini

K, 46 53 46 byte

{x{:[~/t:2?x;{x,*1?2}'x;x,,,/~=/t]}/(1 0;1 1)}

Potongan yang baik dari ukuran (sekitar 7 byte) dari ini adalah untuk fakta bahwa K tidak memiliki xoroperator, jadi saya harus mengimplementasikannya sendiri. Awalnya, saya menggunakan daftar string, diikuti dengan menyadari bahwa itu sangat bodoh. Jadi sekarang saya memotong 7 byte lagi!

Sebelum:

{x{:[~/t:2?x;{x,*$1?2}'x;x,,,/$~=/(0$')'t]}/$:'10 11}

@ JohnE menunjukkan dalam komentar bahwa keadaan awal seharusnya hardcoded, yang biaya 7 byte tambahan. : /

JavaScript ( ES6 ) 152

Sebuah fungsi, menggunakan string (dengan angka harus lebih pendek, tetapi dalam operasi bit javascript terbatas pada integer 32 bit).

Uji di Firefox menggunakan cuplikan di bawah ini.

F=(t,L=['10','11'],l=2,R=n=>Math.random()*n|0,a=L[R(l)],b=L[R(l)])=>
   t--?a==b
     ?F(t,L.map(x=>x+R(2)),l)
     :F(t,L,L.push([...a].map((x,p)=>x^b[p]).join('')))
  :L
  
test=_=>O.innerHTML=F(+I.value).join('\n')

#I{width:3em}

<input id=I value=10><button onclick=test()>-></button><pre id=O></pre>

K, 45 41 38 byte

{x{(x,,~=/t;{x,1?2}'x)@~/t:2?x}/1,'!2}

Struktur jawaban saya sangat mirip dengan @ kirbyfan64sos, tetapi alih-alih string saya menggunakan vektor 1/0 dan saya menghindari kebutuhan untuk conditional (:[ ; ; ] ) dengan cara mengindeks ke dalam daftar.

Beberapa langkah:

  {x{(x,,~=/t;{x,1?2}'x)@~/t:2?x}/1,'!2}3
(1 0 0 0
 1 1 1 1
 0 1 1 1)

  {x{(x,,~=/t;{x,1?2}'x)@~/t:2?x}/1,'!2}3
(1 0 0
 1 1 0
 0 1 0
 1 0 0)

  {x{(x,,~=/t;{x,1?2}'x)@~/t:2?x}/1,'!2}3
(1 0 0
 1 1 0
 0 1 0
 1 1 0)

Edit:

Disimpan empat byte dengan cara yang lebih ringkas untuk membangun alam semesta awal:

1,'!2     / new
(1 0;1 1) / old

Sunting2:

Saya lupa bahwa "pilih" dapat mengambil daftar sebagai argumen yang benar:

  2?"abcd"
"dc"
  2?"abcd"
"cc"
  2?"abcd"
"ca"

Jadi saya bisa menyederhanakan bagian dari ini. Kredit di mana sudah jatuh tempo, Kirby punya trik ini sebelum saya melakukannya.

2?x    / new
x@2?#x / old

Javascript, 241 233 byte

Itu agak lama.

a=[[1,0],[1,1]];for(b=prompt();b--;)if(c=a.length,d=a[c*Math.random()|0],e=a[c*Math.random()|0],d+""==e+"")for(f=0;f<c;f++)a[f].push(2*Math.random()|0);else{g=[];for(h=0;h<d.length;h++)g.push(d[h]^e[h]);a.push(g)}alert(a.join("\n"));

T-SQL (2012+), 1019

Saya benar-benar menyesal ini tidak kompetitif, tetapi jujur ​​saya tidak berpikir saya bisa mendapatkan ini untuk bekerja dan harus mempostingnya begitu saya lakukan. Saya memang mencoba golf sedikit :)

Untuk menangani konversi biner / integer, saya harus membuat beberapa fungsi skalar (513 byte). Aberalih dari integer ke string bit. Bmelakukan yang sebaliknya.

CREATE FUNCTION A(@ BIGINT)RETURNS VARCHAR(MAX)AS
BEGIN
DECLARE @S VARCHAR(MAX);
WITH R AS(SELECT @/2D,CAST(@%2 AS VARCHAR(MAX))M
UNION ALL
SELECT D/2,CAST(D%2 AS VARCHAR(MAX))+M
FROM R
WHERE D>0)SELECT @S=M FROM R WHERE D=0
RETURN @S
END
CREATE FUNCTION B(@ VARCHAR(MAX))RETURNS BIGINT AS
BEGIN
DECLARE @I BIGINT;
WITH R AS(SELECT CAST(RIGHT(@,1)AS BIGINT)I,1N,LEFT(@,LEN(@)-1)S
UNION ALL 
SELECT CAST(RIGHT(S,1)AS BIGINT)*POWER(2,N),N+1,LEFT(S,LEN(S)-1)
FROM R
WHERE S<>''
)SELECT @I=SUM(I)FROM R
RETURN @I
END

Lalu ada prosedurnya. @Cadalah jumlah langkah

DECLARE @C INT=9
DECLARE @ TABLE(S VARCHAR(MAX))
DECLARE @R VARCHAR(MAX)
INSERT @ VALUES('10'),('11')
WHILE(@C>=0)
BEGIN
SET @C-=1
SELECT @R=CASE WHEN MAX(S)=MIN(S)THEN''ELSE RIGHT(REPLICATE('0',99)+dbo.A(dbo.B(MAX(S))^dbo.B(MIN(S))),LEN(MAX(S)))END
FROM(SELECT TOP 2S,ROW_NUMBER()OVER(ORDER BY(SELECT\))N FROM @,(VALUES(1),(1),(1))D(D)ORDER BY RAND(CAST(NEWID()AS VARBINARY(50))))A
IF @R=''UPDATE @ SET S=CONCAT(S,ROUND(RAND(CAST(NEWID() AS VARBINARY(50))),0))
ELSE INSERT @ VALUES(@R)
END
SELECT * FROM @

Sepuluh ribu iterasi memakan waktu sekitar 2 menit dan mengembalikan 9991 baris

1001001100110
1101001001110
0111100100101
1111100001011
1111001010011
0110101001101
...
1110101000100
1111011101100
1100001100010
0110010001001
1110100010100

Pyth - 37 byte

Jelas, cukup ikuti psuedocode. Mungkin bisa banyak golf.

KPP^,1Z2VQ=K?m+dO1KqFJ,OKOKaKxVhJeJ;K

Coba di sini online .

Mathematica, 106 byte

Nest[If[Equal@@#,Map[#~Append~RandomInteger[]&],Append[BitXor@@#]]&[#~RandomChoice~2]@#&,{{1,0},{1,1}},#]&

Perl, 102

#!perl -p
@l=qw(10 11);$_=$l[rand@l]^$l[rand@l],$_|=y//0/cr,@l=/1/?(@l,$_):map{$_.~~rand 2}@l for 1..$_;$_="@l"

Coba saya .

R, 186

L=list(0:1,c(1,1))
if(t>0)for(t in 1:t){A=sample(L,1)[[1]]
B=sample(L,1)[[1]]
if(all(A==B)){L=lapply(L,append,sample(0:1, 1))}else{L=c(L,list(as.numeric(xor(A,B))))}}
L

Tidak ada yang ajaib di sini. Masukkan nilai untuk tdi konsol R dan jalankan skrip. Sulit untuk "bermain golf" dengan kode R tetapi ini versi yang lebih mudah dibaca:

L <- list(0:1, c(1, 1))
if(t > 0) {
  for(t in 1:t) {
    A <- sample(L, 1)[[1]]
    B <- sample(L, 1)[[1]]
    if (all(A == B)) {
      L <- lapply(L, append, sample(0:1, 1))
    } else {
      L <- c(L,list(as.numeric(xor(A, B))))
    }
  }
}
L

Ruby, 82

Cukup mudah. Dibandingkan dengan bahasa non-golf lainnya, ruby ​​tampaknya cocok dengan perpustakaan standarnya yang besar.

->t{l=[2,3]
t.times{a,b=l.sample 2
a.equal?(b)?l.map!{|x|x*2+rand(2)}:l<<(a^b)}
l}

Output sampel untuk t = 101010:

[9, 15, 6, 13, 5, 12, 10, 11, 5, 4, 15, 13, 2, 7, 11, 9, 3, 3, 8, 6, 3, 13, 13, 12, 10, 9, 2, 4, 14, 9, 9, 14, 15, 7, 10, 4, 10, 14, 13, 7, 15, 7]