Hintergrund

Ja, Bitstring-Physik ist eine echte Sache . Die Idee ist, eine neue Theorie der Physik zu konstruieren, die nur Bitketten verwendet, die sich unter einer Wahrscheinlichkeitsregel entwickeln ... oder so. Obwohl ich ein paar Artikel darüber gelesen habe, bin ich immer noch ziemlich verwirrt. Das Bitstring-Universum ist jedoch ein schönes kleines Codegolf.

Programmuniversum

Die Bitstring-Physik findet in einem sogenannten Programmuniversum statt . Bei jedem Schritt der Entwicklung des Universums gibt es eine endliche Liste Lvon Bitfolgen mit einer gewissen Länge k, beginnend mit der Zwei-Elemente-Liste, [10,11]in der k = 2. Ein Zeitschritt wird wie folgt verarbeitet (im Python-ähnlichen Pseudocode).

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

Alle Zufallsentscheidungen sind einheitlich zufällig und voneinander unabhängig.

Beispiel

Eine beispielhafte Entwicklung von 4 Schritten könnte wie folgt aussehen. Beginnen Sie mit der Anfangsliste L:

10
11

Wir wählen zufällig A := 10und B := 10, welche die gleiche Zeile sind, was bedeutet, dass wir jeden String Lmit einem zufälligen Bit erweitern müssen:

101
110

Als nächstes wählen wir A := 101und B := 110, und da sie nicht gleich sind, fügen wir ihre XOR hinzu zu L:

101
110
011

Dann wählen wir A := 011und B := 110und hängen wieder ihre XOR an:

101
110
011
101

Schließlich wählen wir A := 101(letzte Reihe) und B := 101(erste Reihe), die gleich sind, also erweitern wir mit zufälligen Bits:

1010
1100
0111
1010

Die Aufgabe

Ihre Aufgabe ist es, eine nichtnegative Ganzzahl tals Eingabe zu verwenden, das Programmuniversum für tZeitschritte zu simulieren und die resultierende Liste zurückzugeben oder auszudrucken L. Beachten Sie, dass t = 0sich die ursprüngliche Liste ergibt [10,11]. Sie können Leine Liste mit ganzen Zahlen, Listen mit booleschen Werten oder eine Liste mit Zeichenfolgen ausgeben . Wenn die Ausgabe an STDOUT geht, können Sie die Bitstrings auch einzeln pro Zeile in einem angemessenen Format drucken. Die Reihenfolge der Bitfolgen ist signifikant; insbesondere kann die erste Liste nicht sein [11,10], [01,11]oder so etwas. Sowohl Funktionen als auch vollständige Programme sind akzeptabel, Standardlücken sind nicht zulässig, und die niedrigste Bytezahl gewinnt.

Pyth, 27 26 Bytes

u?+RO2GqFKmOG2aGxVFKQ*]1U2

Probieren Sie es online aus: Demonstration

Erläuterung:

                              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 Bytes

1 Byte von Sp3000 gespeichert.

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

Erläuterung

Erstellen Sie den Anfangszustand als Basis-2-Zahl:

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]]

Führen Sie dann die Hauptschleife aus und drucken Sie das Ergebnis am Ende hübsch aus:

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.

Teste es hier.

Julia, 141 129 Bytes

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)

Nichts Schlaues. Erstellt eine unbenannte Funktion, die eine Ganzzahl als Eingabe akzeptiert und ein Array von Arrays zurückgibt. Um es zu nennen, geben Sie ihm einen Namen, z f=t->....

Ungolfed + Erklärung:

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

Beispiele:

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]

12 Bytes gespart dank ML!

Python 2, 141

Ich habe ein paar verschiedene Methoden ausprobiert, aber das Beste, was ich bekommen konnte, war relativ unkompliziert. Vielen Dank an @ Sp3000 für ungefähr 15 Zeichen (und dafür, dass Sie mir die Existenz von beigebracht haben 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

Vorausgesetzt, Python-Bit-Strings des Formulars '0b1'usw. sind in Ordnung:

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)

Die Tatsache, dass XOR (A, B) = 0 ist, wenn A = B, wird hier nur in einer milden Nuance verwendet.

Dank @ SP300 zur Verkürzung der umschließenden forSchleife

Pyth, 34

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

Die Verwendung wird reduziert, um jede Iteration anzuwenden. Ich erkläre, wenn ich mit dem Golfen fertig bin.

Probieren Sie es hier aus

K, 46 53 46 Bytes

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

Ein guter Teil der Größe (ungefähr 7 Bytes) davon hat damit zu tun, dass K keinen xorOperator hat, also musste ich selbst einen implementieren. Ursprünglich habe ich eine Liste von Zeichenfolgen verwendet, gefolgt von der Erkenntnis, dass das wahnsinnig dumm war. Also habe ich jetzt die 7 Bytes wieder abgeschnitten!

Vor:

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

@JohnE wies in den Kommentaren darauf hin, dass der Anfangszustand fest codiert werden sollte, was 7 zusätzliche Bytes kostete. : /

JavaScript ( ES6 ) 152

Eine Funktion, die Zeichenfolgen verwendet (bei Zahlen sollte sie kürzer sein, bei Javascript sind die Bitoperationen jedoch auf 32-Bit-Ganzzahlen beschränkt).

Testen Sie in Firefox mit dem folgenden Snippet.

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 Bytes

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

Die Struktur meiner Antwort ist der von @ kirbyfan64sos ziemlich ähnlich, aber anstelle von Strings habe ich 1/0 Vektoren verwendet und ich vermeide die Notwendigkeit eines conditional ( :[ ; ; ]), indem ich stattdessen in eine Liste indexiere .

Ein paar Läufe:

  {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)

Bearbeiten:

Vier Bytes mit einer kompakteren Methode zum Erstellen des anfänglichen Universums gespart:

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

Edit2:

Ich habe vergessen, dass "select" eine Liste als richtiges Argument verwenden kann:

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

So kann ich einen Teil davon vereinfachen. Gut, wo es fällig ist, hat Kirby diesen Trick vor mir bekommen.

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

Javascript, 241 233 Bytes

Das ist ziemlich lang.

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

Es tut mir wirklich leid, dass dies bei weitem nicht wettbewerbsfähig ist, aber um ehrlich zu sein, ich hätte nicht gedacht, dass ich das zum Laufen bringen könnte, und musste es veröffentlichen, sobald ich es getan habe. Ich habe versucht, ein bisschen Golf zu spielen :)

Um die Binär / Ganzzahl-Konvertierungen zu handhaben, musste ich ein paar Skalarfunktionen erstellen (513 der Bytes). AGeht von Integer zu einer Bitfolge. Bmacht das Gegenteil.

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

Dann gibt es das Verfahren. @Cist die Anzahl der Schritte

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 @

Zehntausend Iterationen dauerten ungefähr 2 Minuten und ergaben 9991 Zeilen

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

Pyth - 37 Bytes

Offensichtlich folgt nur psuedocode. Kann wahrscheinlich viel Golf spielen.

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

Probieren Sie es hier online .

Mathematica, 106 Bytes

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"

Versuch es mit mir .

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

Nichts magisches hier. Geben Sie den Wert für tin die R-Konsole ein und führen Sie das Skript aus. Es ist schwer, R-Code zu "golfen", aber hier ist eine besser lesbare Version:

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

Rubin, 82

Ziemlich direkt. Ruby scheint mit seiner großen Standardbibliothek im Vergleich zu anderen Nicht-Golf-Sprachen gut abzuschneiden.

->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}

Beispielausgabe für 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]