tło

Na potrzeby tego wyzwania nautomat komórkowy jest po prostu funkcją binarną, fktóra pobiera dwie liczby ze zbioru stanu {0, 1, ..., n-1}jako dane wejściowe i zwraca kolejną liczbę z tego zestawu jako dane wyjściowe. Można go zastosować do listy liczb o długości co najmniej 2 oL = [x0, x1, x2, ..., xk-1]

f(L) = [f(x0, x1), f(x1, x2), f(x2, x3), ..., f(xk-2, xk-1)]

Zauważ, że wynikowa lista zawiera jeden element mniej niż oryginał. Schemat czasoprzestrzeni z fpocząwszy od Llista listy otrzymane przez wielokrotne zastosowanie fdo L, i zbieranie rezultatów w liście. Ostateczna lista ma długość 1. W tym, że lista Ljest identyfikacja sekwencji dla fjeśli każdej listy dwuelementowa na zbiorze stan jest ciągłe podlistę jakiegoś rzędu schemacie czasoprzestrzeni począwszy od L. Jest to równoważne z warunkiem, że żaden inny nCA nie ma takiego dokładnego diagramu czasoprzestrzeni.

Wejście

Nasze wejścia są n-by- nmatrycy całkowitą Mwykaz liczb Lo długości co najmniej 2, i ewentualnie numer n. Macierz Mdefiniuje stan nCA fprzez f(a,b) = M[a][b](przy użyciu indeksowania opartego na 0). Gwarantuje się, że n > 0i to Mi Ltylko zawierają elementy zestawu stanów {0, 1, ..., n-1}.

Wynik

Twój wynik powinien być spójną wartością zgodną z prawdą, jeśli Ljest sekwencją identyfikującą dla urzędu certyfikacji f, a spójną wartością fałszowania w przeciwnym razie. Oznacza to, że wszystkie substancje „tak” skutkują tą samą prawdziwą wartością, a wszystkie substancje „nie” skutkują taką samą wartością fałszu.

Przykład

Zastanów się wejść n = 2, M = [[0,1],[1,0]]i L = [1,0,1,1]. Matryca Mwyznacza binarne XOR automatu f(a,b) = a+b mod 2, a schemat czasoprzestrzeni począwszy od LIs

1 0 1 1
1 1 0
0 1
1

Ten diagram nie zawiera 0 0żadnego wiersza, więc Lnie jest to sekwencja identyfikująca, a prawidłowym wyjściem jest False. Jeśli L = [0,1,0,0]zamiast tego wprowadzimy , diagram czasoprzestrzeni to

0 1 0 0
1 1 0
0 1
1

Rzędy tym diagramie zawiera wszystkie pary wyciągnięte z ustawia stan, a mianowicie 0 0, 0 1, 1 0i 1 1tak Ljest identyfikacja sekwencja i prawidłowe wyjściowy True.

Zasady

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.

Przypadki testowe

Trivial automaton
[[0]] [0,0] 1 -> True
Binary XOR
[[0,1],[1,0]] [1,0,1,1] 2 -> False
[[0,1],[1,0]] [1,0,1,0] 2 -> True
[[0,1],[1,0]] [0,1,0,0] 2 -> True
Addition mod 3
[[0,1,2],[1,2,0],[2,0,1]] [0,1,1,0,0,0,1,0,0] 3 -> False
[[0,1,2],[1,2,0],[2,0,1]] [0,1,1,0,0,0,1,0,1] 3 -> True
Multiplication mod 3
[[0,0,0],[0,1,2],[0,2,1]] [0,1,1,2,0,0,1,0,1] 3 -> False
[[0,0,0],[0,1,2],[0,2,1]] [0,1,1,2,2,2,1,0,1] 3 -> True
Some 4-state automata
[[3,2,2,1],[0,0,0,1],[2,1,3,1],[0,1,2,3]] [0,0,0,0,1,1,1,1] 4 -> False
[[3,2,2,1],[0,0,0,1],[2,1,3,1],[0,1,2,3]] [0,0,0,1,0,1,1,1] 4 -> False
[[3,2,2,1],[0,0,0,1],[2,1,3,1],[0,1,2,3]] [0,1,2,3,3,1,2,3,0] 4 -> True
[[0,1,2,1],[1,0,2,0],[2,2,1,0],[1,2,0,0]] [0,0,1,1,2,2,0,2,1] 4 -> False
[[0,1,2,1],[1,0,2,0],[2,2,1,0],[1,2,0,0]] [0,3,1,3,2,3,3,0,1] 4 -> False
[[0,1,2,1],[1,0,2,0],[2,2,1,0],[1,2,0,0]] [0,3,1,3,2,3,3,0,1,2] 4 -> True

CJam, 53 43 42 bajty

l~:M;_,({_[\1>]zW<_{M\{=}/}%}*;](_*\L*_&,=

Jest to bardzo prosta implementacja definicji (po pierwszej próbie zaczerpnąłem inspirację z Jakube). Oczekuje danych wejściowych w odwrotnej kolejności na STDIN, używając tablic w stylu CJam:

2 [1 0 1 1] [[0 1][1 0]]

Oto uprząż testowa, która uruchamia kod dla wszystkich danych wejściowych (najpierw konwertując je na właściwy format wejściowy). Wyniki w polu wejściowym nie są faktycznie używane. Usuń je, jeśli mi nie ufasz. ;)

Python 2: 93 bajty

M,L,n=input();a=[]
while L:z=zip(L,L[1:]);a+=z;L=[M[i][j]for i,j in z]
print len(set(a))==n*n

Prosta implementacja: znajdź wszystkie pary przez skompresowanie, zapamiętaj je na później i zastosuj M do L. Powtórz. Porównaj liczbę znalezionych unikalnych par.

Dane wejściowe mają formę [[0,1],[1,0]], [0,1,0,0], 2.

Mathematica, 90 83 82 bajtów

f=Length[Union@@Last@Reap[#2//.l_List:>Extract[#,Sow/@Partition[l+1,2,1]]]]==#3^2&

Kolejna prosta implementacja.

Stosowanie:

f[{{0, 1}, {1, 0}}, {0, 1, 0, 0}, 2]

Prawdziwe