Introdução

Neste desafio, simularemos um certo autômato celular probabilístico usando números pseudo-aleatórios muito ruins. O autômato celular é definido em cadeias binárias pela seguinte regra local. Suponha que o vizinho esquerdo de uma célula e a própria célula tenham estados ae b.

• Se min(a,b) == 0, então o novo estado de bé max(a,b).
• Se min(a,b) == 1, então o novo estado de bé escolhido aleatoriamente {0,1}.

A figura a seguir mostra uma possível evolução em 10 etapas de uma única 1.

1
11
101
1111
11001
101011
1111111
10001001
110011011
1010111101

Observe como dois 1s adjacentes às vezes evoluem para 1, e algumas vezes para 0, e os bits mais próximos da borda são sempre 1s. Sua tarefa é produzir uma evolução de autômato celular dessa forma.

Entradas

Suas entradas são um número inteiro positivo n, denotando o número de linhas a serem exibidas e uma lista não vazia de bits L, que usamos como fonte de aleatoriedade.

Resultado

Sua saída é uma lista de listas ou matriz 2D de bits, representando a evolução de um único 1para npassos de tempo, como na figura acima. Você pode preencher a saída com 0s para obter linhas de comprimentos iguais, se desejado, mas não deve haver 0s iniciais .

As escolhas aleatórias no autômato celular devem ser retiradas da lista L, voltando ao início quando estiver esgotado. Mais explicitamente, se a saída for percorrida uma linha de cada vez, de cima para baixo, da esquerda para a direita, as sucessivas escolhas aleatórias formarão a lista Lrepetida quantas vezes forem necessárias.

Exemplo

Suponha que as entradas sejam n = 7e L = [0,1,0]. Em seguida, o autômato celular evolui da seguinte maneira durante as 7 etapas, onde colocamos um vdireito acima de cada escolha aleatória:

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

Se lermos todos os bits marcados com a v, obtemos 01001001, que é Lrepetido 2,66 vezes. O próximo bit aleatório seria 0.

Regras e Pontuação

Você pode escrever um programa completo ou uma função. A contagem de bytes mais baixa vence e as brechas padrão não são permitidas. O formato exato das entradas e saídas não é importante (dentro do motivo).

Casos de teste

Versão determinística, todo bit aleatório é 0:

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

Todo bit aleatório é 1:

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

Versões pseudo-aleatórias:

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

Pitão, 33 bytes

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

Experimente on-line: Demonstration or Test Suite

Explicação:

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

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>

Onde <empty>indica que há uma linha vazia à direita. Cada linha entra em um arquivo separado e #deve ser substituída por alimentações de linha (0x0A).

Espera que a entrada para estar nem unária (feita de zeros, como em Unário ), seguido por um espaço, seguido pelo "pseudo-aleatório" cadeia de caracteres, por exemplo, 10, [1, 0, 0, 1]seria lida como

0000000000 1001

A saída é como no desafio, mas preenchida com zeros, por exemplo

1000000000
1100000000
1110000000
1001000000
1101100000
1111110000
1001101000
1101011100
1111111010
1011001111

Isso foi muito mais complicado do que eu esperava ...

Python, 142 135 132 131 bytes

133 132 131 versão de bytes

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

substituídos r[x-1]+r[x]>1por r[x-1]&r[x]eram o operador bit a bit e produz o valor mínimo em(r[x-1],r[x])

Obrigado @ThomasKwa por sugerir em n*nvez de n**2economizar 1 byte!

Obrigado @Shebang pelo -1 byte

Versão de 135 bytes

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

Graças ao @Cole pelos bytes -7:

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

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

Versão de 142 bytes

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

Nem mesmo perto da resposta de @ Jakube, mas eu me diverti muito codificando e jogando golfe.

Espera duas entradas: a primeira entrada é o número de linhas e a segunda entrada é a lista de fontes de pseudo - aleatoriedade . Imprime no console uma linha após a outra, cada uma em uma nova linha.

Como um exemplo:

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]

Agora, para uma breve explicação sobre como funciona:

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    

O truque aqui é que sabemos que a lista de bits sempre começa e termina com um 1porque o primeiro e o último elemento nunca são modificados devido às especificações. da pergunta. Essa é a razão da declaração [1]+r+[1].

Mas se ré inicializado como [1], não há alterações na primeira linha e, em seguida, adicionamos [1]+r+[1]como é que a segunda linha não é [1,1,1]?

Isso se deve ao fato de que, na primeira iteração i=1, range(1,i)retorna uma lista vazia e, como resultado da forcompreensão na lista, não ter nada para repetir rse torna uma lista vazia [1]+r+[1]=[1,1]. Isso acontece na primeira iteração, que é ideal para nós!

PS: Sinta-se à vontade para fazer sugestões sobre como jogar mais.

MATLAB, 146 143 138

(Também funciona no Octave online, mas você precisa fazer login para salvar a função em um arquivo).

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

A função recebe uma entrada neL , e retorna uma matriz oque contém a saída.

Para os valores de entrada, né um escalar e Lé um vetor de coluna, que pode ser especificado no formato[;;;] . Não é exatamente o que você mostra, mas você diz que é flexível dentro da razão e isso parece ser.

A saída é formatada como um n x n matriz contendo 0 e 1.

E uma explicação:

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

Atualização: Eu consegui otimizar a instrução if-else para economizar alguns bytes. O formato de entrada voltou a mudar para o vetor da coluna.

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

%retorna uma lista de listas de bits. Exemplo de uso:

> 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 céus! Carregar a lista aleatória Lé pura dor. Vamos ver se isso pode ser mais curto.

C #, 152 bytes

Não há nada de especial aqui. A função retorna uma matriz 2D onde a primeira classificação é a linha e a segunda é a coluna.

Linhas recuadas e novas para maior clareza:

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

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

O TI-BASIC não tem um operador de incremento, certo? Bem, mais ou menos. A variável de equação u, normalmente usada com sequências, tem um recurso obscuro: quando ué chamada com um argumento, a variável 𝑛é definida como uma maior que o argumento. O incremento condicional depende disso. (Estou esperando para usá-lo há muito tempo.)

Para que a indexação de lista funcione corretamente, 𝑛o valor padrão deve ser 0 e 𝑛Mino valor padrão 1; limpe a RAM da calculadora ou defina esses valores manualmente antes de executar isso.

augment({0},Ans)+augment(Ans,{0calcula uma lista de somas de dois elementos adjacentes, para que retorne uma lista de 0s, 1s e 2s. Então a mágica está nesta linha:

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

O resultado dessa linha será que os elementos da lista serão 0 se forem 0 ou 2 e o bit lido for 0.

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

Caso de teste:

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