Escreva um programa que determine se uma determinada matriz representa um problema. Um quandle é um conjunto equipado com uma única (não-conmutativo, n associativo) ◃ operação que obedece aos seguintes axiomas:

• A operação está fechada, o que significa que a◃b = csempre é um elemento do conjunto se ae bsão elementos do conjunto.
• A operação é auto-direito-distributiva: (a◃b)◃c = (a◃c)◃(b◃c).
• A operação é divisível à direita: para qualquer par escolhido de ae b, há um único único ctal quec◃a = b
• A operação é idempotente: a◃a = a

Um quandle finito pode ser representado como uma matriz quadrada. Abaixo está um exemplo de um quandle do pedido 5 ( origem ).

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

O valor localizado na n-ésima linha e na m-ésima coluna (indexado 0) é o valor de n◃m. Por exemplo, neste dilema 4◃1 = 3,. Algumas das propriedades do quandle são fáceis de ver nesta matriz:

• Está fechado porque apenas os valores 0-4 aparecem nessa matriz 5x5.
• É idempotente porque a diagonal da matriz é 0 1 2 3 4
• É divisível à direita porque nenhuma coluna contém valores duplicados. (As linhas podem, e geralmente serão.)

A propriedade da auto-distributividade correta é mais difícil de testar. Pode haver um atalho, mas o método mais simples é repetir cada combinação possível de três índices para verificar isso m[m[a][b]][c] = m[m[a][c]][m[b][c]].

Entrada

Entrada será a lista de linhas de uma matriz quadrada, usando a indexação 0 ou o índice 1 (sua escolha). Cada entrada será um número de um dígito de 0a 8(ou 1através 9). Eu serei flexível no formato de entrada. Alguns formatos aceitáveis ​​incluem:

• A formatação mais natural do seu idioma para matrizes ou listas, como [[0 0 0][2 1 1][1 2 2]]ou (0,0,0,2,1,1,1,2,2).
• A lista de valores delimitados por espaço em branco, novas linhas, vírgulas etc.
• Uma única sequência que consiste em todos os valores concatenados juntos, como 000211122.

Você também pode aceitar a transposição da matriz como entrada (trocando linhas por colunas). Apenas certifique-se de indicar isso em sua resposta.

Saída

Um único valor de truthy / falsey indicando o status da matriz como um quandle.

Exemplos de Quandles

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

Exemplos de não-quandles

não fechado

1

0 0 0
2 1 1
1 9 2

não é auto-distributivo

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

não divisível à direita

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

não idempotente

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 bytes

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]

A entrada é transposta. A saída é via código de saída, então 0 (êxito) é verdadeiro e 1 (falha) é falso.

Experimente online!

Como funciona

e(t)retorna as linhas enumeradas da matriz de entrada t - que representa um operador ◃ - como (índice, linha) pares. for(a,A)in e(t), por exemplo, itera sobre eles, armazenando o índice em a e a própria linha em A , Atornando-se um atalho para t[a].

Entre o primeiro ,, for(b,B)in e(t)e for C in t, iteramos sobre todas as tuplas possíveis ordenadas (a, b, c) no poder cartesiano t ³ .

Para cada uma dessas tuplas, avaliamos a expressão

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

O valor do booleano entre parênteses é False se e somente se uma ou mais das comparações individuais a seguir fizerem o mesmo.

• a==A[a]falhará (para algum valor de um ) sse ◃ não é idempotent.

• A[a]in Bfalhará se B não contiver todos os índices de A .

  Como A possui n índices e B possui n elementos, não falha significa que os elementos de B correspondem aos índices de A , portanto ◃ é fechado e divisível à direita.

• B>C[B[a]] é uma tautologia, pois o Python 2 considerava os números "menores" que os iteráveis.

• C[B[a]]==t[C[b]][C[a]]falhará por algum valor se ◃ não for auto-distributivo.

Se qualquer uma das comparações retornar False , a expressão (0%...)lançará um ZeroDivisionError . Além disso, se ◃ não está fechado A[a]ou C[b]também pode gerar um IndexError . Nos dois casos, o programa sai com o código de status 1 (falha).

Se todos os testes forem aprovados, o programa será encerrado normalmente com o código de status 0 (êxito).

Haskell, 100 bytes

Esta resposta usa entrada transposta .

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

Parece que não posso usar uma proteção de padrão para vincular um operador infix, então estou usando whereneste caso.

(A primeira versão tinha 108 bytes, mas o teste de idempotência foi perdido, a versão fixa teve 120 bytes, as versões posteriores tiveram 108, 103 e 98 bytes, mas eu tive que perceber, graças ao @nimi, que todas estavam erradas: é claro que preciso fazer o certo. teste de divisibilidade (que implica fechamento) antes de realizar !!operações perigosas , mas eu ainda podia usar a maioria das minhas idéias de golfe mais tarde e, com mais uma, tinha 102 bytes, agora aprimorada alterando a ordem dos operandos #(que é melhor para compensar o transposição) para fazer melhor uso de sua associação à esquerda)

Use assim:

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

Python 2 , 138 bytes

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 é uma lista de listas de números inteiros.

Experimente online!

JavaScript (ES6), 150 bytes

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

Recebe a entrada como uma matriz de matrizes de números inteiros.

Mathematica, 122 bytes

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

Função pura, tendo como entrada uma matriz 2D de números inteiros (1-indexado), com linhas e colunas invertidas da convenção na pergunta e retornando Trueou False. A primeira linha define a operação de infix binárion_±m_ como a operação de quandle.

Para uma matriz lx l, fechado e divisível à direita é equivalente a cada linha (no meu caso) sendo alguma permutação de {1, ..., l}, e idempotente é equivalente à diagonal principal sendo exatamente {1, ..., l}. Então, #&@@Union[Sort/@#]==Range@l==Array[#±#&,l=Length@#]detecta essas três condições. (O uso deSort/@# aqui é o motivo pelo qual escolhi trocar linhas e colunas.)

Para distribuição correta, literalmente verificamos todas as possibilidades usando Array[±##2±#==(#2±#)±(#3±#)&,{l,l,l}]). (Observe que se ±##2±#expande automaticamente para (#2±#3)±#, uma vez que ##2representa a sequência do segundo e terceiro argumentos da função pura de três variáveis ​​que está sendo colocada em matriz.) Em seguida, &&And@@Flatten@verifica se todos os testes foram aprovados. Para algumas quandles não fechadas, podem ser gerados erros ao tentar acessar uma parte de uma matriz que não existe, mas a resposta correta ainda é retornada.

C ++ 14, 175 bytes

Como lambda sem nome, assumindo nser semelhante std::vector<std::vector<int>>e retornando via parâmetro de referência. 0 é falso, tudo o resto é verdadeiro.

#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);}}

Ungolfed e uso:

#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";
}