# Background

Yes, bitstring physics is a real thing. The idea is to construct a new theory of physics using only strings of bits that evolve under a probabilistic rule... or something. Despite reading a couple of papers about it, I'm still pretty confused. However, the bitstring universe makes for a nice little code golf.

# Program Universe

Bitstring physics takes place in a so-called program universe. At each step of the evolution of the universe, there is a finite list L of bitstrings of some length k, starting with the two-element list [10,11] where k = 2. One timestep is processed as follows (in Python-like 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


All random choices are uniformly random and independent of each other.

# Example

An example evolution of 4 steps might look like the following. Start with the initial list L:

10
11


We randomly choose A := 10 and B := 10, which are the same row, which means we need to extend each string in L with a random bit:

101
110


Next, we choose A := 101 and B := 110, and since they are not equal, we add their XOR to L:

101
110
011


Then, we choose A := 011 and B := 110, and again append their XOR:

101
110
011
101


Finally, we choose A := 101 (last row) and B := 101 (first row), which are equal, so we extend with random bits:

1010
1100
0111
1010


Your task is to take a nonnegative integer t as input, simulate the program universe for t timesteps, and return or print the resulting list L. Note that t = 0 results in the initial list [10,11]. You can output L as a list of lists of integers, list of lists of boolean values or a list of strings; if output goes to STDOUT, you may also print the bitstrings one per line in some reasonable format. The order of the bitstrings is significant; in particular, the initial list cannot be [11,10], [01,11] or anything like that. Both functions and full programs are acceptable, standard loopholes are disallowed, and the lowest byte count wins.

• Can we limit the bit string length (that is: may I use 32 bit numbers and bit operations)? – edc65 Jun 16 '15 at 9:58
• @edc65 No, the length of the strings can get arbitrarily high. – Zgarb Jun 16 '15 at 10:08
• @edc65 The expected time and memory requirements for getting over 32 bits are astronomical, but that's just fitting since we're simulating a universe. ;) – Zgarb Jun 16 '15 at 18:53
• Is this Bit-string Physics a crackpot idea? I haven't read the whole paper, but the phrase We have used bit-string physics to provide a theory in which the approximation hbar c/e2 = 22 - 1 + 23 - 1 + 27 - 1 = 137 makes sense in terms of a computer algorithm and information theory strikes me as a bit ... numerological. – xebtl Jun 17 '15 at 7:26
• @xebtl It does seem crazy to me too. I remember reading a justification for the algorithm somewhere, and it sounded more like bad pseudo-philosophy than physics. Also, your description of the algorithm seems to match my version, maybe I'm misunderstanding you in some way. – Zgarb Jun 17 '15 at 18:11

# Pyth, 27 26 bytes

u?+RO2GqFKmOG2aGxVFKQ*]1U2


Try it online: Demonstration

### Explanation:

                              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

• xVFK is equivalent to xMK. – isaacg Jun 16 '15 at 0:19
• @isaacg No, xVFK is equivalent to xMCK, same byte count. – Jakube Jun 16 '15 at 7:09

# CJam, 424038 37 bytes

1 byte saved by Sp3000.

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


## Explanation

Create the initial state as a base-2 number:

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


And then perform the main loop and pretty-print the result at the end:

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.


Test it here.

# 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)  Nothing clever. Creates an unnamed function that accepts an integer as input and returns an array of arrays. To call it, give it a name, e.g. f=t->.... Ungolfed + explanation: 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


Examples:

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]


Saved 12 bytes thanks to M L!

• You can shave it down to 133 characters if you use the ternay operator instead of if/else and if you change 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) – M L Jun 17 '15 at 1:40 • @ML: Nice, thanks. I hadn't thought to use the ternary operator. But you don't actually need the parentheses in the ternary, which saves another 4 over your suggestion. Assigning A and B separately is actually the same length as assigning them together, so I left that part as is. Thanks again for your suggestion! – Alex A. Jun 17 '15 at 2:40 • You’re welcome. Ah, I see. Yes, the parentheses aren’t necessary. – M L Jun 17 '15 at 3:15 # Python 2, 141 I tried a few different methods, but the best I could get was relatively straightforward. Thanks to @Sp3000 for 15 chars or so (and for teaching me about the existence of 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  • Here's 141: link – Sp3000 Jun 16 '15 at 3:57 ## Python 2, 127 122 Assuming python bit strings of the form '0b1' etc. are 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)  Only mild nuance here is use of the fact that XOR(A,B)=0 iff A=B. Thanks to @Sp300 for shortening the enclosing for loop • Taking a look at the comments though, I think leading zeroes need to be preserved – Sp3000 Jun 17 '15 at 8:13 • I cannot test this answer right now, but if it doesn't preserve leading zeroes, it's indeed unfortunately incorrect. – Zgarb Jun 17 '15 at 19:43 # Pyth, 34 u?+ROTGqJOGKOG+Gsms!dqVJKQ[T11  Uses reduce to apply each iteration. I'll explain when I'm done golfing. Try it here # K, 4653 46 bytes {x{:[~/t:2?x;{x,*1?2}'x;x,,,/~=/t]}/(1 0;1 1)}  A good chunk of the size (about 7 bytes) of this is do to the fact that K has no xor operator, so I had to implement one myself. Originally, I used a list of strings, followed by realizing that was insanely stupid. So now I cut off the 7 bytes again! Before: {x{:[~/t:2?x;{x,*$1?2}'x;x,,,/$~=/(0$')'t]}/$:'10 11}  @JohnE pointed out in the comments that the initial state was supposed to be hardcoded, which cost 7 extra bytes. :/ • My reading of the problem spec is that you must always begin with the hardcoded "universe" (1 0;1 1)- your program accepts this as input. – JohnE Jun 15 '15 at 21:36 • @JohnE Fixed. However, there's no guarantee this will work because I didn't test the changes; I just tried the ending part in your oK repl... – kirbyfan64sos Jun 15 '15 at 21:42 • Seems to work fine in Kona as well. – JohnE Jun 15 '15 at 21:43 # JavaScript (ES6) 152 A function, using strings (with numbers it should be shorter, but in javascript bit operations are limited to 32 bit integers). Test in Firefox using the snippet below. 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, 4541 38 bytes {x{(x,,~=/t;{x,1?2}'x)@~/t:2?x}/1,'!2}  The structure of my answer is quite similar to that of @kirbyfan64sos, but instead of strings I used 1/0 vectors and I avoid the need for a conditional (:[ ; ; ]) by instead indexing into a list. A few 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)  ## Edit: Saved four bytes with a more compact way to build the initial universe: 1,'!2 / new (1 0;1 1) / old  ## Edit2: I forgot that "choose" can take a list as its right argument:  2?"abcd" "dc" 2?"abcd" "cc" 2?"abcd" "ca"  So I can simplify part of this. Credit where it's due, Kirby got this trick before I did. 2?x / new x@2?#x / old  • Dang, sometimes I think I know K, then I see your answers... :O – kirbyfan64sos Jun 15 '15 at 22:12 • I think this solution definitely counts as a team effort! – JohnE Jun 15 '15 at 22:14 # Javascript, 241 233 bytes That's kind of 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"));  • Closure Compiler compressed it saving 8 bytes. – Gustavo Rodrigues Jun 16 '15 at 12:28 • 216 bytes: 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")), produces the desired output 3/5 of the time. – Ismael Miguel Jun 16 '15 at 17:16 • 217 bytes: 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")), works 90% of the time. – Ismael Miguel Jun 16 '15 at 17:19 # T-SQL (2012+), 1019 I'm really sorry this is nowhere near competitive, but to be honest I didn't think I could get this to work and had to post it once I did. I did try to golf it a bit :) To handle the binary/integer conversions I had to create a couple of scalar functions (513 of the bytes). A goes from integer to a bit string. B does the reverse. 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  Then there is the procedure. @C is the number of steps 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 @  Ten thousand iterations took around 2 minutes and returned 9991 rows 1001001100110 1101001001110 0111100100101 1111100001011 1111001010011 0110101001101 ... 1110101000100 1111011101100 1100001100010 0110010001001 1110100010100  # Pyth - 37 bytes Obvious, just follows psuedocode. Probably can golf a lot. KPP^,1Z2VQ=K?m+dO1KqFJ,OKOKaKxVhJeJ;K  • You need O2 instead of O1. O1 gives you a random number from the range U1 = [0]. – Jakube Jun 15 '15 at 18:07 • So you're always appending a 0. – Jakube Jun 15 '15 at 18:17 # 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"


Try me.

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


Nothing magical here. Enter the value for t in the R console and run the script. It's hard to "golf" R code but here's a more readable 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

• You can save a number of characters by assigning sample to a variable. eg s=sample, then use s rather than sample. Unfortunately I think your method of appending a random bit in the lapply will end up with one random sample being added to all items in the list. lapply(L,function(x)append(x,sample(0:1,1))) appears to work, but at a cost. You can replace you as.numeric with 1* which should get some back. – MickyT Jun 17 '15 at 2:21
• Good catch on both points, and a nice coercion trick too – shadowtalker Jun 17 '15 at 3:56
• Also just noticed your count is out. I make it 168 using this – MickyT Jun 17 '15 at 22:44

# Ruby, 82

Pretty much straight-forward. Compared with other non-golfing languages, ruby seems to do well with its large standard library.

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


Sample output for 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]