Bitstring Physics

21

Contexte

Oui, la physique des chaînes de bits est une chose réelle . L'idée est de construire une nouvelle théorie de la physique en utilisant uniquement des chaînes de bits qui évoluent sous une règle probabiliste ... ou quelque chose. Malgré la lecture de quelques articles à ce sujet, je suis toujours assez confus. Cependant, l'univers bitstring fait un joli petit golf de code.

Univers du programme

La physique des chaînes de bits se déroule dans un soi-disant univers de programme . À chaque étape de l'évolution de l'univers, il y a une liste finie Lde chaînes de bits d'une certaine longueur k, en commençant par la liste à deux éléments [10,11]k = 2. Un pas de temps est traité comme suit (en pseudocode de type 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

Tous les choix aléatoires sont uniformément aléatoires et indépendants les uns des autres.

Exemple

Un exemple d'évolution de 4 étapes pourrait ressembler à ce qui suit. Commencez avec la liste initiale L:

10
11

Nous choisissons au hasard A := 10et B := 10, qui sont la même ligne, ce qui signifie que nous devons étendre chaque chaîne Lavec un bit aléatoire:

101
110

Ensuite, nous choisissons A := 101et B := 110, et comme ils ne sont pas égaux, nous ajoutons leur XOR à L:

101
110
011

Ensuite, nous choisissons A := 011et B := 110, et ajoutons à nouveau leur XOR:

101
110
011
101

Enfin, nous choisissons A := 101(dernière ligne) et B := 101(première ligne), qui sont égaux, nous étendons donc avec des bits aléatoires:

1010
1100
0111
1010

La tâche

Votre tâche consiste à prendre un entier non négatif ten entrée, à simuler l'univers du programme pour les pas de ttemps et à retourner ou imprimer la liste résultante L. Notez que cela t = 0donne la liste initiale [10,11]. Vous pouvez produire Lune liste de listes d'entiers, une liste de listes de valeurs booléennes ou une liste de chaînes; si la sortie passe à STDOUT, vous pouvez également imprimer les chaînes de bits une par ligne dans un format raisonnable. L'ordre des chaînes de bits est significatif; en particulier, la liste initiale ne peut pas être [11,10], [01,11]ou quelque chose comme ça. Les fonctions et les programmes complets sont acceptables, les failles standard sont interdites et le nombre d'octets le plus bas l'emporte.

Zgarb
la source
Pouvons-nous limiter la longueur de la chaîne de bits (c'est-à-dire: puis-je utiliser des nombres et des opérations sur 32 bits)?
edc65
1
@ edc65 Non, la longueur des chaînes peut devenir arbitrairement élevée.
Zgarb
3
@ edc65 Le temps et la mémoire attendus pour obtenir plus de 32 bits sont astronomiques, mais c'est tout à fait approprié puisque nous simulons un univers. ;)
Zgarb
5
Cette physique des chaînes de bits est-elle une idée de crackpot? Je n'ai pas lu l'intégralité de l'article, mais l'expression Nous avons utilisé la physique des chaînes de bits pour fournir une théorie dans laquelle l'approximation hbar c / e2 = 22 - 1 + 23 - 1 + 27 - 1 = 137 a un sens en termes de un algorithme informatique et la théorie de l'information me semblent un peu ... numérologiques.
xebtl
1
@xebtl Cela me semble aussi fou. Je me souviens avoir lu une justification de l'algorithme quelque part, et cela ressemblait plus à une mauvaise pseudo-philosophie qu'à la physique. De plus, votre description de l'algorithme semble correspondre à ma version, peut-être que je vous comprends mal d'une manière ou d'une autre.
Zgarb

Réponses:

7

Pyth, 27 26 octets

u?+RO2GqFKmOG2aGxVFKQ*]1U2

Essayez-le en ligne: Démonstration

Explication:

                              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
Jakube
la source
xVFKest équivalent à xMK.
isaacg
@isaacg Non, xVFKéquivaut à xMCK, même nombre d'octets.
Jakube
11

CJam, 42 40 38 37 octets

1 octet enregistré par Sp3000.

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

Explication

Créez l'état initial sous forme de nombre en 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]]

Et puis effectuez la boucle principale et imprimez le résultat à la fin:

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.

Testez-le ici.

Martin Ender
la source
6

Julia, 141 129 octets

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)

Rien d'intelligent. Crée une fonction sans nom qui accepte un entier en entrée et renvoie un tableau de tableaux. Pour l'appeler, donnez-lui un nom, par exemple f=t->....

Non golfé + explication:

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

Exemples:

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]

Enregistré 12 octets grâce à ML!

Alex A.
la source
Vous pouvez le réduire à 133 caractères si vous utilisez l'opérateur ternay au lieu de if / else et si vous changez A=something;B=something else to A,B=something,something else:t->(L=Any[[1,0],[1,1]];for i=1:t r=1:length(L);A,B=L[rand(r)],L[rand(r)];A==B?(for j=r L[j]=[L[j],rand(0:1)]end):(push!(L,A$B))end;L)
ML
@ML: Nice, merci. Je n'avais pas pensé à utiliser l'opérateur ternaire. Mais vous n'avez pas réellement besoin des parenthèses dans le ternaire, ce qui économise 4 autres sur votre suggestion. Assigner Aet Bséparément est en fait la même longueur que les assigner ensemble, donc j'ai laissé cette partie telle quelle. Merci encore pour votre suggestion!
Alex A.
Je vous en prie. Ah, je vois. Oui, les parenthèses ne sont pas nécessaires.
ML
4

Python 2, 141

J'ai essayé quelques méthodes différentes, mais le meilleur que j'ai pu obtenir était relativement simple. Merci à @ Sp3000 pour environ 15 caractères (et pour m'avoir appris l'existence 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
KSab
la source
Voici 141: lien
Sp3000
4

Python 2, 127 122

En supposant que les chaînes de bits python du formulaire, '0b1'etc. sont 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)

Seule une légère nuance est ici l'utilisation du fait que XOR (A, B) = 0 si A = B.

Merci à @ Sp300 pour avoir raccourci la forboucle de fermeture

joc
la source
En
jetant
Je ne peux pas tester cette réponse pour le moment, mais si elle ne conserve pas les zéros non significatifs, elle est en effet malheureusement incorrecte.
Zgarb
3

Pyth, 34

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

Les utilisations réduisent pour appliquer chaque itération. Je vous expliquerai quand j'aurai fini de jouer au golf.

Essayez-le ici

FryAmTheEggman
la source
2

K, 46 53 46 octets

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

Un bon morceau de la taille (environ 7 octets) de cela est dû au fait que K n'a pas d' xoropérateur, j'ai donc dû en implémenter un moi-même. À l'origine, j'ai utilisé une liste de chaînes, puis j'ai réalisé que c'était incroyablement stupide. Alors maintenant, je coupe à nouveau les 7 octets!

Avant:

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

@JohnE a souligné dans les commentaires que l'état initial était censé être codé en dur, ce qui coûtait 7 octets supplémentaires. : /

kirbyfan64sos
la source
Ma lecture de la spécification du problème est que vous devez toujours commencer par "l'univers" codé en dur (1 0;1 1)- votre programme l'accepte comme entrée.
JohnE
@JohnE Fixed. Cependant, rien ne garantit que cela fonctionnera car je n'ai pas testé les modifications; Je viens d'essayer la partie finale de votre remplacement oK ...
kirbyfan64sos
Semble également bien fonctionner à Kona.
JohnE
2

JavaScript ( ES6 ) 152

Une fonction, utilisant des chaînes (avec des nombres, elle devrait être plus courte, mais en javascript, les opérations binaires sont limitées à des entiers 32 bits).

Testez dans Firefox en utilisant l'extrait ci-dessous.

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>

edc65
la source
1

K, 45 41 38 octets

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

La structure de ma réponse est assez similaire à celle de @ kirbyfan64sos, mais au lieu de chaînes, j'ai utilisé des vecteurs 1/0 et j'évite d'avoir besoin d'un conditionnel ( :[ ; ; ]) en indexant plutôt dans une liste.

Quelques runs:

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

Éditer:

Quatre octets enregistrés avec une manière plus compacte de construire l'univers initial:

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

Edit2:

J'ai oublié que "choisir" peut prendre une liste comme bon argument:

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

Je peux donc simplifier une partie de cela. À qui cela est dû, Kirby a eu cette astuce avant moi.

2?x    / new
x@2?#x / old
JohnE
la source
1
Dang, parfois je pense que je connais K, alors je vois vos réponses ...: O
kirbyfan64sos
Je pense que cette solution compte vraiment comme un effort d'équipe!
JohnE
1

Javascript, 241 233 octets

C'est un peu long.

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"));
SuperJedi224
la source
Le compilateur de fermeture l'a compressé en économisant 8 octets.
Gustavo Rodrigues
216 octets:, for(b=prompt(a=[[1,0],[1,1]]),R=Math.random;b--;){c=a.length;d=a[c*R()|0];e=a[c*R()|0];if(d+""==e+"")for(f=0;f<c;f++)a[f].push(2*R()|0);else{for(h=0,g=[];h<d.length;)g.push(d[h]^e[h++]);a.push(g)}}alert(a.join("\n"))produit la sortie souhaitée 3/5 du temps.
Ismael Miguel
217 octets:, for(b=prompt(a=[[1,0],[1,1]]),R=Math.random;b--;){c=a.length;d=a[c*R()|0];e=a[c*R()|0];if(d+""==e+"")for(f=0;f<c;f++)a[f].push(2*R()|0);else{g=[];for(h=0;h<d.length;h++)g.push(d[h]^e[h]);a.push(g)}}alert(a.join("\n"))fonctionne 90% du temps.
Ismael Miguel
1

T-SQL (2012+), 1019

Je suis vraiment désolé que ce soit loin d'être compétitif, mais pour être honnête, je ne pensais pas pouvoir le faire fonctionner et j'ai dû le poster une fois que je l'ai fait. J'ai essayé de jouer au golf un peu :)

Pour gérer les conversions binaires / entières, j'ai dû créer quelques fonctions scalaires (513 octets). Apasse d'un entier à une chaîne de bits. Bfait l'inverse.

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

Ensuite, il y a la procédure. @Cest le nombre d'étapes

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 @

Dix mille itérations ont pris environ 2 minutes et ont renvoyé 9991 lignes

1001001100110
1101001001110
0111100100101
1111100001011
1111001010011
0110101001101
...
1110101000100
1111011101100
1100001100010
0110010001001
1110100010100
MickyT
la source
0

Pyth - 37 octets

Évidemment, suit juste le pseudo-code. Peut probablement beaucoup jouer au golf.

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

Essayez-le ici en ligne .

Maltysen
la source
3
Vous avez besoin O2au lieu de O1. O1vous donne un nombre aléatoire dans la plage U1 = [0].
Jakube
2
Vous ajoutez donc toujours un 0.
Jakube
0

Mathematica, 106 octets

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

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"

Essayez- moi .

nutki
la source
0

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

Rien de magique ici. Entrez la valeur de tdans la console R et exécutez le script. Il est difficile de "jouer au golf" avec le code R, mais voici une version plus lisible:

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
shadowtalker
la source
Vous pouvez enregistrer un certain nombre de caractères en les affectant sampleà une variable. Par exemple s=sample, utilisez alors s plutôt que sample. Malheureusement, je pense que votre méthode d'ajout d'un bit aléatoire dans le lapplyse terminera par un échantillon aléatoire ajouté à tous les éléments de la liste. lapply(L,function(x)append(x,sample(0:1,1)))semble fonctionner, mais à un coût. Vous pouvez vous remplacer as.numericpar celui 1*qui devrait en récupérer.
MickyT
Bonne prise sur les deux points, et une belle astuce coercitive aussi
shadowtalker
Je viens également de remarquer que votre décompte est terminé. Je fais 168 en utilisant cela
MickyT
0

Rubis, 82

Assez simple. Comparé à d'autres langages non golfiques, ruby ​​semble bien fonctionner avec sa grande bibliothèque standard.

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

Exemple de sortie pour 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]
blutorange
la source