Schreiben Sie ein Programm, das feststellt, ob eine gegebene Matrix ein Problem darstellt. Ein Quandle ist eine Menge, die mit einer einzigen (nicht kommutativen, nicht assoziativen) Operation ausgestattet ist, die die folgenden Axiome befolgt:
- Die Operation ist geschlossen, dh sie
a◃b = c
ist immer ein Element der Menge, wenna
undb
Elemente der Menge sind. - Der Betrieb ist rechtsSelbst distributive:
(a◃b)◃c = (a◃c)◃(b◃c)
. - Die Operation ist rechts teilbar: Für jedes ausgewählte Paar von
a
undb
gibt es eine einzige eindeutigec
solchec◃a = b
- Die Operation ist idempotent:
a◃a = a
Ein endlicher Quandle kann als quadratische Matrix dargestellt werden. Unten sehen Sie ein Beispiel für ein Order-5-Quandle ( Quelle ).
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
Der Wert in der n-ten Zeile und der m-ten Spalte (0-indiziert) ist der Wert von n◃m. Zum Beispiel in diesem Quandle 4◃1 = 3
. Einige der Quandle-Eigenschaften sind in dieser Matrix leicht zu erkennen:
- Es ist geschlossen, da in dieser 5x5-Matrix nur die Werte 0-4 vorkommen.
- Es ist idempotent, weil die Matrixdiagonale 0 1 2 3 4 ist
- Es ist nach rechts teilbar, da keine Spalte doppelte Werte enthält. (Die Zeilen können und werden normalerweise.)
Die Eigenschaft der Rechtsselbstverteilbarkeit ist schwerer zu testen. Möglicherweise gibt es eine Verknüpfung, aber die einfachste Methode besteht darin, jede mögliche Kombination von drei Indizes zu durchlaufen, um dies zu überprüfen m[m[a][b]][c] = m[m[a][c]][m[b][c]]
.
Eingang
Die Eingabe ist die Liste der Zeilen einer Quadratmatrix, entweder mit 0-Index oder 1-Index (Ihre Wahl). Jeder Eintrag ist eine einstellige Zahl von 0
bis 8
(oder 1
bis 9
). Ich werde beim Eingabeformat flexibel sein. Einige akzeptable Formate sind:
- Die natürlichste Formatierung Ihrer Sprache für Matrizen oder Listen, z. B.
[[0 0 0][2 1 1][1 2 2]]
oder(0,0,0,2,1,1,1,2,2)
. - Die Liste der Werte, die durch Leerzeichen, Zeilenumbrüche, Kommas usw. begrenzt sind.
- Eine einzelne Zeichenfolge, die aus allen miteinander verknüpften Werten besteht, z
000211122
.
Sie können auch die Transponierte der Matrix als Eingabe nehmen (Zeilen mit Spalten tauschen). Geben Sie dies einfach in Ihrer Antwort an.
Ausgabe
Ein einzelner Wahrheitswert, der den Status der Matrix als Quandle angibt.
Beispiele für 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
Beispiele für Nicht-Quandles
nicht geschlossen
1
0 0 0
2 1 1
1 9 2
nicht rechtsselbstverteilend
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
nicht rechts teilbar
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
nicht 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
Antworten:
Python 2 ,
104103102 BytesDie Eingabe wird transponiert. Die Ausgabe erfolgt über den Exit-Code, daher ist 0 (Erfolg) wahr und 1 (Misserfolg) falsch.
Probieren Sie es online!
Wie es funktioniert
e(t)
gibt die aufgezählten Zeilen der Eingabematrix t - die einen Operator ◃ darstellt - als (Index-, Zeilen-) Paare zurück.for(a,A)in e(t)
iteriert z. B. über diese, speichert den Index in a und die Zeile selbst in A und wird soA
zu einer Abkürzung fürt[a]
.Zwischen
for(b,B)in e(t)
, undfor C in t
iterieren wir über alle möglichen geordneten Tupel (a, b, c) in der kartesischen Potenz t 3 .Für jedes dieser Tupel wird der Ausdruck ausgewertet
Der Wert des in Klammern gesetzten Booleschen Werts ist genau dann Falsch, wenn einer oder mehrere der folgenden Einzelvergleiche dasselbe tun.
a==A[a]
schlägt fehl (für einen Wert von a ), wenn if nicht idempotent ist.A[a]in B
schlägt fehl, wenn B nicht alle Indizes von A enthält .Da A hat n Indizes und B hat n Elemente, nicht-Ausfall bedeutet , daß die Elemente der B die Indizes entsprechen A , so ◃ geschlossen ist und mit der rechten teilbar.
B>C[B[a]]
ist eine Tautologie, da Python 2 Zahlen als "kleiner" als iterables ansieht.C[B[a]]==t[C[b]][C[a]]
wird für einen bestimmten Wert fehlschlagen, wenn ◃ nicht rechtsselbstverteilend ist.Wenn einer der Vergleiche False zurückgibt , löst der Ausdruck
(0%...)
einen ZeroDivisionError aus . Auch wenn ◃ nicht geschlossen istA[a]
oderC[b]
auch einen IndexError auslösen kann . In beiden Fällen wird das Programm mit dem Statuscode 1 (Fehler) beendet.Wenn alle Tests bestanden wurden, wird das Programm normal mit dem Statuscode 0 (Erfolg) beendet.
quelle
Haskell, 100 Bytes
Diese Antwort verwendet transponierte Eingaben.
Scheint, als ob ich keinen Pattern Guard zum Binden eines Infix-Operators verwenden kann, also verwende ich
where
in diesem Fall.(Erste Version war 108 Bytes, aber fehlender Idempotenztest, feste Version war 120 Bytes, spätere Versionen hatten 108, 103 und 98 Bytes, aber ich musste dank @nimi erkennen, dass sie alle falsch waren: Natürlich muss ich das Richtige tun Teilbarkeitstest (was bedeutet, dass es geschlossen ist), bevor ich gefährliche
!!
Operationen durchführe, aber ich konnte die meisten meiner späteren Golfideen noch verwenden und mit einer weiteren waren es 102 Bytes, die jetzt durch Ändern der Operandenreihenfolge verbessert wurden#
(was sowieso besser ist, um das zu kompensieren) Umsetzung), um die Verknüpfung mit der linken Seite besser nutzen zu können)Verwenden Sie wie folgt:
quelle
Python 2 , 138 Bytes
m
ist eine Liste von Listen mit ganzen Zahlen.Probieren Sie es online!
quelle
JavaScript (ES6), 150 Byte
Nimmt Eingaben als ein Array von Spaltenarrays von Ganzzahlen.
quelle
Mathematica, 122 Bytes
Reine Funktion, die ein 2D-Array von Ganzzahlen (1-indiziert) als Eingabe verwendet, wobei Zeilen und Spalten von der Konvention in der Frage abweichen und
True
oder zurückgebenFalse
. Die erste Zeile definiert die binäre Infix-Operationn_±m_
als Quandle-Operation.Bei einem
l
x-l
Array entspricht geschlossen und rechts teilbar jeder Zeile (in meinem Fall) eine gewisse Permutation{1, ..., l}
, und idempotent entspricht genau der Hauptdiagonale{1, ..., l}
. So#&@@Union[Sort/@#]==Range@l==Array[#±#&,l=Length@#]
erkennt man für diese drei Zustände. (Sort/@#
Deshalb habe ich hier Zeilen und Spalten vertauscht.)Für die Rechtsverteilung prüfen wir buchstäblich alle Möglichkeiten mit
Array[±##2±#==(#2±#)±(#3±#)&,{l,l,l}])
. (Beachten Sie, dass±##2±#
automatisch erweitert wird(#2±#3)±#
, da dies##2
die Folge des zweiten und dritten Arguments für die reine Funktion mit drei Variablen darstellt, über die ein Array erstellt wird.) Anschließend wird&&And@@Flatten@
geprüft, ob jeder einzelne Test bestanden wurde. Bei einigen nicht geschlossenen Fragen werden möglicherweise Fehler ausgegeben, wenn versucht wird, auf einen Teil einer Matrix zuzugreifen, der nicht vorhanden ist, die richtige Antwort jedoch weiterhin zurückgegeben wird.quelle
±m__:=#[[m]];
Ich glaube. Und es gibt eineDiagonal
eingebaute. Und±
ist linksassoziativ , so dass Sie verwenden können#2±#±(#3±#)
, aber wenn ich keinen Fehler gemacht hat , dann ist es kürzer neu zuweisen#
zu#3
und tun#±#2±#3==#±#3±±##2&
. Und es sollte auch möglich sein, das ganzeFlatten@
Teil durch(...&~Array~{l,l,l}<>"")
l=Length
inRange@l
zwar , weil, man sollte zuerst ausgewertet werden, so dass , wenn Sie die Funktion wiederholt verwenden, ich denkeRange
immer noch die vorherige wirdl
, nicht wahr?C ++ 14, 175 Bytes
Als unbenanntes Lambda unter der Annahme
n
, dass es identisch iststd::vector<std::vector<int>>
und über den Referenzparameter zurückgegeben wird. 0 ist falsch, alles andere ist wahr.Ungolfed und Nutzung:
quelle
int a,b,c,u,s=r=m.size()F
stattint s=r=m.size(),a,b,c F
,u=0;r*=s==A.size()&&a==A[a]F
stattr*=s==A.size()&&A[a]==a;int u=0 F
,r*=s>A[b]F
stattr*=A[b]<s F
und~u+(1<<s)
stattu-(1<<s)+1