Écrivez un programme qui déterminera si une matrice donnée représente un dilemme. Un quandle est un ensemble équipé d'une seule opération (non commutative, non associative) ◃ qui obéit aux axiomes suivants:

• L'opération est fermée, ce qui signifie que a◃b = cc'est toujours un élément de l'ensemble si aet bsont des éléments de l'ensemble.
• L'opération est droit auto-distributive: (a◃b)◃c = (a◃c)◃(b◃c).
• L'opération est divisible à droite: pour toute paire choisie de aet b, il existe un unique unique ctel quec◃a = b
• L'opération est idempotente: a◃a = a

Un quandle fini peut être représenté comme une matrice carrée. Ci-dessous, un exemple de quandle d'ordre 5 ( source ).

0 0 1 1 1
1 1 0 0 0
3 4 2 4 3
4 2 4 3 2
2 3 3 2 4

La valeur située à la nième ligne et à la mième colonne (indexée 0) est la valeur de n◃m. Par exemple, dans ce quandle, 4◃1 = 3. Certaines des propriétés quandle sont faciles à voir dans cette matrice:

• Il est fermé car seules les valeurs 0-4 apparaissent dans cette matrice 5x5.
• Elle est idempotente car la diagonale de la matrice est 0 1 2 3 4
• Il est divisible à droite car aucune colonne ne contient de valeurs en double. (Les rangées le peuvent et le seront généralement.)

La propriété de l'auto-distributivité droite est plus difficile à tester. Il peut y avoir un raccourci, mais la méthode la plus simple consiste à parcourir chaque combinaison possible de trois index pour le vérifier m[m[a][b]][c] = m[m[a][c]][m[b][c]].

Contribution

L'entrée sera la liste des lignes d'une matrice carrée, en utilisant soit l'indexation 0 soit l'index 1 (votre choix). Chaque entrée sera un numéro à un chiffre de 0à 8(ou à 1travers 9). Je serai flexible sur le format d'entrée. Certains formats acceptables comprennent:

• Formatage le plus naturel de votre langue pour les matrices ou les listes, comme [[0 0 0][2 1 1][1 2 2]]ou (0,0,0,2,1,1,1,2,2).
• La liste des valeurs délimitées par des espaces, des sauts de ligne, des virgules, etc.
• Une chaîne unique composée de toutes les valeurs concaténées, telles que 000211122.

Vous êtes également autorisé à prendre la transposition de la matrice en entrée (échange de lignes avec des colonnes). Assurez-vous simplement de l'indiquer dans votre réponse.

Production

Une seule valeur vérité / falsey indiquant l'état de la matrice comme un dilemme.

Exemples de dilemmes

0

0 0
1 1

0 0 0
2 1 1
1 2 2

0 0 1 1
1 1 0 0
3 3 2 2
2 2 3 3

0 3 4 1 2
2 1 0 4 3
3 4 2 0 1
4 2 1 3 0
1 0 3 2 4

Exemples de non-quandles

pas fermé

1

0 0 0
2 1 1
1 9 2

pas d'auto-distribution à droite

0 0 1 0
1 1 0 1
2 3 2 2
3 2 3 3

(3◃1)◃2 = 2◃2 = 2
(3◃2)◃(1◃2) = 3◃0 = 3

non divisible à droite

0 2 3 4 1
0 1 2 3 4
3 4 2 2 2
3 3 3 3 3
4 1 1 1 4

0 1 2 3
3 1 2 0
3 1 2 3
0 1 2 3

pas idempotent

1 1 1 1
3 3 3 3
2 2 2 2
0 0 0 0

2 1 0 4 3
3 4 2 0 1
4 2 1 3 0
1 0 3 2 4
0 3 4 1 2

Python 2 , 104 103 102 102 octets

t=input();e=enumerate
[0%(a==A[a]in B>C[B[a]]==t[C[b]][C[a]])for(a,A)in e(t)for(b,B)in e(t)for C in t]

L'entrée est transposée. La sortie se fait via le code de sortie, donc 0 (succès) est vrai et 1 (échec) est faux.

Essayez-le en ligne!

Comment ça fonctionne

e(t)renvoie les lignes énumérées de la matrice d'entrée t - qui représente un opérateur ◃ - sous forme de paires (index, ligne). for(a,A)in e(t), par exemple, itère sur ceux-ci, stockant l'index dans a et la ligne elle-même dans A , Adevient ainsi un raccourci pour t[a].

Entre les premiers ,, for(b,B)in e(t)et for C in t, nous itérons sur tous les tuples ordonnés possibles (a, b, c) dans la puissance cartésienne t ³ .

Pour chacun de ces tuples, nous évaluons l'expression

0%(a==A[a]in B>C[B[a]]==t[C[b]][C[a]])

La valeur du booléen entre parenthèses est False si et seulement si une ou plusieurs des comparaisons individuelles suivantes font de même.

• a==A[a]échouera (pour une valeur de a ) si ◃ n'est pas idempotent.

• A[a]in Béchouera si B ne contient pas tous les indices de A .

  Puisque A a n indices et B a n éléments, la non-défaillance signifie que les éléments de B correspondent aux indices de A , donc ◃ est fermé et divisible à droite.

• B>C[B[a]] est une tautologie, car Python 2 considérait les nombres "plus petits" que les itérables.

• C[B[a]]==t[C[b]][C[a]]échouera pour une certaine valeur si ◃ n'est pas auto-distributif à droite.

Si l'une des comparaisons renvoie False , l'expression lèvera(0%...) une ZeroDivisionError . De plus, si ◃ n'est pas fermé A[a]ou C[b]peut également déclencher une IndexError . Dans les deux cas, le programme se ferme avec le code d'état 1 (échec).

Si tous les tests ont réussi, le programme se terminera normalement avec le code d'état 0 (succès).

Haskell, 100 octets

Cette réponse utilise entrée transposée .

q m=and$(elem<$>v<*>m)++[a#a==a&&a#b#c==a#c#(b#c)|a<-v,b<-v,c<-v]where v=[0..length m-1];i#j=m!!j!!i

On dirait que je ne peux pas utiliser un modèle de garde pour lier un opérateur d'infixe, donc j'utilise wheredans ce cas.

(La première version était de 108 octets mais le test d'idempotence a été manqué, la version fixe était de 120 octets, les versions ultérieures avaient 108, 103 et 98 octets mais j'ai dû réaliser grâce à @nimi qu'elles se trompaient toutes: bien sûr, je dois faire le bien- test de divisibilité (qui implique la fermeture) avant de faire tout dangereux !! opérations , mais je pouvais encore utiliser la plupart de mes idées de golf ultérieures et avec une autre, il était de 102 octets, maintenant amélioré en changeant l'ordre des opérandes de #(ce qui est plus agréable de toute façon pour compenser la transposition) pour mieux utiliser son association à gauche)

Utilisez comme ceci:

*Main> q [[0,1,2,3],[0,1,3,2],[1,0,2,3],[0,1,2,3]]
False

Python 2 , 138 octets

def f(m):R=range(len(m));return all(m[i][i]==i<set(zip(*m)[i])==set(R)>m[m[j][k]][i]==m[m[j][i]][m[k][i]]for i in R for j in R for k in R)

m est une liste de listes d'entiers.

Essayez-le en ligne!

JavaScript (ES6), 150 octets

a=>!(a.some((b,i)=>b[i]-i)|a.some(b=>[...new Set(b)].sort()+''!=[...b.keys()])||a.some((_,i)=>a.some((_,j)=>a.some((b,k)=>b[a[j][i]]-a[b[j]][b[i]]))))

Prend l'entrée comme un tableau de tableaux de colonnes d'entiers.

Mathematica, 122 octets

(n_±m_:=#[[m,n]];#&@@Union[Sort/@#]==Range@l==Array[#±#&,l=Length@#]&&And@@Flatten@Array[±##2±#==(#2±#)±(#3±#)&,{l,l,l}])&

Fonction pure prenant en entrée un tableau 2D d'entiers (indexés 1), avec des lignes et des colonnes inversées par rapport à la convention dans la question, et retournant Trueou False. La première ligne définit l'opération d'infixe binaire n_±m_comme étant l'opération quandle.

Pour un tableau lx l, fermé et divisible à droite est équivalent à chaque ligne (dans mon cas) étant une permutation de {1, ..., l}, et idempotent est équivalent à la diagonale principale étant exactement {1, ..., l}. #&@@Union[Sort/@#]==Range@l==Array[#±#&,l=Length@#]Détecte donc ces trois conditions. (L'utilisation Sort/@#ici est la raison pour laquelle j'ai choisi d'échanger des lignes et des colonnes.)

Pour une distribution à droite, nous vérifions littéralement toutes les possibilités en utilisant Array[±##2±#==(#2±#)±(#3±#)&,{l,l,l}]). (Notez que ±##2±#se développe automatiquement en (#2±#3)±#, car ##2représente la séquence des deuxième et troisième arguments de la fonction pure à trois variables en cours de tableau.) &&And@@Flatten@Vérifie ensuite si chaque test a été réussi. Pour certains dilemmes non fermés, des erreurs peuvent être levées lorsqu'il essaie d'accéder à une partie d'une matrice qui n'existe pas, mais la bonne réponse est toujours renvoyée.

C ++ 14, 175 octets

Comme lambda sans nom, en supposant n être comme std::vector<std::vector<int>>et en retournant via le paramètre de référence. 0 est faux, tout le reste est vrai.

#define F(x);for(x=-1;++x<s;){
[](auto m,int&r){int s=r=m.size(),a,b,c F(a)auto A=m[a];r*=s==A.size()&&A[a]==a;int u=0 F(b)u|=1<<m[b][a];r*=A[b]<s F(c)r*=m[A[b]][c]==m[A[c]][m[b][c]];}}r*=!(u-(1<<s)+1);}}

Non golfé et utilisation:

#include<vector>
#include<iostream>

auto f=
#define F(x);for(x=-1;++x<s;){
[](auto m,int&r){
 int s=r=m.size(),a,b,c
 F(a)
  auto A=m[a];               //shortcut for this row
  r*=s==A.size()&&A[a]==a;   //square and idempotet
  int u=0                    //bitset for uniqueness in col
  F(b)
   u|=1<<m[b][a];            //count this item
   r*=A[b]<s                 //closed
   F(c)
    r*=m[A[b]][c]==m[A[c]][m[b][c]];
   }
  }
  r*=!(u-(1<<s)+1);          //check right-divisibility
 }
}
;

int main(){
 int r;
 std::vector<std::vector<int>>
  A = {
   {0, 0, 1, 1},
   {1, 1, 0, 0},
   {3, 3, 2, 2},
   {2, 2, 3, 3},
  },
  B = {
   {0, 2, 3, 4, 1},
   {0, 1, 2, 3, 4},
   {3, 4, 2, 2, 2},
   {3, 3, 3, 3, 3},
   {4, 1, 1, 1, 4},
  };
 f(A,r);
 std::cout << r << "\n";
 f(B,r);
 std::cout << r << "\n";
}