Fondo

Sí, la física de las cadenas de bits es algo real . La idea es construir una nueva teoría de la física utilizando solo cadenas de bits que evolucionen bajo una regla probabilística ... o algo así. A pesar de leer un par de artículos al respecto, todavía estoy bastante confundido. Sin embargo, el universo de la cadena de bits lo convierte en un bonito código de golf.

Programa Universo

La física de Bitstring tiene lugar en el llamado universo de programas . En cada paso de la evolución del universo, hay una lista finita Lde cadenas de bits de cierta longitud k, comenzando con la lista de dos elementos [10,11]donde k = 2. Un paso de tiempo se procesa de la siguiente manera (en pseudocódigo similar a 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

Todas las elecciones aleatorias son uniformemente aleatorias e independientes entre sí.

Ejemplo

Un ejemplo de evolución de 4 pasos podría ser el siguiente. Comience con la lista inicial L:

10
11

Elegimos aleatoriamente A := 10y B := 10, que son la misma fila, lo que significa que necesitamos extender cada cadena Lcon un bit aleatorio:

101
110

A continuación, elegimos A := 101y B := 110, y dado que no son iguales, agregamos su XOR a L:

101
110
011

Luego, elegimos A := 011y B := 110, y nuevamente agregamos su XOR:

101
110
011
101

Finalmente, elegimos A := 101(última fila) y B := 101(primera fila), que son iguales, por lo que ampliamos con bits aleatorios:

1010
1100
0111
1010

La tarea

Su tarea es tomar un número entero no negativo tcomo entrada, simular el universo del programa para tpasos de tiempo y devolver o imprimir la lista resultante L. Tenga t = 0en cuenta que los resultados en la lista inicial [10,11]. Puede generar Luna lista de listas de enteros, una lista de listas de valores booleanos o una lista de cadenas; si la salida va a STDOUT, también puede imprimir las cadenas de bits una por línea en algún formato razonable. El orden de las cadenas de bits es significativo; en particular, la lista inicial no puede ser [11,10], [01,11]ni nada de eso. Ambas funciones y programas completos son aceptables, las lagunas estándar no están permitidas y gana el conteo de bytes más bajo.

Pyth, 27 26 bytes

u?+RO2GqFKmOG2aGxVFKQ*]1U2

Pruébelo en línea: demostración

Explicación:

                              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 guardado por Sp3000.

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

Explicación

Cree el estado inicial como un número base-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]]

Y luego realice el bucle principal e imprima el resultado al final:

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.

Pruébalo aquí.

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)

Nada inteligente Crea una función sin nombre que acepta un entero como entrada y devuelve una matriz de matrices. Para llamarlo, dale un nombre, por ejemplo f=t->....

Ungolfed + explicación:

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

Ejemplos:

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]

¡Guardado 12 bytes gracias a ML!

Pitón 2, 141

Probé algunos métodos diferentes, pero lo mejor que pude obtener fue relativamente sencillo. Gracias a @ Sp3000 por 15 caracteres más o menos (y por enseñarme sobre la existencia de 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

Pitón 2, 127 122

Suponiendo que las cadenas de bits de Python del formulario, '0b1'etc. estén bien:

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)

Aquí solo un ligero matiz es el uso del hecho de que XOR (A, B) = 0 si A = B.

Gracias a @ Sp300 por acortar el forcircuito de cierre

Pyth, 34

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

Utiliza reducir para aplicar cada iteración. Te lo explicaré cuando termine de jugar golf.

Pruébalo aquí

K, 46 53 46 bytes

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

Una buena parte del tamaño (aproximadamente 7 bytes) de esto se debe al hecho de que K no tiene xoroperador, por lo que tuve que implementar uno yo mismo. Originalmente, usé una lista de cadenas, seguido de darme cuenta de que era increíblemente estúpido. ¡Así que ahora corté los 7 bytes nuevamente!

Antes de:

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

@JohnE señaló en los comentarios que se suponía que el estado inicial estaba codificado, lo que costó 7 bytes adicionales. : /

JavaScript ( ES6 ) 152

Una función, que utiliza cadenas (con números debería ser más corta, pero en JavaScript las operaciones de bits están limitadas a enteros de 32 bits).

Prueba en Firefox usando el fragmento a continuación.

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}

La estructura de mi respuesta es bastante similar a la de @ kirbyfan64sos, pero en lugar de cadenas utilicé vectores 1/0 y evito la necesidad de un condicional ( :[ ; ; ]) al indexar en una lista.

Algunas carreras:

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

Editar:

Guardado cuatro bytes con una forma más compacta de construir el universo inicial:

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

Edit2:

Olvidé que "elegir" puede tomar una lista como argumento correcto:

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

Entonces puedo simplificar parte de esto. Crédito donde corresponde, Kirby consiguió este truco antes que yo.

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

Javascript, 241 233 bytes

Eso es un poco largo.

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

Lamento mucho que esto no sea competitivo, pero para ser sincero, no pensé que podría hacer que esto funcione y tuve que publicarlo una vez que lo hice. Intenté jugar al golf un poco :)

Para manejar las conversiones binarias / enteras, tuve que crear un par de funciones escalares (513 de los bytes). Ava de entero a una cadena de bits. Bhace lo contrario

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

Luego está el procedimiento. @Ces la cantidad de pasos

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 @

Diez mil iteraciones tomaron alrededor de 2 minutos y devolvieron 9991 filas

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

Pyth - 37 bytes

Obviamente, solo sigue el psuedocode. Probablemente pueda jugar mucho al golf.

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

Pruébalo aquí en línea .

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"

Trate de mí .

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

Nada mágico aquí. Ingrese el valor para ten la consola R y ejecute el script. Es difícil "jugar" el código R pero aquí hay una versión más legible:

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

Rubí, 82

Bastante sencillo. En comparación con otros idiomas que no son de golf, Ruby parece tener un buen desempeño con su gran biblioteca estándar.

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

Salida de muestra para 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]