Quandle Quandary Episode I: Identifying Finite Quandles

Question

Write a program that will determine if a given matrix represents a quandle. A quandle is a set equipped with a single (non-commutative, non-associative) operation ◃ which obeys the following axioms:

• The operation is closed, meaning that a◃b = c is always an element of the set if a and b are elements of the set.
• The operation is right-self-distributive: (a◃b)◃c = (a◃c)◃(b◃c).
• The operation is right-divisible: For any chosen pair of a and b, there is a single unique c such that c◃a = b
• The operation is idempotent: a◃a = a

A finite quandle can be represented as a square matrix. Below is an example of an order-5 quandle (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

The value located at the n-th row and m-th column (0-indexed) is the value of n◃m. For example, in this quandle, 4◃1 = 3. Some of the quandle properties are easy to see from this matrix:

• It is closed because only values 0-4 appear in this 5x5 matrix.
• It is idempotent because the matrix diagonal is 0 1 2 3 4
• It is right-divisible because no column contains any duplicate values. (The rows can, and usually will.)

The property of right-self-distributivity is harder to test. There might be a shortcut, but the simplest method is to iterate over each possible combination of three indexes to verify that m[m[a][b]][c] = m[m[a][c]][m[b][c]].

Input

Input will be the list of rows of a square matrix, using either 0-indexing or 1-index (your choice). Each entry will be a single digit number from 0 to 8 (or 1 through 9). I will be flexible on the input format. Some acceptable formats include:

• Your language's most natural formatting for matrices or lists, such as [[0 0 0][2 1 1][1 2 2]] or (0,0,0,2,1,1,1,2,2).
• The list of values delimited by whitespace, newlines, commas, etc.
• A single string consisting of all values concatenated together, such as 000211122.

You are also allowed to take the transpose of the matrix as input (swapping rows with columns). Just be sure to state this in your answer.

Output

A single truthy/falsey value indicating the matrix's status as a quandle.

Examples of 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

Examples of non-quandles

not closed

1

0 0 0
2 1 1
1 9 2

not right-self-distributive

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

not right-divisible

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

not 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

Answer 1

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]

Input is transposed. Output is via exit code, so 0 (success) is truthy and 1 (failure) is falsy.

Try it online!

How it works

e(t) returns the enumerated rows of the input matrix t – which represents an operator ◃ – as (index,row) pairs. for(a,A)in e(t), e.g., iterates over these, storing the index in a and the row itself in A, so A becomes a shortcut for t[a].

Between the former, for(b,B)in e(t), and for C in t, we iterate over all possible ordered tuples (a, b, c) in the Cartesian power t³.

For each of these tuples, we evaluate the expression

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

The value of the parenthesized Boolean is False if and only if one or more of the following individual comparisons do the same.

• a==A[a] will fail (for some value of a) iff ◃ is not idempotent.

• A[a]in B will fail if B doesn't contain all indices of A.

  Since A has n indices and B has n elements, non-failure means that the elements of B match the indices of A, so ◃ is closed and right-divisible.

• B>C[B[a]] is a tautology, since Python 2 considered numbers "smaller" than iterables.

• C[B[a]]==t[C[b]][C[a]] will fail for some value if ◃ is not right-self-distributive.

If any one of the comparisons returns False, the expression (0%...) will throw a ZeroDivisionError. Also, if ◃ is not closed A[a] or C[b] may also throw an IndexError. In both cases, the program exits with status code 1 (failure).

If all test passed, the program will exit normally with status code 0 (success).

Answer 2

Haskell, 100 bytes

This answer uses transposed input.

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

Seems like I can't use a pattern guard to bind an infix operator, so I'm using where in this case.

(First version was 108 bytes but missed idempotency test, fixed version was 120 bytes, later versions had 108, 103 and 98 bytes but I had to realize thanks to @nimi that they were all wrong: of course I need to do the right-divisibility test (which implies closedness) before doing any dangerous !! operations, but I could still use most of my later golfing ideas and with one more, it was 102 bytes, now improved by changing the operand order of # (which is nicer anyway to compensate the transposition) to make better use of its associating to the left)

Use like this:

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

Answer 3

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 is a list of lists of integers.

Try it online!

Answer 4

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

Takes input as an array of column arrays of integers.

Answer 5

Mathematica, 122 bytes

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

Pure function taking a 2D array of integers (1-indexed) as input, with rows and columns reversed from the convention in the question, and returning True or False. The first line defines the binary infix operation n_±m_ to be the quandle operation.

For an l x l array, closed and right-divisible is equivalent to every row (in my case) being some permutation of {1, ..., l}, and idempotent is equivalent to the main diagonal being exactly {1, ..., l}. So #&@@Union[Sort/@#]==Range@l==Array[#±#&,l=Length@#] detects for these three conditions. (The use of Sort/@# here is why I chose to swap rows and columns.)

For right-distributive, we literally check all possibilities using Array[±##2±#==(#2±#)±(#3±#)&,{l,l,l}]). (Note that ±##2±# automatically expands to (#2±#3)±#, since ##2 represents the sequence of the second and third arguments to the three-variable pure function being arrayed over.) Then &&And@@Flatten@ checks whether every single test was passed. For some non-closed quandles, errors might be thrown when it tries to access a part of a matrix that doesn't exist, but the correct answer is still returned.

Answer 6

C++14, 175 bytes

As unnamed lambda, assuming n to be like std::vector<std::vector<int>> and returning via reference parameter. 0 is false, everything else is true.

#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 and usage:

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