Napisz program, który określi, czy dana macierz reprezentuje quandle. Quandle to zespół wyposażony w pojedynczy (nie przemiennego, nie-asocjacyjnej) działania ◃ która spełnia następujące axioms:

• Operacja jest zamknięta, co oznacza, że a◃b = czawsze jest elementem zestawu, jeśli ai bsą elementami zestawu.
• Operacja jest tuż-self-rozdzielcze: (a◃b)◃c = (a◃c)◃(b◃c).
• Operacja jest podzielna na prawo: dla dowolnej wybranej pary ai bistnieje jedna unikalna ctakac◃a = b
• Operacja jest idempotentna: a◃a = a

Skończony quandle może być reprezentowany jako macierz kwadratowa. Poniżej znajduje się przykład quandle rzędu 5 ( źródło ).

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

Wartość znajdująca się w n-tym rzędzie i m-tej kolumnie (indeksowana 0) jest wartością n◃m. Na przykład w tym quandle 4◃1 = 3. Niektóre właściwości quandle są łatwo widoczne z tej matrycy:

• Jest zamknięty, ponieważ w tej matrycy 5x5 pojawiają się tylko wartości 0-4.
• Jest idempotentny, ponieważ przekątna matrycy wynosi 0 1 2 3 4
• Jest podzielny na prawo, ponieważ żadna kolumna nie zawiera żadnych zduplikowanych wartości. (Wiersze mogą i zwykle będą.)

Trudniej jest przetestować właściwość samo-dystrybucji. Może istnieć skrót, ale najprostszą metodą jest iteracja każdej możliwej kombinacji trzech indeksów, aby to sprawdzić m[m[a][b]][c] = m[m[a][c]][m[b][c]].

Wejście

Dane wejściowe będą listą wierszy macierzy kwadratowej, przy użyciu indeksowania 0 lub indeksu 1 (do wyboru). Każdy wpis będzie jednocyfrową liczbą od 0do 8(lub 1poprzez 9). Będę elastyczny w zakresie formatu wejściowego. Niektóre dopuszczalne formaty obejmują:

• Najbardziej naturalne formatowanie języka dla macierzy lub list, takich jak [[0 0 0][2 1 1][1 2 2]]lub (0,0,0,2,1,1,1,2,2).
• Lista wartości rozdzielonych spacjami, znakami nowej linii, przecinkami itp.
• Pojedynczy ciąg składający się ze wszystkich połączonych ze sobą wartości, takich jak 000211122.

Możesz również przyjąć transpozycję macierzy jako dane wejściowe (zamieniając wiersze z kolumnami). Pamiętaj tylko, aby podać to w swojej odpowiedzi.

Wynik

Pojedyncza wartość true / falsey wskazująca status matrycy jako quandle.

Przykłady 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

Przykłady non-quandles

nie zamknięte

1

0 0 0
2 1 1
1 9 2

nie jest samodystrybucyjny

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

nie podzielny na prawo

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

nie idempotentny

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

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]

Wejście jest transponowane. Wyjście odbywa się za pomocą kodu wyjścia, więc 0 (sukces) jest prawdą, a 1 (niepowodzenie) jest fałszem.

Wypróbuj online!

Jak to działa

e(t)zwraca wyliczone wiersze macierzy wejściowej t - która reprezentuje operator ◃ - jako pary (indeks, wiersz). for(a,A)in e(t)Np iteruje nich przechowywania indeks i rząd umieszczonego w A , więc staje się skrót .At[a]

Pomiędzy tym pierwszym, for(b,B)in e(t)i for C in t, iterujemy wszystkie możliwe uporządkowane krotki (a, b, c) w potędze kartezjańskiej t ³ .

Dla każdej z tych krotek oceniamy wyrażenie

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

Wartość w nawiasach logicznych jest Fałsz wtedy i tylko wtedy, gdy jedno lub więcej z poniższych indywidualnych porównań robi to samo.

• a==A[a]zawiedzie (dla pewnej wartości a ) iff ◃ nie jest idempotentny.

• A[a]in Bnie powiedzie się, jeśli B nie zawiera wszystkich wskaźników A .

  Ponieważ A ma n wskaźników, a B ma n elementów, brak awarii oznacza, że ​​elementy B pasują do wskaźników A , więc ◃ jest zamknięte i podzielne na prawo.

• B>C[B[a]] jest tautologią, ponieważ Python 2 uważał liczby za „mniejsze” niż iterowalne.

• C[B[a]]==t[C[b]][C[a]]zawiedzie dla pewnej wartości, jeśli ◃ nie jest samorozdzielcze .

Jeśli którekolwiek z porównań zwróci False , wyrażenie (0%...)wyrzuci błąd ZeroDivisionError . Ponadto, jeśli ◃ nie jest zamknięte A[a]lub C[b]może również wygenerować błąd IndexError . W obu przypadkach program kończy działanie z kodem stanu 1 (awaria).

Jeśli wszystkie testy zakończą się pomyślnie, program zakończy się normalnie z kodem stanu 0 (sukces).

Haskell, 100 bajtów

Ta odpowiedź wykorzystuje transponowane dane wejściowe.

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

Wygląda na to, że nie mogę użyć osłony wzorca do powiązania operatora infix, więc wherew tym przypadku używam .

(Pierwsza wersja miała 108 bajtów, ale brakowało testu idempotencji, stała wersja wynosiła 120 bajtów, późniejsze wersje miały 108, 103 i 98 bajtów, ale musiałem zdać sobie sprawę z @nimi, że wszystkie były w błędzie: oczywiście muszę zrobić dobrze - test podzielności (co oznacza zamknięcie) przed wykonaniem jakichkolwiek niebezpiecznych !!operacji, ale nadal mogłem wykorzystać większość moich późniejszych pomysłów na golfa, a z jeszcze jednym było 102 bajty, teraz ulepszone przez zmianę kolejności operandów #(co jest i tak ładniejsze, aby zrekompensować transpozycja), aby lepiej wykorzystać jego skojarzenie po lewej)

Użyj w ten sposób:

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

Python 2 , 138 bajtów

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 to lista list liczb całkowitych.

Wypróbuj online!

JavaScript (ES6), 150 bajtów

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

Pobiera dane wejściowe jako tablicę tablic kolumn liczb całkowitych.

Mathematica, 122 bajty

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

Czysta funkcja przyjmująca jako dane wejściowe tablicę 2D liczb całkowitych (indeksowanych 1), z wierszami i kolumnami odwróconymi od konwencji w pytaniu i zwracająca True lub False. Pierwszy wiersz definiuje operację binarnej n_±m_poprawki jako operację quandle.

Dla tablicy lx l, zamknięty i podzielny na prawo jest równoważny każdemu wierszowi (w moim przypadku) będącym pewną permutacją {1, ..., l}, a idempotent jest równoważny dokładnie głównej przekątnej{1, ..., l} . #&@@Union[Sort/@#]==Range@l==Array[#±#&,l=Length@#]Wykrywa więc te trzy warunki. (Zastosowanie Sort/@#tutaj jest powodem, dla którego zdecydowałem się zamienić wiersze i kolumny).

W celu zapewnienia właściwej dystrybucji dosłownie sprawdzamy wszystkie możliwości za pomocą Array[±##2±#==(#2±#)±(#3±#)&,{l,l,l}]). (Zauważ, że ±##2±#automatycznie rozwija się do (#2±#3)±#, ponieważ ##2reprezentuje sekwencję drugiego i trzeciego argumentu w funkcji czystego z trzema zmiennymi). Następnie &&And@@Flatten@sprawdza, czy każdy pojedynczy test został zaliczony. W przypadku niektórych nie zamkniętych quandli błędy mogą być zgłaszane, gdy próbuje uzyskać dostęp do części matrycy, która nie istnieje, ale poprawna odpowiedź jest nadal zwracana.

C ++ 14, 175 bajtów

Jako nienazwana lambda, zakładając, że njest podobna std::vector<std::vector<int>>i wraca przez parametr referencyjny. 0 jest fałszem, wszystko inne jest prawdą.

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

Niegolfowane i użytkowanie:

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