Wprowadzenie

W tym wyzwaniu przeprowadzimy symulację pewnego probabilistycznego automatu komórkowego przy użyciu bardzo złych liczb pseudolosowych. Automat komórkowy jest zdefiniowany na ciągach binarnych według następującej reguły lokalnej. Załóżmy, że lewy sąsiad komórki i sama komórka mają stany ai b.

• Jeśli min(a,b) == 0, to nowy stan bto max(a,b).
• Jeśli min(a,b) == 1, to nowy stan bjest wybierany losowo z {0,1}.

Poniższy obrazek pokazuje jedną możliwą 10-etapową ewolucję jednego 1.

1
11
101
1111
11001
101011
1111111
10001001
110011011
1010111101

Zauważ, jak dwa sąsiednie 1s czasami ewoluują do 1, a czasami do 0, a najbardziej graniczne bity są zawsze 1s. Twoim zadaniem jest wytworzenie ewolucji automatów komórkowych tej formy.

Wejścia

Twoje dane wejściowe są dodatnią liczbą całkowitą n, oznaczającą liczbę wierszy do wyświetlenia, oraz niepustą listę bitów L, których używamy jako źródła losowości.

Wynik

Twój wynik to lista list lub dwuwymiarowy zestaw bitów, przedstawiający ewolucję pojedynczego 1dla nkroków czasowych, jak na powyższym rysunku. Możesz wypełnić dane wyjściowe za pomocą 0s, aby uzyskać rzędy o równej długości, jeśli to pożądane, ale nie może być wiodących 0s.

Losowe wybory w automacie komórkowym muszą być narysowane z listy L, przeskakując z powrotem na początek, kiedy się wyczerpie. Mówiąc ściślej, jeśli dane wyjściowe są przesuwane po jednym wierszu od góry do dołu, od lewej do prawej, kolejne losowe wybory tworzą listęL powtarzaną tyle razy, ile to konieczne.

Przykład

Załóżmy, że dane wejściowe to n = 7i L = [0,1,0]. Następnie automat komórkowy ewoluuje w następujący sposób podczas 7 kroków, gdzie postawiliśmy vprawo nad każdym przypadkowym wyborem:

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

Jeśli odczytamy wszystkie bity oznaczone a v, otrzymamy 01001001, co Lpowtarza się 2,66 razy. Kolejny losowy bit to0 .

Zasady i punktacja

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone. Dokładny format danych wejściowych i wyjściowych jest nieistotny (z uzasadnionego powodu).

Przypadki testowe

Wersja deterministyczna, każdy losowy bit to 0:

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

Każdy losowy bit to 1:

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

Wersje pseudolosowe:

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 bajty

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

Wypróbuj online: pakiet demonstracyjny lub testowy

Wyjaśnienie:

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

Siatkówka , 139 bajtów

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

Gdzie <empty>wskazuje, że na końcu jest pusta linia końcowa. Każda linia przechodzi w osobny plik i #powinna zostać zastąpiona liniami (0x0A).

Oczekuje, że dane wejściowe będą składać się nz jedności (składającej się z zer, jak w Unary ), po której następuje spacja, a po niej ciąg „pseudolosowy”, np. 10, [1, 0, 0, 1]Będzie czytany jako

0000000000 1001

Wyjście jest jak w wyzwaniu, ale jest uzupełnione zerami, np

1000000000
1100000000
1110000000
1001000000
1101100000
1111110000
1001101000
1101011100
1111111010
1011001111

To było o wiele trudniejsze niż się spodziewałem ...

Python, 142 135 132 131 bajtów

133 132 131 wersja bajtowa

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

zastąpione r[x-1]+r[x]>1przez r[x-1]&r[x]operator bitowy i daje minimalną wartość w(r[x-1],r[x])

Dzięki @ThomasKwa za sugerowanie n*nzamiast tego n**2oszczędza 1 bajt!

Dzięki @Shebang za bajt -1

Wersja 135 bajtów

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

Dzięki @Cole za -7 bajtów:

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

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

Wersja 142-bajtowa

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

Nie jest nawet blisko odpowiedzi @ Jakube, ale świetnie się bawiłem kodując i grając w golfa.

Oczekuje dwóch danych wejściowych: pierwsze dane wejściowe to liczba wierszy, a drugie dane wejściowe to lista źródeł pseudolosowych . Drukuje na konsoli jeden wiersz po drugim, każdy w nowej linii.

Jako przykład:

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]

Teraz krótkie wyjaśnienie, jak to działa:

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    

Sztuczka polega na tym, że wiemy, że lista bitów zawsze zaczyna się i kończy na, 1ponieważ pierwszy i ostatni element nigdy nie są modyfikowane ze względu na specyfikację. pytania. To jest powód tego stwierdzenia[1]+r+[1] .

Ale jeśli rjest inicjalizowany jako [1], nie ma żadnych zmian w pierwszym wierszu, a następnie dodajemy, [1]+r+[1]dlaczego drugi wiersz nie jest[1,1,1] ?

Wynika to z faktu, że przy pierwszej iteracji i=1tak range(1,i)zwraca pustą listę, a w wyniku tego forzrozumienie listy bez niczego do iteracji rstaje się pustą listą [1]+r+[1]=[1,1]. Dzieje się tak podczas pierwszej iteracji, która jest dla nas idealna!

PS: Nie krępuj się z sugestiami, jak bardziej grać w golfa.

MATLAB, 146 143 138

(Działa również na Octave online, ale musisz się zalogować, aby zapisać funkcję w pliku).

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

Funkcja pobiera dane wejściowe ni Lzwraca tablicę ozawierającą dane wyjściowe.

Dla wartości wejściowych njest skalarem i Ljest wektorem kolumny, który można określić w formacie [;;;]. Nie do końca to, co pokazujesz, ale mówisz, że jest elastyczny w granicach rozsądku i wydaje się, że tak.

Dane wyjściowe są sformatowane jako n x ntablica zawierająca zera i jedynki.

I wyjaśnienie:

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

Aktualizacja: Udało mi się zoptymalizować instrukcję if-else, aby zaoszczędzić kilka bajtów. Format wejściowy ponownie zmienił się z powrotem na wektor kolumny.

Haskell, 153 149 bajtów

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

%zwraca listę list bitów. Przykład użycia:

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

O jej! Przenoszenie losowej listy Ljest czystym bólem. Zobaczmy, czy może to być krótsze.

C #, 152 bajty

Nie ma tu nic specjalnego. Funkcja zwraca tablicę 2D, w której pierwszy stopień jest linią, a drugi kolumną.

Wcięte i nowe linie dla przejrzystości:

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 bajtów

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 nie ma operatora przyrostowego, prawda? Cóż, tak się dzieje. Zmienna równania u, zwykle używana z sekwencjami, ma niejasną cechę: gdy ujest wywoływana z argumentem, zmienna𝑛 jest ustawiana na wartość większą niż ten argument. Od tego zależy przyrost warunkowy. (Długo czekałem na jego użycie).

Aby indeksowanie list działało poprawnie, 𝑛jego domyślna wartość musi wynosić 0, a 𝑛Mindomyślna wartość 1, więc wyczyść pamięć RAM kalkulatora lub ustaw te wartości ręcznie przed uruchomieniem.

augment({0},Ans)+augment(Ans,{0oblicza listę sum dwóch sąsiednich elementów, więc zwróci listę zer, 1 i 2. Zatem magia jest na tej linii:

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

Wynikiem tego wiersza będzie to, że elementy listy mają wartość 0, jeśli były równe 0 lub były równe 2, a odczytany bit wynosił 0.

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

Przypadek testowy:

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