introduction

Dans ce défi, nous simulerons un certain automate cellulaire probabiliste utilisant de très mauvais nombres pseudo-aléatoires. L'automate cellulaire est défini sur des chaînes binaires par la règle locale suivante. Supposons que le voisin gauche d'une cellule et la cellule elle-même aient des états aet b.

• Si min(a,b) == 0, alors le nouvel état de best max(a,b).
• Si min(a,b) == 1, alors le nouvel état de best choisi aléatoirement {0,1}.

L'image suivante montre une évolution possible en 10 étapes d'un seul 1.

1
11
101
1111
11001
101011
1111111
10001001
110011011
1010111101

Notez comment deux 1s adjacents évoluent parfois vers 1, et parfois vers 0, et les bits les plus à la frontière sont toujours 1s. Votre tâche est de produire une évolution automate cellulaire de cette forme.

Contributions

Vos entrées sont un entier positif n, indiquant le nombre de lignes à afficher, et une liste non vide de bits L, que nous utilisons comme source de hasard.

Production

Votre sortie est une liste de listes ou un tableau 2D de bits, décrivant l'évolution d'un seul 1pour les npas de temps, comme dans la figure ci-dessus. Vous pouvez remplir la sortie avec 0s pour obtenir des lignes de longueurs égales, si vous le souhaitez, mais il ne doit pas y avoir de 0s en tête .

Les choix aléatoires dans l'automate cellulaire doivent être tirés de la liste L, en remontant au début quand il est épuisé. Plus explicitement, si la sortie est parcourue une ligne à la fois de haut en bas, de gauche à droite, les choix aléatoires successifs formeront la liste Lrépétée autant de fois que nécessaire.

Exemple

Supposons que les entrées soient n = 7et L = [0,1,0]. Ensuite, l'automate cellulaire évolue comme suit au cours des 7 étapes, où nous avons mis un vdroit au-dessus de chaque choix aléatoire:

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

Si nous lisons tous les bits marqués d'un v, nous obtenons 01001001, qui est Lrépété 2,66 fois. Le bit aléatoire suivant serait 0.

Règles et notation

Vous pouvez écrire un programme complet ou une fonction. Le nombre d'octets le plus bas gagne et les failles standard sont interdites. Le format exact des entrées et sorties est sans importance (dans des limites raisonnables).

Cas de test

Version déterministe, chaque bit aléatoire est 0:

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

Chaque bit aléatoire est 1:

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

Versions pseudo-aléatoires:

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

Pyth, 33 octets

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

Essayez-le en ligne: démonstration ou suite de tests

Explication:

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

Rétine , 139 octets

^.
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>

Où <empty>indique qu'il y a une ligne vide de fin. Chaque ligne va dans un fichier séparé et #doit être remplacée par des sauts de ligne (0x0A).

S'attend à ce que l'entrée soit nen unaire (faite de zéros, comme dans Unaire ), suivie d'un espace, suivie de la chaîne "pseudo-aléatoire", par exemple 10, [1, 0, 0, 1]serait lue comme

0000000000 1001

La sortie est comme dans le défi, mais remplie de zéros, par exemple

1000000000
1100000000
1110000000
1001000000
1101100000
1111110000
1001101000
1101011100
1111111010
1011001111

C'était beaucoup plus délicat que ce à quoi je m'attendais ...

Python, 142 135 132 131 131 octets

133 132 Version 131 octets

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

remplacé r[x-1]+r[x]>1par r[x-1]&r[x]étaient l'opérateur au niveau du bit et donne la valeur minimale en(r[x-1],r[x])

Merci à @ThomasKwa d'avoir suggéré n*nau lieu de n**2ce qui économise 1 octet!

Merci @Shebang pour le -1 octet

Version 135 octets

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

Merci à @Cole pour les -7 octets:

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

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

Version 142 octets

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

Pas même proche de la réponse de @ Jakube, mais j'ai eu beaucoup de plaisir à coder et à jouer au golf.

Attend deux entrées: la première entrée est le nombre de lignes et la deuxième entrée est la liste des sources de pseudo - aléatoire . Il imprime sur la console une ligne après l'autre, chacun sur une nouvelle ligne.

Par exemple:

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]

Maintenant, pour une courte explication sur la façon dont cela fonctionne:

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    

L'astuce ici est que nous savons que la liste de bits commencera et se terminera toujours par un 1car les premier et dernier éléments ne sont jamais modifiés en raison des spécifications. de la question. C'est la raison de la déclaration [1]+r+[1].

Mais si rest initialisé en tant que [1], il n'y a aucun changement sur la première ligne, puis nous ajoutons [1]+r+[1]pourquoi la deuxième ligne ne l'est pas [1,1,1]?

Cela est dû au fait que lors de la première itération retourne i=1donc range(1,i)une liste vide et, à la suite de la forcompréhension dans la liste, rien à répéter rdevient une liste vide [1]+r+[1]=[1,1]. Cela se produit juste sur la première itération qui est juste idéale pour nous!

PS: N'hésitez pas à faire des suggestions sur la façon de jouer au golf plus.

MATLAB, 146 143 138

(Fonctionne également sur Octave en ligne, mais vous devez vous connecter pour enregistrer la fonction dans un fichier).

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

La fonction prend une entrée net L, et retourne un tableau oqui contient la sortie.

Pour les valeurs d'entrée, nest un scalaire et Lun vecteur de colonne, qui peut être spécifié dans le format [;;;]. Pas tout à fait ce que vous montrez, mais vous dites qu'il est flexible dans des limites raisonnables et cela semble être le cas.

La sortie est formatée comme un n x ntableau contenant des 0 et des 1.

Et une explication:

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

Mise à jour: j'ai réussi à optimiser la déclaration if-else pour économiser quelques octets. Le format d'entrée est redevenu vecteur de colonne.

Haskell, 153 149 octets

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

%renvoie une liste de listes de bits. Exemple d'utilisation:

> 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 cher! Porter la liste aléatoire Lest une pure douleur. Voyons voir si cela peut être plus court.

C #, 152 octets

Il n'y a rien de spécial ici. La fonction renvoie un tableau 2D où le premier rang est la ligne et le second la colonne.

Nouvelles lignes en retrait pour plus de clarté:

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 octets

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 n'a pas d'opérateur d'incrémentation, non? Eh bien, en quelque sorte. La variable d'équation u, normalement utilisée avec les séquences, a une caractéristique obscure: lorsqueu est appelée avec un argument, la variable 𝑛est définie sur un supérieur à cet argument. L'incrément conditionnel en dépend. (J'attends de l'utiliser depuis longtemps.)

Pour que l'indexation de liste fonctionne correctement, 𝑛sa valeur par défaut doit être 0 et 𝑛Minsa valeur par défaut 1, donc effacez la RAM de votre calculatrice ou définissez ces valeurs manuellement avant d'exécuter cela.

augment({0},Ans)+augment(Ans,{0calcule une liste de sommes de deux éléments adjacents, il renvoie donc une liste de 0, 1 et 2. Ensuite, la magie est sur cette ligne:

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

Le résultat de cette ligne sera que les éléments de liste sont 0 s'ils étaient 0 ou s'ils étaient 2 et le bit lu était 0.

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

Cas de test:

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