21
\$\begingroup\$

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

The Task

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.

\$\endgroup\$
  • \$\begingroup\$ Can we limit the bit string length (that is: may I use 32 bit numbers and bit operations)? \$\endgroup\$ – edc65 Jun 16 '15 at 9:58
  • 1
    \$\begingroup\$ @edc65 No, the length of the strings can get arbitrarily high. \$\endgroup\$ – Zgarb Jun 16 '15 at 10:08
  • 3
    \$\begingroup\$ @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. ;) \$\endgroup\$ – Zgarb Jun 16 '15 at 18:53
  • 5
    \$\begingroup\$ 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. \$\endgroup\$ – xebtl Jun 17 '15 at 7:26
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Zgarb Jun 17 '15 at 18:11

16 Answers 16

7
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ xVFK is equivalent to xMK. \$\endgroup\$ – isaacg Jun 16 '15 at 0:19
  • \$\begingroup\$ @isaacg No, xVFK is equivalent to xMCK, same byte count. \$\endgroup\$ – Jakube Jun 16 '15 at 7:09
11
\$\begingroup\$

CJam, 42 40 38 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.

\$\endgroup\$
6
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – M L Jun 17 '15 at 1:40
  • \$\begingroup\$ @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! \$\endgroup\$ – Alex A. Jun 17 '15 at 2:40
  • \$\begingroup\$ You’re welcome. Ah, I see. Yes, the parentheses aren’t necessary. \$\endgroup\$ – M L Jun 17 '15 at 3:15
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Here's 141: link \$\endgroup\$ – Sp3000 Jun 16 '15 at 3:57
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Taking a look at the comments though, I think leading zeroes need to be preserved \$\endgroup\$ – Sp3000 Jun 17 '15 at 8:13
  • \$\begingroup\$ I cannot test this answer right now, but if it doesn't preserve leading zeroes, it's indeed unfortunately incorrect. \$\endgroup\$ – Zgarb Jun 17 '15 at 19:43
3
\$\begingroup\$

Pyth, 34

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

Uses reduce to apply each iteration. I'll explain when I'm done golfing.

Try it here

\$\endgroup\$
2
\$\begingroup\$

K, 46 53 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. :/

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – JohnE Jun 15 '15 at 21:36
  • \$\begingroup\$ @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... \$\endgroup\$ – kirbyfan64sos Jun 15 '15 at 21:42
  • \$\begingroup\$ Seems to work fine in Kona as well. \$\endgroup\$ – JohnE Jun 15 '15 at 21:43
2
\$\begingroup\$

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>

\$\endgroup\$
1
\$\begingroup\$

K, 45 41 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
\$\endgroup\$
  • 1
    \$\begingroup\$ Dang, sometimes I think I know K, then I see your answers... :O \$\endgroup\$ – kirbyfan64sos Jun 15 '15 at 22:12
  • \$\begingroup\$ I think this solution definitely counts as a team effort! \$\endgroup\$ – JohnE Jun 15 '15 at 22:14
1
\$\begingroup\$

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"));
\$\endgroup\$
  • \$\begingroup\$ Closure Compiler compressed it saving 8 bytes. \$\endgroup\$ – Gustavo Rodrigues Jun 16 '15 at 12:28
  • \$\begingroup\$ 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. \$\endgroup\$ – Ismael Miguel Jun 16 '15 at 17:16
  • \$\begingroup\$ 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. \$\endgroup\$ – Ismael Miguel Jun 16 '15 at 17:19
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

Pyth - 37 bytes

Obvious, just follows psuedocode. Probably can golf a lot.

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

Try it here online.

\$\endgroup\$
  • 3
    \$\begingroup\$ You need O2 instead of O1. O1 gives you a random number from the range U1 = [0]. \$\endgroup\$ – Jakube Jun 15 '15 at 18:07
  • 2
    \$\begingroup\$ So you're always appending a 0. \$\endgroup\$ – Jakube Jun 15 '15 at 18:17
0
\$\begingroup\$

Mathematica, 106 bytes

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

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – MickyT Jun 17 '15 at 2:21
  • \$\begingroup\$ Good catch on both points, and a nice coercion trick too \$\endgroup\$ – shadowtalker Jun 17 '15 at 3:56
  • \$\begingroup\$ Also just noticed your count is out. I make it 168 using this \$\endgroup\$ – MickyT Jun 17 '15 at 22:44
0
\$\begingroup\$

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]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.