Pseudorandom Cellular Automaton

Question

Introduction

In this challenge, we will simulate a certain probabilistic cellular automaton using very bad pseudorandom numbers. The cellular automaton is defined on binary strings by the following local rule. Suppose that the left neighbor of a cell and the cell itself have states a and b.

• If min(a,b) == 0, then the new state of b is max(a,b).
• If min(a,b) == 1, then the new state of b is chosen randomly from {0,1}.

The following picture shows one possible 10-step evolution of a single 1.

1
11
101
1111
11001
101011
1111111
10001001
110011011
1010111101

Note how two adjacent 1s sometimes evolve to 1, and sometimes to 0, and the border-most bits are always 1s. Your task is to produce a cellular automaton evolution of this form.

Inputs

Your inputs are a positive integer n, denoting the number of rows to display, and a non-empty list of bits L, which we use as a source of randomness.

Output

Your output is a list of lists or 2D array of bits, depicting the evolution of a single 1 for n time steps, as in the above figure. You can pad the output with 0s to get rows of equal lengths, if desired, but there must not be leading 0s.

The random choices in the cellular automaton must be drawn from the list L, jumping back to the beginning when it is exhausted. More explicitly, if the output is traversed one row at a time form top to bottom, left to right, then the successive random choices shall form the list L repeated as many times as necessary.

Example

Suppose the inputs are n = 7 and L = [0,1,0]. Then the cellular automaton evolves as follows during the 7 steps, where we have put a v right above every random choice:

[1]

[1,1]
   v
[1,0,1]

[1,1,1,1]
   v v v
[1,1,0,0,1]
   v
[1,1,1,0,1,1]
   v v   v
[1,0,0,1,1,1,1]

If we read all the bits marked with a v, we get 01001001, which is L repeated 2.66 times. The next random bit would be 0.

Rules and Scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. The exact format of the inputs and outputs is unimportant (within reason).

Test Cases

Deterministic version, every random bit is 0:

Inputs: 10 [0]
Output:
1
11
101
1111
10001
110011
1010101
11111111
100000001
1100000011

Every random bit is 1:

Inputs: 6 [1,1]
Output:
1
11
111
1111
11111
111111

Pseudorandom versions:

Inputs: 10 [0,0,1]
Output:
1
11
101
1111
10101
111111
1010011
11110101
101011111
1111101001

Inputs: 10 [1,0,0,1]
Output:
1
11
111
1001
11011
111111
1001101
11010111
111111101
1011001111

Inputs: 15 [1,1,1,0,0,0]
Output:
1
11
111
1111
10001
110011
1110111
11011001
111111011
1100011111
11100100011
111101100101
1001111101111
11011000111111
101101001011101

Answer 1

Pyth, 33 bytes

jjLk.u++1m?hSde=.<Q1sd.:N2 1tvz]1

Try it online: Demonstration or Test Suite

Explanation:

jjLk.u++1m?hSde=.<Q1sd.:N2 1tvz]1  implicit: Q = input list
    .u                      tvz]1  reduce N=[1] input-1 times by applying
                      .:N2           all substrings of length 2
         m                           map each d of ^ to:
          ?hSd                         if min(d) = 0 then:
               =.<Q1                     rotate Q by one
              e                          and use the last element
                    sd                 else use sum(d) (=max(d))
      ++1                  1         add a 1 at the front and the back
                                   .u gives all intermediate results
 jLk                               join these lists to strings
j                                  print each string on a line

Answer 2

Retina, 139 bytes

^.
1

 00:0 01:1 10:1 11:
(m`^(..)((\S*)(?<=0) .*)
$1$3#$1!$2
+m`(?<=^(?<-2>.)*(..).*?#(.)*.)\d!(.)(.*\1:)(.)(\d*)
$5$3!$4$6$5
)`!0
0
 .+
<empty>

Where <empty> indicates that there is a trailing empty line. Each line goes in a separate file and the # should be replaced with linefeeds (0x0A).

Expects the input to be n in unary (made of zeroes, as in Unary), followed by a space, followed by the "pseudo-random" string, e.g. 10, [1, 0, 0, 1] would be read as

0000000000 1001

Output is as in the challenge, but padded with zeroes, e.g.

1000000000
1100000000
1110000000
1001000000
1101100000
1111110000
1001101000
1101011100
1111111010
1011001111

This was way trickier than I expected...

Answer 3

Python, 142 135 132 131 bytes

133 132 131 byte version

f=input;n=f();L=f()*n*n;r=[1];i=1
while i<=n:print r;r=[L.pop(0)if r[x-1]&r[x]else r[x-1]+r[x]for x in range(1,i)];r=[1]+r+[1];i+=1

replaced r[x-1]+r[x]>1 by r[x-1]&r[x] were the bitwise operator & yields the minimum value in (r[x-1],r[x])

Thanks @ThomasKwa for suggesting n*n instead of n**2 which saves 1 byte!

Thanks @Shebang for the -1 byte

135 byte version

f=input;n=f();L=f()*n**2;r=[1];i=1
while i<=n:print r;r=[L.pop(0)if r[x-1]+r[x]>1 else r[x-1]+r[x]for x in range(1,i)];r=[1]+r+[1];i+=1

Thanks to @Cole for the -7 bytes:

min(r[x-1],r[x])->r[x-1]+r[x]>1

max(r[x-1],r[x])->r[x-1]+r[x]

142 byte version

f=input;n=f();L=f()*n**2;r=[1];i=1
while i<=n:print r;r=[L.pop(0)if min(r[x-1],r[x])else max(r[x-1],r[x])for x in range(1,i)];r=[1]+r+[1];i+=1

Not even close to @Jakube's answer but I had a lot of fun coding and golfing this one.

Expects two inputs: first input is the number of rows and second input is the pseudorandomness source list. It prints on console one row after another, each on a new line.

As an example:

10 # This is input
[0] # This is input
[1] <- First output row
[1, 1]
[1, 0, 1]
[1, 1, 1, 1]
[1, 0, 0, 0, 1]
[1, 1, 0, 0, 1, 1]
[1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 1, 0, 0, 0, 0, 0, 0, 1, 1]

Now for a short explanation on how it works:

f=input;n=f();L=f()*n*n;r=[1];i=1 First we define the input() function as f 
                                   for saving bytes as we have to call it twice.
                                   Then L is defined as a list made of the 
                                   pseudorandom numbers in their order *many* times 
                                   (were *many* is an upperbound of the canges that 
                                   could be done); r as the first row and i as the row 
                                   counter.

while i<=n:print r                 A while loop that exits when the nth row has been 
                                   calculated and the printing of the actual row.

r=[L.pop(0)if r[x-1]&r[x] else r[x-1]+r[x] for x in range(1,i)];r=[1]+r+[1];i+=1
     ^           ^                 ^                         ^
     |           |                 |Same as max(r[x-1],r[x]) | from 2nd to last element
     |           | Same as min(r[x-1],r[x]) (0->False;1->True)                
     | get random bit from pseudorandom list    

The trick here is that we know that the bit list will always start and end with a 1 because the first and last elements are never modified due to the specs. of the question. That's the reason for the statement [1]+r+[1].

But if r is initialized as [1], there are no changes on the first row and then we add [1]+r+[1] how come the second row is not [1,1,1]?

This is due to the fact that on the first iteration i=1 so range(1,i) returns an empty list and, as a result of the for in the list comprehension having nothing to iterate over r becomes an empty list so [1]+r+[1]=[1,1]. This just happens on the first iteration which is just ideal for us!

P.S: Feel free to make any suggestions on how to golf it more.

Answer 4

MATLAB, 146 143 138

(Also works on Octave online, but you need to sign in to save the function in a file).

function o=c(n,L);o=zeros(n);o(:,1)=1;for i=2:n;for j=2:i;a=o(i-1,j-1);b=o(i-1,j);c=a|b;d=a&b;c(d)=L(d);L=circshift(L,-d);o(i,j)=c;end;end

The function takes an input n and L, and returns an array o which contains the output.

For the input values, n is a scalar, and L is a column vector, which can be specified in the format [;;;]. Not quite what you show, but you say it is flexible within reason and this seems so.

The output is formatted as an n x n array containing 0's and 1's.

And an explanation:

function o=c(n,L)
%Create the initial array - an n x n square with the first column made of 1's
o=zeros(n);o(:,1)=1;
%For each row (starting with the second, as the first is done already)
for i=2:n;
    %For each column in that row, again starting with the second as the first is done
    for j=2:i;
        %Extract the current and previous elements in the row above
        a=o(i-1,j-1); %(previous)
        b=o(i-1,j);   %(current)
        %Assume that min()==0, so set c to max();
        c=a|b;
        %Now check if min()==1
        d=a&b;
        %If so, set c to L(1)
        c(d)=L(d);
        %Rotate L around only if min()==1
        L=circshift(L,-d);
        %And store c back to the output matrix
        o(i,j)=c;
    end;
end

---

Update: I have managed to optimise away the if-else statement to save a few bytes. The input format has once again changed back to column vector.

Answer 5

Haskell, 153 149 bytes

j[_]o l=(l,o)
j(a:u@(b:c))o q@(l:m)|a*b==0=j u(o++[a+b])q|1<2=j u(o++[l])m
k(r,a)=fmap((1:).(++[1]))$j a[]r
n%l=map snd$take n$iterate k(cycle l,[1])

% returns a list of bit lists. Usage example:

> 10 % [1,0,0,1] 
[[1],[1,1],[1,1,1],[1,0,0,1],[1,1,0,1,1],[1,1,1,1,1,1],[1,0,0,1,1,0,1],[1,1,0,1,0,1,1,1],[1,1,1,1,1,1,1,0,1],[1,0,1,1,0,0,1,1,1,1]]

Oh dear! Carrying the random list L around is pure pain. Let's see if this can be shorter.

Answer 6

C#, 152 bytes

There's nothing special here. The function returns a 2D array where the first rank is the line and the second is the column.

Indented and new lines for clarity:

int[,]F(int n,int[]l){
    var o=new int[n,n];
    for(int y=0,x,i=0,m;y<n;y++)
        for(o[y,x=0]=1;x++<y;)
            o[y,x]=(m=o[y-1,x-1]+o[y-1,x])<2?m:l[i++%l.Length];
    return o;
}

Answer 7

TI-BASIC, 106 94 87 86 87 bytes

Prompt N,B
"∟B(1+remainder(,dim(∟B→u
{1
For(I,1,N
Disp Ans
augment({0},Ans)+augment(Ans,{0
Ans and Ans≠2+seq(u(-(Ans(X)<2)+2dim(∟B)),X,1,dim(Ans
End

TI-BASIC doesn't have an increment operator, right? Well, it sort of does. The equation variable u, normally used with sequences, has an obscure feature: when u is called with an argument, the variable is set to one greater than that argument. The conditional increment depends on this. (I've been waiting to use it for a long time.)

For list indexing to work properly, must be its default value of 0, and Min should be its default 1, so either clear your calculator's RAM or set those values manually before running this.

augment({0},Ans)+augment(Ans,{0 calculates a list of sums of two adjacent elements, so it will return a list of 0s, 1s, and 2s. Then the magic is on this line:

Ans and Ans≠2+seq(u(-(Ans(X)≠2)+dim(∟B)),X,1,dim(Ans

Ans and                 ;set 0s to 0
Ans≠                    ;set to 0 all sums that equal...
2+
  seq(...,X,1,dim(Ans   ;execute for each element of the list
      u(                ;return this element in list of bits (looping)        
                       ;current location in the list
        -(Ans(X)≠2)+    ;subtract 1 if the element isn't 2
        2dim(∟B)        ;Add twice the dimension of the list
                           ;(because n<nMin on the first iteration, it's out of the domain
                           ;this prevents an error)
       )                      ;set n to one greater than that value
                              ;i.e. increment if element≠2
                        ;Will equal Ans(X) iff Ans(X)=2 and the bit read false

The result of this line will be that list elements are 0 if they were 0 or if they were 2 and the bit read was 0.

Result of above line
n \ u |  0  |  1
0        0     0

Test case:

N=?7
B=?{0,1,0
             {1}
           {1 1}
         {1 0 1}
       {1 1 1 1}
     {1 1 0 0 1}
   {1 1 1 0 1 1}
 {1 0 0 1 1 1 1}
            Done