20
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ The word "matrix" is misleading, because this is nothing to do with linear algebra. "Table" would be better (or maybe "Cayley table", but I think that strictly that's only appropriate for a group). \$\endgroup\$ – Peter Taylor Mar 13 '17 at 9:19
7
\$\begingroup\$

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 t3.

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

\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ ±m__:=#[[m]]; I think. And there's a Diagonal built-in. And ± is left-associative so you can use #2±#±(#3±#), but if I didn't make a mistake then it's shorter to reassign # to #3 and do #±#2±#3==#±#3±±##2&. And it should also be possible replace the whole Flatten@ part with (...&~Array~{l,l,l}<>"") \$\endgroup\$ – Martin Ender Mar 13 '17 at 9:07
  • \$\begingroup\$ I wonder if you have to move the l=Length into Range@l though because that one should be evaluated first, so if you use the function repeatedly, I think Range still gets the previous l, no? \$\endgroup\$ – Martin Ender Mar 13 '17 at 9:08
0
\$\begingroup\$

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";
}
\$\endgroup\$
  • \$\begingroup\$ Suggest int a,b,c,u,s=r=m.size()F instead of int s=r=m.size(),a,b,c F, u=0;r*=s==A.size()&&a==A[a]F instead of r*=s==A.size()&&A[a]==a;int u=0 F, r*=s>A[b]F instead of r*=A[b]<s F and ~u+(1<<s) instead of u-(1<<s)+1 \$\endgroup\$ – ceilingcat Mar 21 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.