Contexte

Pour les besoins de ce défi, un nautomate cellulaire à l'état est simplement une fonction binaire fqui prend deux nombres de l'ensemble d'états {0, 1, ..., n-1}en entrée et renvoie un autre nombre de cet ensemble en sortie. Il peut être appliqué à une liste de nombres de longueur au moins 2 parL = [x0, x1, x2, ..., xk-1]

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

Notez que la liste résultante contient un élément de moins que l'original. Un diagramme d'espace - temps de fdémarrage à partir de Lla liste des listes obtenues en appliquant de façon répétée fà L, et la collecte des résultats dans une liste. La liste finale a une longueur 1. Nous disons que la liste Lest une séquence d'identification pour f, si chaque liste à deux éléments sur l'ensemble d'états est une sous-liste contiguë d'une ligne du diagramme d'espace-temps à partir de L. Cela équivaut à la condition qu'aucune autre nautorité de certification à l'état ne dispose de ce diagramme d'espace-temps exact.

Contribution

Vos entrées sont une matrice n-par- nentier M, une liste d'entiers Lde longueur au moins 2, et éventuellement le nombre n. La matrice Mdéfinit une nautorité fde certification -état par f(a,b) = M[a][b](en utilisant une indexation basée sur 0). Il est garanti que n > 0, et que Met Lne contiennent que des éléments de l'ensemble d'états {0, 1, ..., n-1}.

Production

Votre sortie doit être une valeur véridique cohérente s'il Ls'agit d'une séquence d'identification pour l'AC f, et une valeur faussement cohérente dans le cas contraire. Cela signifie que tous les cas de «oui» donnent la même valeur de vérité et tous les cas de «non» donnent la même valeur de faux.

Exemple

Tenez compte des entrées n = 2, M = [[0,1],[1,0]]et L = [1,0,1,1]. La matrice Mdéfinit l'automate XOR binaire f(a,b) = a+b mod 2, et le diagramme espace-temps à partir de Lest

1 0 1 1
1 1 0
0 1
1

Ce diagramme ne contient 0 0aucune ligne, il Lne s'agit donc pas d'une séquence d'identification et la sortie correcte l'est False. Si nous saisissons à la L = [0,1,0,0]place, le diagramme d'espace-temps est

0 1 0 0
1 1 0
0 1
1

Les lignes de ce diagramme contiennent toutes les paires tirées de l'ensemble de l' état, à savoir 0 0, 0 1, 1 0et 1 1, donc Lest une séquence d' identification et la sortie correcte est True.

Règles

Vous pouvez écrire un programme complet ou une fonction. Le nombre d'octets le plus bas gagne et les failles standard sont interdites.

Cas de test

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 octets

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

Il s'agit d'une mise en œuvre très simple de la définition (je me suis inspiré de Jakube après ma première tentative). Il attend une entrée dans l'ordre inverse sur STDIN, en utilisant des tableaux de style CJam:

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

Voici un faisceau de test qui exécute le code par rapport à toutes les entrées (en les convertissant au format d'entrée correct en premier). Les résultats dans le champ de saisie ne sont pas réellement utilisés. Retirez-les si vous ne me faites pas confiance. ;)

Python 2: 93 octets

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

Implémentation simple: trouvez toutes les paires en zippant, mémorisez-les pour plus tard et appliquez M à L. Répétez. Comparez le nombre de paires uniques trouvées.

L'entrée est de la forme [[0,1],[1,0]], [0,1,0,0], 2.

Mathematica, 90 83 82 octets

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

Une autre implémentation simple.

Usage:

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

Vrai